next up previous
Next: Collapse Up: Additional Query Operators Previous: Additional Query Operators

   
Slice

It is often useful to slice a portion from a property in each label along a path. The most common example is a transaction-time slice, or rollback, query that determines the other properties as of a particular transaction time. A path is sliced by slicing each property in a label on the path, and checking whether the resulting path is valid.


[ ${\it Slice\/}\xspace_{\Gamma}:
{\it LABEL\/} \times 2^{\it PATHS\/} \rightarrow
2^{\it PATHS\/}$]

A descriptor, ${\cal L}$, slices the labels along each path in a set of paths, P, as follows.


		${\it Slice\/}\xspace_{\Gamma}({\cal L},~P) \stackrel{\scriptstyle \triangle}{=}...
...me}}}~\ldots~ {\mathop{\longrightarrow}\limits^{{{\cal L}_m^\prime}}}~w ~\vert~$

$v~{\mathop{\longrightarrow}\limits^{{{\cal L}_1}}}~\ldots~{\mathop{\longrightarrow}\limits^{{{\cal L}_m}}}~w \in P~\land~$
${\cal L}_1^\prime = {\it LaSl\/}\xspace_{\Gamma}({\cal L},{\cal L}_1) \wedge \l...
...e {\cal L}_m^\prime = {\it LaSl\/}\xspace_{\Gamma}({\cal L},{\cal L}_m)\ \wedge$
${\it Valid\/}\xspace_{\Gamma}(v~{\mathop{\longrightarrow}\limits^{{{\cal L}_1^\prime}}}~\ldots~ {\mathop{\longrightarrow}\limits^{{{\cal L}_m^\prime}}}~w)$`$\mathchoice{\raisebox{-.3ex}{\vbox{\hrule width5pt height2.5pt
\hrule width5pt...
...dth5pt height2.5pt
\hrule width5pt height2.5pt
\hrule width5pt height2.5pt}}}$2

A label is sliced property by property. This slicing is complicated by missing properties. Specifically, if a property is missing from the descriptor, but present in the label, it is passed unchanged into the result. A missing property in a label is also missing in the result, except if the descriptor requires the property, in which case the property from the descriptor is added to the result. Finally, if the property is both in the label and the descriptor then a property-specific constructor slices the property appropriately and adds it to the result.

[ ${\it LaSl\/}\xspace_{\Gamma}:
{\it LABEL\/} \times {\it LABEL\/} \rightarrow {\it LABEL\/}$]

A label, ${\cal L}$, slices a label, ${\cal S}$, as follows.


		${\it LaSl\/}\xspace_{\Gamma}({\cal L},~{\cal S}) \stackrel{\scriptstyle \triangle}{=} ~$

$\{(p{\rm !}~ {\it PrSl\/}\xspace_p(x,~y))~\vert~$
$ (p{\rm !}~x) \in {\cal L} \wedge ((p{\rm :}~ y) \in {\cal S} \vee (p{\rm !}~ y) \in {\cal S})\}~\cup$
$\{(p{\rm !}~ {\it PrSl\/}\xspace_p(x,~y))~\vert~$
$ (p{\rm !}~y) \in {\cal S} \wedge ((p{\rm :}~ x) \in {\cal L} \vee (p{\rm !}~ x) \in {\cal L})\}~\cup$
$\{(p{\rm :}~ {\it PrSl\/}\xspace_p(x,~y))~\vert~(p{\rm :}~x) \in {\cal L} \wedge (p{\rm :}~ y) \in {\cal S} \}~\cup$
$\{(p{\rm !}~ y)~\vert~(p{\rm !}~ y) \in {\cal S} \wedge \neg \exists x [(p{\rm :}~ x) \in {\cal L} \vee (p{\rm !}~ x) \in {\cal L}] \}~\cup$
$\{(p{\rm !}~ x)~\vert~(p{\rm !}~ x) \in {\cal L} \wedge \neg \exists y [(p{\rm :}~ y) \in {\cal L} \vee (p{\rm !}~ y) \in {\cal L}] \}~\cup$
$\{(p{\rm :}~ x)~\vert~(p{\rm :}~ x) \in {\cal L} \wedge \neg \exists y [(p{\rm :} y) \in {\cal S} \vee (p{\rm !}~ y) \in {\cal S}] \}$ `$\mathchoice{\raisebox{-.3ex}{\vbox{\hrule width5pt height2.5pt
\hrule width5pt...
...dth5pt height2.5pt
\hrule width5pt height2.5pt
\hrule width5pt height2.5pt}}}$2

Recall that ${\it PrSl\/}\xspace_p$ is a property-specific constructor that slices a property. Table 1 shows the slicing operators.


 A user is interested in retrieving the other properties about movie stars names as of the current time. That set of paths can be obtained as follows.


		 ${\cal L}_{\it m\/}$
:= {(name! movie)}

${\cal L}_{\it s\/}$ := {(name! stars)}
${\cal L}_{\it n\/}$ := {(name! name)}
${\cal L}_{\it now\/}$ := {(trans. time: [now - now])}
${\it Slice\/}\xspace_{\Gamma}({\cal L}_{\mathit{now}}, {\it Match\/}\xspace_{\it DB\/}({\it ROOTS\/}, ~{\cal L}_{\it m\/}.{\cal L}_{\it s\/}.{\cal L}_{\it n\/}))$

Note that a ${\it Slice\/}\xspace_{\Gamma}$ with ${\cal L}_{\it now\/}$ as its first argument differs from a Match with that descriptor since the transaction time property of every label (that has a transaction time) in the sliced path is [now - now], whereas the transaction time property in the matched path would be unchanged from the underlying data.  $\mathchoice{\raisebox{-.3ex}{\vbox{\hrule width5pt height2.5pt
\hrule width5pt...
...dth5pt height2.5pt
\hrule width5pt height2.5pt
\hrule width5pt height2.5pt}}}$2



next up previous
Next: Collapse Up: Additional Query Operators Previous: Additional Query Operators

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