A Semistructured Model With Properties

A semistructured database, ${\it DB\/} = (V,~E,~{\it \&root\/},~\Gamma)$, consists of a set of nodes, V, a set of labeled, directed edges, E, a single root node, ${\it\&root\/}$, and a collection of so-called property operations, $\Gamma$, that determine the semantics of properties. We also define ${\it ROOTS\/} \subseteq E$ to be the set of edges emanating from ${\it \&root}$. (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 ${\cal L}$ is denoted $v~{\mathop{\longrightarrow}\limits^{\cal L}}~w$. ${\cal L}$ is a label with properties.

[Label with properties]

A label with properties, ${\cal L}$, is a set of m pairs, $\{(p_1{\rm :}~x_1),~(p_2{\rm :}~x_2),~\ldots~,~(p_m{\rm :}~x_m)\}$, 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 $x_i \in {\it domain\/}(p_i)$, (iii) property operations exist in $\Gamma$ for each p_i, and (iv) each property name is unique, that is, $\forall i, j (p_i = p_j \Rightarrow i = j)$.

A required property, say p_i with value x_i, is denoted $(p_i{\rm !}~ x_i)$. $\mathchoice{\raisebox{-.3ex}{\vbox{\hrule width5pt height2.5pt \hrule width5pt... ...dth5pt height2.5pt \hrule width5pt height2.5pt \hrule width5pt height2.5pt}}}$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. $\mathchoice{\raisebox{-.3ex}{\vbox{\hrule width5pt height2.5pt \hrule width5pt... ...dth5pt height2.5pt \hrule width5pt height2.5pt \hrule width5pt height2.5pt}}}$2

To accommodate properties in queries, several operations for each property are needed, namely property collapse ( ${\it PrCl\/}\xspace$), property match ( ${\it PrMa\/}\xspace$), property coalesce ( ${\it PrCs\/}\xspace$), and property slice ( ${\it PrSl\/}\xspace$) (see Section 3.2). These operations determine the semantics of properties and are included in $\Gamma$.

[Property operations]

For each property p in a label, operations with the following signatures should be present in $\Gamma$. For brevity, let T be ${\it domain\/}(p)$.

• ${\it PrCl\/}\xspace_p: T \times T \rightarrow T~\cup~ {\it\{undefined\}}$
  
• ${\it PrMa\/}\xspace_p: T \times T \rightarrow {\it BOOLEAN}$
  
• ${\it PrCs\/}\xspace_p: 2^{T~\cup~{\it\{undefined\}}} \rightarrow T~\cup~ {\it\{undefined\}}$
  
• ${\it PrSl\/}\xspace_p: T \times T \rightarrow T~\cup~ {\it\{undefined\}}$ $\mathchoice{\raisebox{-.3ex}{\vbox{\hrule width5pt height2.5pt \hrule width5pt... ...dth5pt height2.5pt \hrule width5pt height2.5pt \hrule width5pt height2.5pt}}}$2

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.

 

Table 1: Property Operations

	name	valid time	security	transaction time	price	quality
${\it PrMa\/}\xspace_p$	=	truth assignment	overlaps	overlaps	$\geq$	$\leq$
${\it PrCl\/}\xspace_p$	concatenation	AND	intersection	intersection	sum	minimum
${\it PrCs\/}\xspace_p$	union	OR	coalesce	coalesce	$\min$	average
${\it PrSl\/}\xspace_p$	semantic error	conjunct elimination	intersection	intersection	> pruning	< pruning