Databases Reference
In-Depth Information
In the first phase of the algorithm, the subqueries are applied to each segment of
the data graph, in isolation, and intermediate results are computed. Then these
intermediate results are combined in the second phase of the algorithm to give
the answers to the user query
Q
. The proposed algorithm computes the answers
to a given query correctly, independently of: a) the data graph partitioning, b)
how graph segments are stored, c) the query decomposition, and d) the algorithm
used for calculating (partial) results.
2 Data and Query Graphs
In this section we introduce an abstract version of our data model. For this, we
assume two disjoint infinite sets
U
so
and
U
p
of URI references, an infinite set
L
of
(plain) literals
1
,andaset
V
of variables. A triple (
s,p,o
)
∈
U
so
×
U
p
×
(
U
so
∪
L
) is called a
data triple
. A triple (
s,p,o
)
V
)
is called a
query triple
. In a data/query triple,
s
is said to be the
subject
,
p
the
predicate
and
o
the
object
.A
data graph
G
is a set of data triples. A
query graph
(or simply a
query
)
Q
is a set of query triples. The
output pattern
O
(
Q
)ofaquery
Q
is the sequence (
X
1
,...,X
n
) of the variables appearing in
Q
. A data graph
G
is a
subgraph
of a data graph
G
if
G
⊆
∈
(
U
so
∪
V
)
×
U
p
×
(
U
so
∪
L
∪
G
.Aquery
Q
is a
subquery
of a query
Q
if
Q
⊆
Q
. Note that, data graphs correspond to ground RDF graphs defined in [2,9],
i.e. RDF graphs without blank nodes. Graphically, a data/query triple (
s,p,o
)is
represented by
s
p
−→
o
. A node (subject or object) is represented as a rounded
rectangle unless it is literal which is represented by a rectangle. Strings with initial
lowercase letters represent predicates, while strings with initial uppercase letters
denote URIs. Literals are strings enclosed in double quotes. Finally, we assume
that variables' names begin with the question mark symbol (?).
Example 1.
Fig. 1(a) (resp. 1(b)) depicts a data (resp. query) graph.
Person1
?W
Person2
hasSupervisor
Person3
hasSupervisor
hasAuthor
hasAuthor
Person4
hasAuthor
hasAuthor
hasAuthor
?A
hasAuthor
hasAuthor
hasTitle
Article2
Article3
Article1
?T
year
year
publishedIn
publishedIn
publishedIn
hasTitle
“2008”
publishedIn
hasTitle
hasTitle
year
year
Journal1
“2008”
“Title1”
“Title3”
Journal1
“Title2”
“2005”
“2008”
Journal2
(b)
(a)
Fig. 1.
(a) A data graph, and (b) a query graph
1
In this paper we do not consider typed literals.
Search WWH ::
Custom Search