Database Reference
In-Depth Information
d
+
, written as
M
. We now
make a case study of the numbers of the application of rules for expanding
F
K
into . For each node,
the -rule and the -rule may be used at most O (
c
times, and the ∃
≥
, ∀
≥
, ∀
+
, ∀
+
and ³
³
-rules
may be used at most
O cr
1
Proof.
By Lemma 8, the number of nodes in is at most |
I
| (2 )
cr
(
) times. The number of the application of these rules is at most
O M
(
cr
)
times. The number of the application of ≤
r
-rule is at most
O
(|
I
|)
times. For each node, The number
of the application of -rule is at most
O
(
d
times for
M
nodes.
To sum up, the total number for the application of rules is at most
O Mcr M
d
times, and is at most
O M
|
|)
(
|
|)
(
+
d
times.
|
|)
Theorem 4.
Let be a
f
-SHIF (
D
KB and
q
a fuzzy conjunctive query in which all the roles are
simple, deciding whether
K
q
is in co3NexpTime w.r.t. combined complexity, and is in coNP w.r.t.
data complexity.
Proof.
If
K
q
, there must exists a Îccf
, such that
q
F
does not hold. Due to the exis-
tence of the nondeterministic rules, and by Theorem 3, the construction of can be done in nondeter-
ministic tripe exponential time in the size of ||
q
. By Corollary 1, the number of the nodes in is
,
||
at most triple exponential in the size of ||
q
. For a fuzzy CQ
q
with
k
variables, checking for
a mapping takes
M
k
times, which is tripe exponential in the size of ||
,
||
q
. Hence, deciding
K
q
is in 3NexpTime, and deciding |=
q
is in co3NexpTime. Similarly, the data complexity deciding
|=
q
is in coNP.
,
||
CONCLUSION
Fuzzy Description Logics-based knowledge bases are envisioned to be useful in the Semantic Web.
Existing fuzzy DL reasoners either are not capable of answering complex queries (mainly conjunctive
queries), or only apply to DLs with less expressivity. We thus present an algorithm for answering expres-
sive fuzzy conjunctive queries over the relative expressive DL, namely fuzzy SHIF (
D
. The algorithm
we suggest here can easily be adapted to existing (and future) DL implementations. Future direction
concern applying the proposed technique to more expressive fuzzy query language, e.g. in (Pan et al.,
2008).
REFERENCES
Baader, F., Calvanese, D., McGuinness, D. L., Nardi, D., & Patel-Schneider, P. F. (Eds.). (2003).
The
description logic handbook: Theory, implementation, and applications
. Cambridge University Press.
Baader, F., & Nutt, W. (2003).
Basic description logics
(pp. 43-95).
Bechhofer, S., Van Harmelen, F., Hendler, J., Horrocks, I., McGuinness, D., Patel-Schneider, P., et al.
(2004).
OWL Web ontology language reference
. W3C recommendation.
Bobillo, F., & Straccia, U. (2008). fuzzydl: An expressive fuzzy description logic reasoner.
Proceedings
of the 2008 IEEE International Conference on Fuzzy Systems
, (pp. 923-930).
