Database Reference
In-Depth Information
QUERY ENTAILMENT ALGORITHM
As with the algorithms for basic inference services and simple query answering, our algorithm for decid-
ing fuzzy query entailment is also based on tableau algorithms. However, the query entailment problem
can not be reduced to the knowledge base satisfiability problem, since the negation of a fuzzy conjunc-
tive query is not expressible with existing constructors provided by an
f
-SHIF (
D
knowledge base.
For this reason, tableau algorithms for reasoning over knowledge bases is not sufficient. A knowledge
base may have infinitely many possibly infinite models, whereas tableau algorithms construct only
a subset of finite models of the knowledge base. The query entailment holds only if the query is true in
all models of the knowledge base, we thus have to show that inspecting only a subset of the models,
namely the
canonical
ones, suffices to decide query entailment.
Our algorithm works on a data structure called
completion forest
. A completion forest is a finite re-
lational structure capturing a set of models of a KB . Roughly speaking, models of are repre-
sented by an initial completion forest
F
K
. Then, by applying
expansion rules
repeatedly, new comple-
tion forests are generated. Since every model of is preserved in some completion forest that results
from the expansion,
K
q
can be decided by considering a set
of sufficiently expanded forests.
From each such an , a single
canonical model
is constructed. Semantically, the finite set of these
canonical models is sufficient for answering all queries
q
of bounded size. Furthermore, we prove that
entailment in the canonical model obtained from can be checked effectively via a syntactic mapping
of the terms in
q
to the nodes in .
Completion Forests
Definition 3.
(Completion Forest) A completion tree
T
for an
f
-SHIF (
D
KB is a tree all of whose
nodes are generated by expansion rules, except for the root node which might correspond to an abstract
individual name in
I
. A completion forest for an
f
-SHIF (
D
KB consists of a set of completion
trees whose root nodes correspond to abstract individual names occurring in the ABox, an equivalent
relation » and an inequivalent relation ¹ among nodes.
The nodes in a completion forest , denoted Nodes( ), can be divided into abstract nodes (de-
noted ANodes( )) and concrete nodes (or data type nodes, denoted CNodes( )). Each abstract node
o
in a completion forest is labeled with a set ( ) = {
〈 ≥ 〉 , where
C su
Î ( ,
n
Î (0,1]. The
concrete nodes
v
can only serve as leaf nodes, each of which is labeled with a set ( ) = { ,
o
C
,
,
n
}
〈 ≥ 〉 ,
where
d su
Î (
D
,
n
Î (0,1]. Similarly, the edges in a completion forests can be divided into abstract
edges and concrete edges. Each abstract edge 〈
v
d
,
n
}
′
〉
′
〉
o o
, is labeled with a set (
〈
o o
,
) = {
〈 ≥ 〉
R
,
,
n
, where
}
R
Î
R
. Each concrete edge 〈
o v
, is labeled with a set (
〉
〈
o v
,
〉
) = { ,
〈 ≥ 〉
T
,
n
, where
T
}
Î
R
.
c
′
〉
′
〉
, then
o
is called an
R
n
If 〈
o o
, is an edge in a completion forest with 〈 ≥ 〉 ∈ 〈
R
,
,
n
(
o o
,
)
³,
-
suc-
³,
-
predecessor
of
o
. Ignoring the inequality and membership degree,
we can also call
o
an
R
-successor of
o
and
o
an
R
-predecessor of
o
.
Ancestor
and
descendant
are
the transitive closure of predecessor and successor, respectively. The union of the successor and prede-
cessor relation is the
neighbor
relation. The
distance
between two nodes
o
,
o
in a completion forest
is the shortest path between them.
cessor
of
o
and
o
is called an
R
n
