Data Graph Satisfying a Schema Graph
given data graph
D
and schema graph
S
D
is an
instance of
S
(or
D
satisfies
S
) if
there exists a
simulation
R
from
D
to
S
such that
(root(D), root(S))
is in
R
a
simulation
is a relation
R
between nodes:
if
(u,v)
is in
R
and
(u,x)
labelled
l
is in
D
then there exists
(v,y)
labelled
l
in
S
such that
(x,y)
is in
R
for our example:
node
&1
in
D
related under
R
to node at target of edge labelled
bib
in
S
&2
and
&4
related to node at target of edge labelled
paper
&3
related to node at target of edge labelled
book
note that above two cases need to satisfy requirements of edges labelled
references
as well
&10
and
&11
related to node at target of edge labelled
author
...
Peter Wood
16 of 21
