Databases Reference
In-Depth Information
T
H
and certain single-individual
ABoxes amounts to computing the Boolean function
f
H
.Let
H
=(
V,E
)bea
hypergraph of degree 2 with
V
=
q
H
over
It turns out that answering the CQ
{
v
1
,...,v
n
}
and
E
=
{
e
1
,...,e
m
}
.Wedenote
by
α
(
v
i
)the
i
-th component of
α
∈{
0
,
1
}
n
and by
β
(
e
j
)the
j
-th component of
β
∈{
0
,
1
}
m
. Define an ABox
A
α
,
β
with a single individual
a
by taking
A
α
,
β
{
R
v
i
(
a, a
)
|
α
(
v
i
)=1
}∪{
A
e
j
(
a
)
|
β
(
e
j
)=1
}
.
=
Theorem 6 ([30]).
Let H
=(
V,E
)
be a hypergraph of degree 2. Then, for any
tuples
}
|V |
and
}
|E|
,
α
∈{
0
,
1
β
∈{
0
,
1
(
T
H
,
A
α
,
β
)
|
=
q
H
iff f
H
(
α
,
β
)=1
.
What is so special about hypergraphs of degree
≤
2? First, one can show that all
hypergraph functions of degree
2 can be computed by polynomial-size mono-
tone Boolean circuits—in fact, by polynomial-size monotone nondeterministic
branching programs (NBPs), also known as switching-and-rectifier networks [29].
Moreover, the converse also holds: if a family of Boolean functions is computable
by polynomial-size NBPs then it can be represented by a family of polynomial-
size hypergraphs of degree
≤
2. As a consequence of this fact, we obtain a positive
result on the size of NDL-rewritings:
≤
Theorem 7 ([30]).
For any CQ
q
and any TBox
T
of depth one, there is an
NDL-rewriting of
q
and
T
of polynomial size.
On the 'negative' side, there are families of Boolean functions
f
n
that are com-
putable by polynomial-size monotone NBPs, but any monotone Boolean formu-
las computing
f
n
are of superpolynomial size, at least 2
Ω
(log
2
n
)
,tobemore
precise. For example, Grigni and Sipser [24] consider functions that take the ad-
jacency matrix of a directed graph of
n
vertices with a distinguished vertex
s
as
input and return 1 iff there is a directed path from
s
to some vertex of outdegree
at least two. Can we use this lower bound to establish a corresponding super-
polynomial lower bound for the size of PE-rewritings? The answer naturally
depends on what syntactical means we can use in our rewritings.
Let us assume first that the FO- and NDL-rewritings of CQs
q
and
OWL 2 QL
TBoxes
can contain equality (=), any non-predifined predicates and only
those constant symbols that occur in
T
. Thus, we do not allow new constants
and various built-in predicates in our rewritings. Such rewritings are sometimes
called
pure
.
As any NBP corresponds to a polynomial-size hypergraph of degree
q
2, we
obtain a sequence
H
n
of polynomial hypergraphs of degree 2 such that
f
n
=
f
H
n
.
We take the sequence of CQs
≤
q
n
and TBoxes
T
n
associated with the hypergraphs
of degree
2 for the sequence
f
n
of Boolean functions chosen above. We show
that any pure PE-rewriting
≤
q
n
of
T
n
can be transformed into a monotone
Boolean formula
χ
n
computing
f
n
and having size
q
n
and
≤|
q
n
|
.
q
n
in the following way: take a
constant
a
and replace every subformula of the form
To define
χ
n
, we eliminate the quantifiers in
q
n
with
ψ
(
a
),
∃
xψ
(
x
)in
