Data Updates

An edge can be inserted at any time into the semistructure. On insertion, the transaction time of the label on the inserted edge is set to $[{\it current~time} - {\rm uc}]$.

[Edge insertion]

Let T be the current time. An edge is inserted into a semistructure, $DB = (V,~E,~{\it\&root\/},~\Gamma)$, as follows.

		${\it Insert\/}_{\it DB\/}(T, v~{\mathop{\longrightarrow}\limits^{\cal L}}~w) \stackrel{\scriptstyle \triangle}{=}$

				$(V~\cup~\{v,~w\},~E~\cup~\{v~{\mathop{\longrightarrow}\limits^{{\cal L}^\prime}}~w\},~{\it\&root\/},~\Gamma)$,


where${\cal L}^\prime = {\cal L}~\cup~${(transaction time:$~[T - {\rm uc}])\}.$`$\mathchoice{\raisebox{-.3ex}{\vbox{\hrule width5pt height2.5pt
\hrule width5pt...
...dth5pt height2.5pt
\hrule width5pt height2.5pt
\hrule width5pt height2.5pt}}}$2

Redundant and overlapping labels are permitted on edges, i.e., the data is not stored coalesced. Note also that edge insertion inserts nodes if the nodes not already exist in the database. We do not give a separate operation to insert only a node (our focus is on the relevant changes needed to support properties in labels).

Edges are (logically) deleted by terminating their transaction-time interval.

[Edge deletion]

Let T be the current time. An edge is deleted from a semistructure, $DB = (V,~E,~{\it\&root\/},~\Gamma)$, as follows.

		${\it Delete\/}_{\it DB\/}(T,~v~{\mathop{\longrightarrow}\limits^{\cal L}}~w) \stackrel{\scriptstyle \triangle}{=}$

				$(V,~(E~ - ~\{v~{\mathop{\longrightarrow}\limits^{\cal L}}~w\})~\cup ~\{v~{\mathop{\longrightarrow}\limits^{{\cal L}^\prime}}~w\},~{\it\&root\/},~\Gamma)$,

where the label ${\cal L}^\prime$ is exactly the same as ${\cal L}$ except in the transaction time property. If ${\cal L}$ has a transaction time property, say (transaction time: x), then

		${\cal L}^\prime = {\cal L} - \{($transaction time:$~x)\}~\cup~$

				$\{($transaction time:$~(x~\cap~[{\rm beginning} - T]))\}.$

If the transaction time property is missing from ${\cal L}$,

		${\cal L}^\prime = {\cal L} ~\cup ~\{($transaction time:$~[{\rm beginning} - T])\}.$
`$\mathchoice{\raisebox{-.3ex}{\vbox{\hrule width5pt height2.5pt
\hrule width5pt...
...dth5pt height2.5pt
\hrule width5pt height2.5pt
\hrule width5pt height2.5pt}}}$2

Finally, a node can be (logically) deleted by removing all incoming edges, and an edge modification is modeled as an edge deletion followed by an edge insertion.

transactions that created the two edges in Figure 4 are given below. Let

		v :=  &Star Wars IV, 
		w :=  &by Videotastic, 
		${\cal L}_1~:=~~\{$(name: review),   (security! developer)}, and 
		${\cal L}_2~:=~~\{$(name: review),  (security! paid subscriber)}.


On 15/Mar/1998, the first edge is inserted:

				${\it Insert\/}_{\it DB\/}($15/Mar/1998, $v~{\mathop{\longrightarrow}\limits^{{\cal L}_1}}~w)$


On 24/May/1998, the first edge is deleted:

				${\it Delete\/}_{\it DB\/}($24/May/1998, $v~{\mathop{\longrightarrow}\limits^{{\cal L}_1}}~w)$


On 25/May/1998, the second edge is inserted:

				${\it Insert\/}_{\it DB\/}($25/May/1998, $v~{\mathop{\longrightarrow}\limits^{{\cal L}_2}}~w)$
`$\mathchoice{\raisebox{-.3ex}{\vbox{\hrule width5pt height2.5pt
\hrule width5pt...
...dth5pt height2.5pt
\hrule width5pt height2.5pt
\hrule width5pt height2.5pt}}}$2