Database Reference
In-Depth Information
element
v
in D
D
, such that
T b v
( ,
( )
)
³ ³ and
d
1
0.8
v
³ holds. By constructing a mapping p
o
, p(
with p( ) =
x
y
) =
b
, p( ) =
z
c
, and p(
y
) =
v
, we have I
q
.
c
RELATED WORK
The first conjunctive query algorithm (Calvanese, De Giacomo, & Lenzerini, 1998) over DLs was actu-
ally specified for the purpose of deciding conjunctive query containment for
DLR
reg
. Recently, query
entailment and answering have been extensively studied for tractable DLs, i.e., DLs that have reasoning
problems of at most polynomial complexity. For example, the constructors provided by DL-Lite family
(Calvanese, De Giacomo, Lembo, Lenzerini, & Rosati, 2007) are elaborately chosen such that the basic
reasoning tasks are PTime-complete and query entailment is in LogSpace with respect to data complex-
ity. Moreover, in DL-Lite family, as TBox reasoning can usually be done independently of the ABox,
ABox storage can be transformed into database storage, thus knowledge base users can achieve efficient
queries by means of well-established DBMS query engines. Another tractable DL comes from
EL
with
PTime-complete reasoning complexity. It was shown that union of conjunctive queries (UCQs) entail-
ment in
EL
and in its extensions with role hierarchies is NP-complete regarding the combined complex-
ity (Rosati, 2007b). The data complexity of UCQ entailment in
EL
is PTime-complete (Rosati, 2007a).
Allowing, additionally, role composition in the logic as in
EL
++
, leads to undecidability (Krtzsch, Ru-
dolph, & Hitzler, 2007).
Query answering algorithms for expressive DLs are being tracked with equal intensity. CARIN
system (Levy & Rousset, 1998), the first framework for combining a description logic knowledge base
with rules, provided a decision procedure for conjunctive query entailment in the description logic
ALCNR
, where stands for role conjunction. Decision procedures for more expressive DLs, i.e.,
the whole
SH
family, were presented (Ortiz, Calvanese, & Eiter, 2006; Ortiz, Calvanese, & Eiter, 2008),
and the coNP-complete data complexity for a whole range of sublogics of SHOIQ , as long as only
simple roles in the query, was proved. The algorithms for answering CQs with transitive roles over
SHIQ (Glimm, Lutz, Horrocks, & Sattler, 2008) and
SHOQ
(Glimm, Horrocks, & Sattler, 2007)
KBs are provided and also a coNP upper bound was established.
Following current research developments in crisp DLs, there also have been efforts for answering CQs
over fuzzy DL knowledge bases. In particular, a fuzzy extension of DL-Lite was proposed in (Straccia,
2006), along with an algorithm for answering conjunctive queries over fuzzy DL-Lite KBs. Since the
query language for fuzzy DL-Lite has the same syntax as that of crisp DLs, the technique for efficiently
computing the top-k answers of a conjunctive query was shown. In (Pan, Stamou, Stoilos, Taylor, &
Thomas, 2008), a general framework of the aforementioned query language was proposed, covering all
the existing query languages for fuzzy ontologies as well as some new ones that can be customized by
users. The algorithms for these queries were implemented in the system ONTOSEARCH2 and evalua-
tion showed that these can still be answered in a very efficient way. Clearly, threshold queries give users
more flexibility in that users can specify different thresholds for different atoms. Maillis et al. (Mailis et
al., 2007) proposed a fuzzy extension of CARIN system called fuzzy CARIN, and provided the ability
of answering to union of conjunctive queries.
However, there is still no report for query answering over fuzzy DLs with data types. We tackle this
issue in the next section.
