Database Reference
In-Depth Information
Inlining patterns
The key ingredient in our algorithms is a translation of a pattern
π
compatible with
aDTD
D
into a
conjunctive query
I
NL
P
ATTERN
(
π
,
D
) over the relational schema
I
NL
S
CHEMA
(
D
). Very roughly, it can be viewed as this:
1. View a pattern
(
x
) as a tree
T
π
in which some attribute values could be variables.
2. Compute the relational database I
NL
D
OC
(
T
π
,
D
) over the schema I
NL
S
CHEMA
(
D
)
(which may have variables as attribute values).
3. View I
NL
D
OC
(
T
π
,
D
) as a tableau of a conjunctive query.
π
The algorithm is actually more complicated because using I
NL
D
OC
“as-is” in Step 2
does not guarantee correctness (we shall explain this shortly).
Towards defining I
NL
P
ATTERN
properly, recall that each tree pattern
(
x
) can be viewed
as an XML document, which we denote by
T
π(
x
)
. In this document, both actual values and
variables can be used as attribute values. For the sake of completeness, we recall how this
is done now. The tree
T
(
x
)
is a single-node tree labeled
, with
x
as attribute values. If
π
π
is
(
x
)[
π
k
(
x
k
)], then the root of
T
π
is labeled
and has
x
as attribute values. It also
has
k
children, with the subtrees rooted at them being
T
π
1
(
x
1
)
,...,
T
π
k
(
x
k
)
.
However, even for a pattern
π
1
(
x
1
)
,...,
(
x
) compatible with a DTD
D
, we may not be able to define
its inlining as the inlining of
T
π(
x
)
, because
T
π(
x
)
need not conform to
D
. For example, if a
DTD has a rule
r
π
ab
and we have a pattern
r
/
a
, it is compatible with
D
,but
T
r
[
a
]
does
not conform to
D
,asitismissinga
b
-node.
Despite this, we can still mark the nodes of
T
π(
x
)
with respect to
D
and define the near-
est appropriate ancestor exactly as it has been done previously. Intuitively, the procedure
I
NL
P
ATTERN
shreds each node of
T
π(
x
)
into a different predicate, and then joins these
predicates using the nearest appropriate ancestor.
→
Example 15.7 The pattern
π
(
x
,
y
)=
r
/
book
(
x
)
/
author
/
name
(
y
)
translates into the following conjunctive query:
⎛
⎞
R
r
(
id
r
)
⎝
⎠
.
Q
π
(
x
,
y
)=
∃
id
r
∃
id
b
∃
id
n
∃
z
1
∃
z
1
∃
z
3
∧
R
book
(
id
b
,
x
,
id
r
,
z
1
,
z
2
)
∧
R
author
(
id
a
,
id
b
,
id
n
,
y
,
z
3
)
Next, we can state the correctness of I
NL
P
ATTERN
. That is, the inlining of π (which is
a conjunctive query over the schema I
NL
S
CHEMA
(
D
)), when applied to the inlining of
T
(which is a relational instance of the same schema), returns
π
(
T
).
Proposition 15.8
Given a nested relational DTD D, a pattern
π
compatible with D, and
a tree T that conforms to D, we have
,
D
)
I
NL
D
OC
(
T
,
D
)
.
π
(
T
)=I
NL
P
ATTERN
(
π
