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

   
Coalesce

Several (virtual) edges may connect a pair of nodes. For example, two edges connect the pair of nodes in Figure 4. The first edge was added when the review began to be developed on 15/Mar/1998. The security was set to restrict the edge to page developers. By 25/May/1998, the edge was publicly released as part of the June issue and so the security was weakened to include paid subscribers.


  
Figure 4: Evolving Information About a Review
\scalebox{.68}{\includegraphics{idraw/j.ps}}

When several edges connect a pair of nodes, information about a single property may be distributed among multiple labels. In order to determine the full extent of a property that (conceptually) pertains to a relationship between a pair of nodes, regardless of whether information about that property is distributed among a number of edges, it is advantageous to coalesce the property from the set of edges.

[ ${\it Coalesce\/}\xspace_{\Gamma}:
{\it NAME\/} \times2^{\it EDGES\/} \rightarrow {\it VALUE\/}$]

Assume that a set of edges, F, connects the same pair of nodes. F is coalesced for a single property, p, as follows.


		${\it Coalesce\/}\xspace_{\Gamma}(p, F) \stackrel{\scriptstyle \triangle}{=}{\it PrCs\/}\xspace_p($

$\{ x~\vert~((p{\rm :}~x) \in {\cal L}~\lor~(p{\rm !}~x) \in {\cal L}~\land~v~{\mathop{\longrightarrow}\limits^{\cal L}}~w \in F\})\}~\cup$
$\{ {\it undefined}~\vert~((p{\rm :}~x) \not\in {\cal L}~\land~(p{\rm !}~x) \not\in {\cal L})~\land~$
$v~{\mathop{\longrightarrow}\limits^{\cal L}}~w \in F\})$ `$\mathchoice{\raisebox{-.3ex}{\vbox{\hrule width5pt height2.5pt
\hrule width5pt...
...dth5pt height2.5pt
\hrule width5pt height2.5pt
\hrule width5pt height2.5pt}}}$2

The ${\it PrCs\/}\xspace_p$ operation is a property-specific constructor. Unlike the collapsing constructor, the coalescing constructor does not have to be a restrictor or mutator. Also, the result is not a label, but a single, coalesced value.

following strategy can be used to determine the transaction time for the review of Star Wars IV by Videotastic, irrespective of the security, valid time, etc. First, find all the paths from a root to the review. Note that this requires a certain level of security. Second, collapse each path into a virtual edge. Finally, coalesce the transaction times of the virtual edges.


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

${\cal L}_{\it review\/}$ :=  {(name! review), (security: developer)}
$E :=~ {\it Collapse\/}\xspace_{\Gamma}({\it Match\/}\xspace_{\it DB\/}({\it ROOTS\/},~ {\cal L}_{\it movie\/}.{\cal L}_{\it review\/} ))$
${\it Coalesce\/}\xspace_{\Gamma}(\mbox{\bf trans. time},~E)$
The result is {(&root, (trans. time: [15/Mar/1998 - uc]), &by Videotastic)}. The coalesced transaction time property, [15/Mar/1998 - uc], is the union of the two transaction time intervals in Figure 4. $\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: Updates Up: Additional Query Operators Previous: Collapse

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