Databases Reference
In-Depth Information
then no polynomial-size family of (not necessarily monotone) circuits can com-
pute
Clique
n,k
.
A few other interesting examples of monotone functions have also been found.
Thus, [55] gave a family of monotone Boolean functions that can be computed
by polynomial-size monotone circuits, but any monotone
formulas
computing
this family are of size 2
n
ε
,forsome
ε>
0. Or there is a family of monotone
functions [56,8] showing that non-monotone Boolean circuits are in general su-
perpolynomially more succinct than monotone circuits.
Boolean circuits
superpolynomially
more succinct
monotone Boolean circuits
exponentially
more succinct
monotone Boolean formulas
Let us now return to rewritings of CQs and
TBoxes. As we shall
see later on in this section, there is a close correspondence between (arbitrary)
Boolean formulas and FO-rewritings, monotone Boolean formulas and
PE-rewritings, and between monotone Boolean circuits and NDL-rewritings:
OWL 2 QL
Boolean formulas
≈
FO-rewritings
monotone Boolean circuits
≈
NDL-rewritings
≈
monotone Boolean formulas
PE-rewritings
To begin with, we associate with the tree-witness (PE- or NDL-) rewritings
q
tw
certain monotone Boolean functions that will be called hypergraph functions.
A
hypergraph H
=(
V,E
) is given by its
vertices v
∈
V
and
hyperedges e
∈
E
,
2
V
. We call a subset
X
e
=
where
E
⊆
⊆
E independent
if
e
∩
∅
, for any distinct
e,e
∈
X
. The set of vertices that occur in the hyperedges of
X
is denoted by
V
X
.
With each vertex
v
E
we associate propositional
variables
p
v
and
p
e
, respectively. The
hypergraph function f
H
for a hypergraph
H
is computed by the Boolean formula
∈
V
and each hyperedge
e
∈
p
e
.
f
H
=
p
v
∧
(14)
X
independent
e∈X
v∈V \V
X
This definition is clearly inspired by (8). The PE-rewriting
q
tw
of
q
and
T
defines
a hypergraph whose vertices are the atoms of
q
and hyperedges are the sets
q
t
,for
. We denote this hypergraph by
H
T
tree witnesses
t
for
q
and
T
. The formula (14)
defining
f
H
T
is basically the same as the rewriting (8) with the atoms
S
(
z
)in
q
and tree witness formulas
tw
t
treated as propositional variables. We denote
these variables by
p
S
(
z
)
and
p
t
(rather than
p
v
and
p
e
), respectively.
Example 11.
Consider again the CQ
q
and TBox
T
from Example 9. The hy-
pergraph
H
T
and its hypergraph function
f
H
T
are shown below:
