Database Reference
In-Depth Information
•
We present a novel tableau-based algorithm for checking query entailment over
f
-SHIF (
D
KBs. We generalize the mapping conditions from a fuzzy query into a completion forest, reducing
the times required for checking mapping in different completion forests.
•
We close the open problem of the complexity for answering fuzzy conjunctive queries in expres-
sive fuzzy DLs by establishing two complexity bounds: for data complexity, we prove a coNP
upper bound, as long as only simple roles occur in the query. Regarding combined complexity, we
prove a co3NExpTime upper bound in the size of the knowledge base and the query.
PRELIMINARIES
Syntax and Semantics of
f
-
SHIF
(D)
Fuzzy DL
f
-SHIF
(D)
allows to reason with fuzzy data types, such as
Young
and
Small
, by relying on
so-called fuzzy concrete domains. We recall that SHIF
(D)
is the basic DL
ALC
(Baader & Nutt,
2003) extended with transitive role axioms ( ), role hierarchy (), inverse roles ( ), functional roles
( ) and concrete domains allowing to deal with data types such as strings and integers. In fuzzy
SHIF
(D)
, however, concrete domains are treated as fuzzy sets. More specially, a fuzzy data type
theory
D
D consists of a data type domain D
D
and a mapping
.
D
that assigns to each data
value an element of D
D
, to each
n
-ary data type predicate
d
an
n
-ary fuzzy relation over D
D
. For ex-
ample, we define
Young
:
D D
.
= (
,
)
® to be a fuzzy data type predicate over the natural numbers denot-
ing the degree of youngness of a person's age. Then,
YoungPerson
[0,1]
=
Person
$
age Young
.
denotes
young persons.
Let
A, R R I, I
, ,
c c
and
M
be countable infinite and pairwise disjoint sets of concept names (de-
noted by
A
), abstract role names (denoted by
R
), concrete role names (denoted by
T
), abstract indi-
vidual names (denoted by
o
), and concrete individual names (denoted by
v
). We assume that the set of
abstract role names
R
can be divided into two disjoint subsets,
R
t
and
R
n
, which stands for the subset
of
transitive role names
and
non-transitive role names
, respectively.
f
-SHIF (
D
abstract roles (or
→ | , where
R
N
Î
R
,
R
-
is called the
inverse role
of
R
. A role inclusion axiom is of the form
R
, with
R
,
S
abstract roles. A role hierarchy (also called
a RBox) is a finite set of role inclusion axioms.
For the sake of brevity and clarity, we use following notations: (
i
) we use an abbreviation
Inv
( )
to denote inverse role of
R
, (
ii
) for a RBox , we define
*
as the reflexive transitive closure of
over
abstract roles for short) are defined as
R
R
R
N
, (
iii
) for a RBox and a role
S
, we define the set
Trans
of transitive roles as {
S
there is a role
R
with
R
∪
{
Inv R
(
)
Inv S
(
) |
R
S
∈
}
º
*
S
and
R
Î
R
or
Inv R
(
)
Î
R
, (
iv
) a role
S
}
t
t
is called simple w.r.t. a RBox if, for each role
R
such that
R
*
S
,
R
Ï Trans
. The subscript
of
*
and
Trans
is dropped if clear from the context.
f
-SHIF
(D)
complex concepts (or simply concepts) are defined by concept names according to
the following abstract syntax:
C
→ ⊥
|
A C
C C
C
¬
C
∀
R C
∃
R C
≤
1
S
≥
2
S
∀
T D T D
∃
,
|
|
|
|
|
.
|
.
|
|
|
.
|
.
1
2
1
2
