Database Reference
In-Depth Information
however that our implem
attributes, text values, etc..
mentation can handle full XML documents includ
ding
Paper Organization:
The
describes the basic concep
can be stored in a more sp
how these shared structur
grammars, and it describes
tree grammars. Section 3 de
data directly and discusses
paths to an update DAG,
isolated nodes, and sharing
of the presented update met
Finally, Section 6 summariz
remainder of this paper is organized as follows. Sectio
pt of grammar-based compression, i.e., how an XML t
pace saving way by sharing similar structures, it expla
res can be represented by patterns being used in t
how paths in XML document trees correspond to path
escribes how updates can be performed on the compres
the phases of performing updates: combining the upd
isolating the update DAG from the grammar, updat
g of identical sub-trees. Section 4 describes the evaluat
thod. Section 5 compares our contribution to related wo
zes our contribution.
on 2
tree
ains
tree
hs in
ssed
date
ting
tion
ork.
2 Sharing Similar Tr
rees
2.1 The Paper's Example
e Document
To simplify the following p
and its label. The following
compression and to give a
compressed data.
presentation, we do not distinguish between an XML n
g example is used for explaining the idea of grammar-ba
visual representation of our idea of direct updates on
node
ased
the
Fig. 1.
Document tree o
of an XML document D with repeated matches of patterns
Fig. 1 shows an example
r's first-child is k1 whose
generated by the following
the symbol
e XML document D represented as a binary tree, where
e next-sibling is k2. This XML document tree can
grammar using the non-terminal S as the start symbol
sub-tree, i.e., the right hand side of the grammar rule
rder notation of the binary tree given in Fig. 1:
e.g.
be
and
is a
as the empty
term representing the pre-or
ε
S
r(k1(c(d(j(m(
ε
,
ε
),b
b(
ε
,
ε
)),e(
ε
,
ε
)),
ε
), k2(h(g(j(n (
ε
,
ε
),b(
ε
,
ε
)),e(
ε
,
ε
)),
ε
),
k3(c(d(j(o (
ε
,
ε
),b(
(
ε
,
ε
)),e(
ε
,
ε
)),
ε
), k4(h(g(j(p (
ε
,
ε
),b(
ε
,
ε
)),e(
ε
,
ε
)),
ε
),
ε
)))),
ε
ε
)
Grammar 1:
G
Grammar corresponding to the binary tree of Fig. 1
