Database Reference
In-Depth Information
sDoc()
sElem(1,"SigmodRecord")
sElem(2,"issue")
attr(9,"vol","33")
attr(10,"num","2")
sElem(3,"articles")
sElem(4,"article")
sElem(5,"name")
text(6,"EDBT04 W...")
eElem(5,"name")
sElem(7,"author")
text(8,"B. Catania")
eElem(7,"author")
eElem(4,"article")
eElem(3,"articles")
eElem(2,"issue")
...
eDoc()
Fig. 1.
XML Document representation: tree-based (left), event-based (right)
Alternatively, a document can be represented as a stream of SAX-like events, which
describe the nodes encountered in a depth-first traversal of the document. A document
D
is an ordered sequence of events:
sDoc
() and
eDoc
(), indicating the start/end of
the document;
sElem
(
v,n
)
and
eElem
(
v,n
), indicating the start/end of element
v
tagged
n
;
attr
(
v,n,s
)and
text
(
v,s
), indicating the attribute/text node
v
with name
n
and value
s
. Fig. 1 contrasts the tree/event-based representations of a fragment of
the
SigmodRecord
document to be updated. In the former, dotted lines are used to
represent edges leading to attribute nodes.
In handling PULs, we need to check whether some relationships (like parent-child,
element-attribute, left-right sibling) hold among two nodes in both representations. This
information is obtained without directly accessing the document through a labeling
scheme [12] associated with nodes through function
l
. In this scheme, the introduc-
tion/deletion of nodes does not require node re-labelling. Table 1 reports the predicates
that can be assessed through the adopted labeling scheme.
2.2
Update Operations and PULs
Table 2 reports the primitives defined in [15] that we consider, where
v ∈ V
is a node,
P
=[
T
1
,...,T
k
]
,
k ≥
0
, is a list (possibly empty in case of the
repN
or
repC
op-
eration) of trees,
n ∈N
is a name,
s ∈V
is a value. Given an operation
op
,
t
(
op
)
denotes its target node,
o
(
op
)
denotes its name, and
p
(
op
)
denotes its second parameter
Ta b l e 1 .
Structural relationships
Predicate Description
v
1
v
2
v
1
precedes
v
2
in document order
v
1
s
v
2
v
1
is the (adjacent) left sibling of
v
2
v
1
s
v
2
v
1
is a preceding sibling of
v
2
v
1
/
c
v
2
v
1
is a child of
v
2
v
1
/
a
v
2
v
2
v
1
/
d
v
2
v
1
is a descendant of
v
2
v
1
/
¬
d
v
2
v
1
is a descendant of
v
2
but not an attribute of
v
1
v
1
is an attribute of
