next up previous
Next: Retrieving Information From Semistructures Up: Extending a Semistructured Data Previous: Extending a Semistructured Data

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 pi is the name of a property, (ii) xi 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 pi, and (iv) each property name is unique, that is, $\forall i, j (p_i = p_j \Rightarrow i = j)$.

A required property, say pi with value xi, 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)$.

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


 


next up previous
Next: Retrieving Information From Semistructures Up: Extending a Semistructured Data Previous: Extending a Semistructured Data

Copyright © 1998. Curtis E. Dyreson, Michael H. B&. All rights reserved.