Databases Reference
In-Depth Information
Algorithm 1.
Basic Query Rewriting algorithm
Input
: Conjunctive query
q
, DL ontology
O
Output
: Union (set) of conjunctive queries
1
P
:=
P
q
2
repeat
3
P
:=
P
foreach
q ∈ P
do
4
foreach
g in q
do
// expansion
5
foreach
axiom i of one of the forms 1-4 from Table 1 in O
do
6
if
i is applicable to g
then
7
P
:=
P ∪
q
[
g/
gr(
g,i
)]
// see Table 2
8
9
until
P
=
P
10
return
P
Tabl e 2.
Semantics of gr(
g,i
) of Algorithm 1 (' ' stands for a “fresh” variable)
g
i
gr(
g/i
)
(
x,
rdf:type
,A
)
B A
(
x,
rdf:type
,B
)
∃P A
(
x,
)
∃P
−
A
(
,x
)
(
x,P
1
,y
)
P
2
P
1
(
x,P
2
,y
)
Example 3
Taking Query 4 again, the BGP
{
(?
X,
a
,
foaf:Agent
)
}
corresponds to the
conjunctive query:
q
(?
X
)
←
(?
X,
rdf:type
,
foaf:Agent
)
which expanded by Algorithm 1 with respect to the ontology in Fig. 4(b)
results in the following UCQ:
q
(?
X
)
←
(?
X,
a
,
foaf:Agent
)
q
(?
X
)
←
(?
X,
a
,
foaf:Person
)
q
(?
X
)
←
(?
X,
a
,
foaf:Organization
)
q
(?
X
)
←
(?
X,
foaf:made
,
?
Y
)
The resulting UCQ can again (using the UNION pattern) be translated
back to SPARQL:
