A semistructured database, , consists of a set of nodes, V, a set of labeled, directed edges, E, a single root node, , and a collection of so-called property operations, , that determine the semantics of properties. We also define to be the set of edges emanating from . (These edges lead to what would normally be considered the roots of the semistructure; the extra level of indirection serves to record the properties of the root nodes.) An edge in E from node v to node w with the label is denoted . is a label with properties.
[Label with properties]
A label with properties, , is a set of m pairs, , where (i) each p_{i} is the name of a property, (ii) x_{i} is a value drawn from the property's domain, that is , (iii) property operations exist in for each p_{i}, and (iv) each property name is unique, that is, .
A required property, say p_{i} with value x_{i}, is denoted . 2
Figure 2, an edge connects &movies to &Color of Night. The label is the set of properties {(name: movie), (security! over 18)}. The security property is a required property. It is intended to limit access to the node to individuals over 18 years of age. 2
To accommodate properties in queries, several operations for each property are needed, namely property collapse ( ), property match ( ), property coalesce ( ), and property slice ( ) (see Section 3.2). These operations determine the semantics of properties and are included in .
[Property operations]
For each property p in a label, operations with the following signatures should be present in . For brevity, let T be .
These operations collapse, match, coalesce, and slice property values.
New properties may be introduced at any time by registering the appropriate operations with the database. Default semantics are available for the operations, as will be discussed in Section 3.4.2. Table 1 lists operations for one possible implementation of the properties discussed in this paper. The role of the property operations will become clear when querying is considered, next.