=Paper=
{{Paper
|id=Vol-1687/project3
|storemode=property
|title=Query Answering over Fact Bases for Fuzzy Interval Ontologies
|pdfUrl=https://ceur-ws.org/Vol-1687/proposal3.pdf
|volume=Vol-1687
|authors=Gerald S. Plesniewicz,Vu Nguen Thi Min,Dmitry Masherov
|dblpUrl=https://dblp.org/rec/conf/cla/PlesniewiczMM16
}}
==Query Answering over Fact Bases for Fuzzy Interval Ontologies==
https://ceur-ws.org/Vol-1687/proposal3.pdf
Query Answering over Fact Bases for Fuzzy Interval
Ontologies
Gerald S. Plesniewicz, Vu Nguen Thi Min, Dmitry Masherov
National Research University MPEI
e-mail1: salve777@mail.ru
Abstract. Temporal ontologies contain events that are concepts and roles with
references to temporal intervals. Therefore, a temporal ontology induces the in-
terval ontology. We consider fuzzy interval ontologies written in a fuzzy Bool-
ean extension of Allen’s interval logic. Syntactically, the extended logic ELA is
the set of all Boolean combinations of propositional variables and sentences of
Allen’s interval logic. Semantics of ELA is defined using fuzzy interpretations
of propositional variables and atomic sentences of Allen’s logic. An interval on-
tology in ELA is a finite set ELA sentences (formulas). A fact is an estimate of
a formula i.e. an expression of the form r ≤ φ ≤ s where φ is a ELA formula
and 0 ≤ r ≤ s ≤ 1. A fact base for an interval ontology is a finite set of facts
with formulas from the ontology. We present a method of finding answers to
queries addressed to fact bases for fuzzy interval ontologies. The method uses
analytical tableaux.
Keywords: knowledge representation, ontologies, fuzzy ontologies, temporal
logics, Allen’s interval logic, query answering
1 Introduction
Temporal ontologies contain events that are concepts and roles with references to
temporal intervals. Therefore, a temporal ontology induces the interval ontology.
Consider an example.
Example 1. Suppose, we should define the structure of the concept Agent in some
ontology for a multi-agent system. Then we may write declarations such as
Agent[Name: String, Carry_out: Action(*)],
Action[Name: String, Interval: (Integer,Integer), Procedure: Program].
The terms Agent(Name=rob07) and Agent(Name=rob07).Carry_out.Interval denote
the robot rob07 and the temporal intervals of the actions carrying out by rob07. Let
the robot rob07 is able to carry out the actions a, b and c, i.e.
Agent(Name=rob07).Carry_out = {a, b, c}. These actions spend certain time. Thus,
temporal intervals A, B and C are associated with the actions.
Suppose, there is the following knowledge about the intervals:
(1) If p is true then there is no time point at which both actions a and b are carried
out;
94 Gerald S. Plesniewicz et al.
(2) If q is true then the action b is carried out only when the action c is carried out.
Consider the question:
(3) What Allen’s relations are impossible between the C and A if both conditions
p and q take place?
In Allen’s interval logic (see [1, 2]) with implication, the statements (1) and (2) can be
written as the interval ontology O ={p →A bb*B, q →B edfs C}(see further). The
query (3) is written as ?x – p ∧ q → C –x A.
(End of Example 1.)
In Allen’s interval logic LA, there are 7 basic relations between intervals: e
(equals), b (before), m (meets), o (overlaps), f (finishes), s (starts), d (during). (See
Table 1 for interpretation of these relations, where A– and A+ denote the left and the
right ends of the interval A). Let tr(A θ B) be the set of inequalities characterized
of the basic Allen’s relation θ (see the third column of Table 1). For example,
tr(A f B) = {A– > B–, А+ ≥ В+, B+ ≥ A+}.
Table 1. Basic relations of Allen’s interval logic
Interval
relation Illustration Inequalities for the ends of intervals
AbB |===A===| |===B===| В– > А+
AmB |===A===|=====B=====| А + ≥ В –, В – ≥ А +
AoB |===A===| B– >A–, A+ > В–, B+ >A+
|=====B=====|
AdB |===A===| A– >B–, B+ >A+
|=====B=====|
AsB |===A===| A – ≥ B –, B – ≥ A –, B + > A +
|=====B=====|
AfB |===A===| A – > B –, А + ≥ В +, B + ≥ A +
|=====B=====|
AeB |=====A=====| A – ≥ B –, B – ≥ A –, А + ≥ В +, А + ≥ В +
|=====B=====|
The inverted relations are marked by asterisks: b* (after), m* (met-by), o* (over-
lapped-by), f* (finished-by), s* (started-by), d* (contains); so, A α*B ó B α A.
Let Ω0 = {e, b, m, o, f, s, d} and Ω = Ω0 U { b*, m*, o*, f*, s*, d*} = {e, b, m, o,
f, s, d, b*, m*, o*, f*, s*, d*}.
A sentence (formula) of LA is an expression of the form A ω B where ω is any
subset of the set Ω and A, B are interval variables. If ω = {α}, then instead of A{α}B
we write simply A α B. If ω ={α1, α2,…, αk} then we write A α1α2…αk B instead of
A{α1, α2,…, αk}B. By definition, the formula A α1α2…αk B is true if it is true at least
Query Answering over Fact Bases for Fuzzy Interval Ontologies 95
one formula A αi B (1 ≤ i ≤ k). The sentences of the form A α B with α ∈ Ω0 are called
atomic.
The fuzzy Boolean extension ELA Allen’s interval logic is defined as follows.
SYNTAX of ELA:
• propositional variables are ELA formulas;
• every LA formula belongs to ELA, i.e. LA ⊆ ELA;
• if φ and ψ are ELA formulas then ~φ, φ /\ ψ and φ \/ ψ are also ELA formulas,
and
φ → ψ is ELA formula considered as shorthand for ~φ \/ ψ.
An (interval) ontology is a finite set of ELA formulas. Let P(O) be the set of all
propositional variables entering the formulas from O, and A(O) be the set of all atom-
ic sentences entering the formulas from O. Let В(О) = U{tr(β) | β ∈ А(О)}. For ex-
ample, if О = {A o B → (B mf C) /\ p, q → A s C, C o*A} then Р(О) = {p, q} and
А(О) = {B m C, B f C, A s C, A o C}, and B(O) = {B+ ≥ C–, C– ≥ B+, B– > C–, B+ ≥
C+, C+ ≥ B+, A– ≥ C–, C– ≥ A–, C+ > A+, C– >A–, A+ > C–, C+ >A+ }.
SEMANTICS of ELA is defined using fuzzy interpretations.
A fuzzy interpretation of an ontology O is any function “...” from Р(О) ∪ B(О) to
[0,1] = {x | 0 ≤ x ≤ 1} with the following constraints:
(a) If X r, φ ≥ r, φ < r and φ ≤ r are called estimates of the formula φ, and
expressions of the form r ≤ φ ≤ s (where 0 ≤ r ≤ s ≤ 1) are called bilateral estimates
of φ. The estimates are interpreted naturally. Let “...” be any interpretation of the
ontology {φ}. Then “φ > r” ódf “φ” > r, “φ ≥ r” ódf “φ” ≥ r, “φ < r” ódf “φ” < r,
“φ ≤ r” ódf “φ” ≤ r, “r ≤ φ ≤ s” ódf r ≤ “φ” ≤ s.
The set EST of all estimates for ELA formulas can be considered as a crisp logic
with fuzzy interpretations. As every logic, EST has the relation ‘|=” of logical conse-
quence. Let E ⊆ EST and σ ∈ EST. We state E |= σ when there is no fuzzy interpreta-
tion “...”: E → [0,1] such that all estimates from E are true but the estimate σ is false.
We consider estimates with the relation “≤” as facts. For any interval ontol-
ogy O = {φ1, φ2,…, φn} (φi ∈ ELA), any set Fb = {r1 ≤ φ1 ≤ s1, r2 ≤ φ2 ≤ s2,…, rn ≤ φn ≤
sn} (0 ≤ ri, si ≤ 1) of bilateral estimates is called a fact base for the ontology O.
We can query a fact base and get the appropriate answers. Let ψ = ψ[x1, x2,…, xn]
be an ELA formula in which some of its Allen’s connectives are replaced with varia-
bles x1, x2,…, xn whose values are in Ω. A query is an expression of the form
? (x1, x2,…, x m) – ψ[ x 1, x2,…, xm],
(1.1)
96 Gerald S. Plesniewicz et al.
where ψ = ψ[x1, x2,…, xn] is an ELA formula in which some of its Allen’s connectives
are replaced with variables x1, x2,…, xn whose values are in Ω. (For example, the ex-
pression ?(x1, x2) – (p \/ A bs B) → B x1od C /\ ~A x2 D is a query.)
The answer to query (1.1), addressed to the fact base Kb, is the set of all tuples
(g, h; α1, α2,…, αm) with αi ∈ Ω and g, h ∈ [0,1] such that Kb |= g ≤ ψ[α1, α2,…, αm] ≤
h with maximal g and minimal h. So, we have g = max{r | Kb |= r ≤ ψ[α1, α2,…,
αm]}and g = min{s | Kb |= ψ[α1, α2,…, αm] ≤ s}.
Remarks. 1) It is easy to prove that the maximum and the minimum exist. 2) Since
“φ ≤ r” ó “φ” ≤ r ó 1–“φ” ≥ 1 – r ó “~ φ” ≥ r ó “~ φ ≥ 1– r” and “r ≤ φ ≤ s” ó r
≤ “φ” ≤ s ó r ≤ “φ”, “φ” ≤ s ó “φ ≥ r”, “~ φ ≥ 1– s”, then any fact base with bilat-
eral estimates is equivalent to a fact base with lower estimates i.e. of the form φi ≥ ri.
We will consider further only fact bases with lower estimates.
Example 3. Consider the ontology O from Example 1 as a fuzzy ontology with the
fact base Fb = {р → А bb*В ≥ 0.6, q →В edfs С ≥ 0.9}. In the next section we show
that the set {(0.6, d), (0.6, e), (0.6, f), {(0.6, s)} is the answer to the query ?x – p ∧ q
→ ~ C x A.
(End of Example 3.)
Generally, we can associate with any fuzzy logic the crisp logic of estimates whose
sentences are expressions of the form r ≤ φ ≤ s where φ are formulas of the fuzzy
logic and 0 ≤ r ≤ s ≤ 1. Umberto Straccia have studied a fuzzy description logic
which are the logics of estimates for description logics [4, 5]. The logic of estimates
for propositional logic was considered in [6] where the method of query answering
over fact bases was described.
In the paper, we present the method (based on analytical tableaux [6]) for finding
the answers to queries addressed a fact base for an interval ontology.
2 Finding Answers to Queries Addressed to a Fact Base
The method of analytical tableaux can be applied to the problem of finding an-
swers to queries addressed to fact bases for fuzzy interval ontologies. We show, by
example, how to do this.
Example 3. Consider again the interval ontology O and the its fact base from Ex-
ample 2: Fb = {р → А bb*В ≥ 0.6, q →В edfs С ≥ 0.9}. In Fig.1, it is shown the
deduction tree constructed step by step from Fb and the estimate p ∧ q → ~ C x A < g
which is corresponded to the body of the query ?x – p ∧ q → ~ C x A.
Constructing the deduction tree, we start with the initial branch containing the for-
mulas р → А bb*В ≥ 0.6, q →В edfs С ≥ 0.9. At the first step we apply the rule from
Table 2 in the fourth row and second column (denote by T2(4,2) this rule) to the for-
mula р → А bb*В ≥ 0.6 and we put the label “[1]” on the right of the formula. As a
result of the application of the rule T2(4,2), the “fork” with the estimates p ≤ 0.4 and
А bb*В ≥ 0.6 are added to the initial branch and the label “1:” is put on the left of
each of the estimates. At the step 2, the rule T2(4,2) is applied to q →В edfs С ≥ 0.9.
As a result, the “fork” with the estimates q ≤ 0.1 and В edfs С ≥ 0.9 are added to each
of two current branches. At the step 8, the rule T8(1,2) is applied to the estimates q ≤
Query Answering over Fact Bases for Fuzzy Interval Ontologies 97
0.1 and q >1– g. As a result, we get the inequality g ≤ 0.9 that means the estimates q ≤
0.1 and q ≥ 1– g are inconsistent (and therefore, the first branch is inconsistent) if
and if g ≤ 0.9. At step 9, the rule T8(1,2) is applied to the estimates p ≤ 0.4 and p >1–
g. As a result, we obtain that the second branch is inconsistent if and only if g ≤ 0.6.
At step 10, the rule T8(1,2) is applied to the estimates q ≤ 0.1 and q ≥ 1– g. As a re-
sult, we obtain that the third branch is inconsistent if and only if g ≤ 0.9. Thus, the
first, second and third branch are inconsistent if and only if g ≤ min{0.9, 0.6, 0.9} =
0.6.
At step 12, the rule T4(1,1) is applied to the estimates В edfs С ≥ 0.9 and В edfs С
≥ 0.9, and as result, the estimate А bb*dfmm*oo*s C ≥ 0.6 is obtained. Indeed, using
Table 4 which is a fragment of the Allen’s table of compositions (see [2]), we have
bb* ᵒ edfs = b ᵒ e U b ᵒ d U b ᵒ f U b ᵒ s U b* ᵒ e U b* ᵒd U b* ᵒ f U b* ᵒ s =
b U bdmos U bdmos U b U b* U b*dfm*o* U b* U b*dfm*o* =
bb*dfmm*oo*s.
At step 13, the rule T4(1,3) is applied to the estimate А bb*dfmm*oo*s C ≥ 0.6,
and we have C b*bd*f*m*mo*os*A ≥ 0.6. At step 14, the substitution {x := defs, g :=
0.6} is applied to the estimate C –x A < g, and we have C b*bd*f*m*mo*os* A <
0.6. Finally, at step15 we obtain the contradiction: C b*bd*f*m*mo*os* A ≥ 0.6 and
C b*bd*f*m*mo*os* A < 0.6. From the substitution we obtain the following answer
to the query ?x – p ∧ q → ~ C x A: {(0.6, d), (0.6, e), (0.6, f), {(0.6, s)}.
(End of Example 3.)
p∧q→~CxA1– g [4] 3: p ∧ q >1– g [5] 3: p ∧ q >1– g [6] 3: p ∧ q >1– g [7]
3: ~ C x A < g 3: ~ C x A < g 3: ~ C x A < g 3: ~ C x A < g [11]
4: p >1– g 5: p >1– g [9] 6: p >1– g 7: p >1– g
4: q >1– g [8] 5: q >1– g 6: q >1– g [10] 7: q < 1– g
8: g ≤ 0.9 X 9: g ≤ 0.6 X 10: g ≤ 0.9 X 11: C –x A < g
{x := defs, g := 0.6} [14]
12: А bb*dfmm*oo*s C ≥ 0.6 [13]
13: C b*bd*f*m*mo*os* A ≥ 0.6 [15]
14: C b*bd*f*m*mo*os* A < 0.6 [15]
15: X
Fig. 1. Deduction tree for Example 2
98 Gerald S. Plesniewicz et al.
Remark. In Example 2, the Tables 2, 3 and 4 were used to construct the deduction
tree in Fig. 1. Generally, the Tables 5, 6, 7 may be needed. The inference rules enter-
ing all these tables are formed a complete system for query answering over fact bases
for ontologies written in the language ELA.
Table 2. Inference rules for propositional connectives
~φ>t ~φ≥t ~φ 1– t φ ≥ 1– t
φ /\ ψ > t φ /\ ψ ≥ t φ /\ ψ < t φ /\ ψ ≤ t
___________ ___________ _____________ _____________
φ>t φ>t φt ψ>t
φ \/ ψ > t φ \/ ψ ≥ t φ \/ ψ < t φ \/ ψ ≤ t
______________ ______________ ___________ __________
φ>t|ψ>t φ≥t|ψ≥t φ t φ→ψ ≥ t φ→ψ < t φ→ψ ≤ t
_______________ ------------------ ----------- -----------
φ <1– t | ψ > φ ≤ 1– t | ψ ≥ t φ >1– t φ ≥ 1– t
t ψ t (X ≥ A+) ≤ t (X ≥ A+) < t
______________ _______________ ______________ ______________
– – –
(X >A ) ≥ (X > A ) > (X >A ) ≤ (X >A–) <
t t t t
Query Answering over Fact Bases for Fuzzy Interval Ontologies 99
(A– ≥ X) ≥ t (A– ≥ X) < t (A– ≥ X) ≤ t (A– ≥ X) < t
-------------- -------------- -------------- --------------
(A– ≥ X) ≥ t (A– ≥ X) < t (A– ≥ X) ≤ t (A– ≥ X) < t
X ∈{B+, B–}
Table 6. Inference rules for Allen’s connectives
АbВ>t АbВ≥t АbВ t – +
(В ≥ A ) ≥ t – +
(В ≥ A ) < t (В– ≥ A+) < t
АmВ>t АmВ≥t АmВ t (A ≥ В ) ≥ t (A ≥ В ) < t | (A ≥ В ) t |
(В– ≥ A+) > t (В– ≥ A+) > t (В– ≥ A+) < t (В– ≥ A+) < t
АoВ>t АoВ≥t АoВ A ) > t (B > A ) ≥ t (B > A ) < t | (B > A ) ≤ t |
(A+ > B–) > t (A+ > B–) ≥ t (A+ > B–) < t | (A+ > B–) ≤ t |
(A+ < B+) > t (A+ < B+) ≥ t (A+ < B+) < t (A+ < B+) ≤ t
АfВ>t АfВ≥t АfВ B ) > t (A > B ) ≥ t (A > B ) < t | (A > B ) ≤ t |
(A+ ≥ B+) > t (A+ ≥ B+) ≥ t (A+ ≥ B+) < t | (A+ ≥ B+) ≤ t |
(A+ ≥ B+) > t (B+ ≥ A+) > t (A+ ≥ B+) < t (A+ ≥ B+) < t
АsВ>t АsВ≥t АsВ B ) > t (A > B ) ≥ t (A ≥ B ) < t | (A ≥B ) ≤ t |
(B+ ≥ A+) > t (B+ ≥ A+) ≥ t (B+ ≥ A+) < t | (B+ ≥ A+) ≤ t |
(B+ > A+) > t (B+ > A+) > t (B+ > A+) < t (B+ > A+) ≤ t
АdВ>t АdВ≥t АdВ B ) > t (A > B ) ≥ t (A > B ) < t | (A > B ) ≤ t |
(B+< A+) > t (B+< A+) ≥ t (B+< A+) < t (B+< A+) ≤ t
АeВ>t АeВ>t АeВ t (B ≥ A ) ≥ t (B ≥ A ) < t | (B ≥ A ) ≤ t |
(A– ≥ B–) > t (A– ≥ B–) ≥ t (A– ≥ B–) < t | (A– ≥ B–) ≤ t |
(B+ ≥ A+) > t (B+ ≥ A+) ≥ t (B+ ≥ A+) < t | (B+ ≥ A+) ≤ t |
(A+ ≥ B+) > t (A+ ≥ B+) ≥ t (A+ ≥ B+) < t (A+ ≥ B+) ≤ t
100 Gerald S. Plesniewicz et al.
Table 7. Inference rules for contrary pairs (where V ∈ {X ≥ Y, X > Y})
px p≤ t (V) < x (V) ≥ t (V) > x (V) ≤ t
_________________ ________________ ___________________ ___________________
x≤ t x≥ t x≤ t x≥ t
V ∈ {X ≥ Y, X > Y})
3 Conclusion
We have defined the fuzzy Boolean extension of Allen’s interval logic and consid-
ered ontologies written in the extension. Fact bases for such ontologies consist of
bilateral estimates for formulas from the ontologies. We have considered the problem
of query answering over fact bases. For decision of this problem the analytical tab-
leaux method was applied.
Acknowledgement
This work was supported by Russian Foundation for Basic Research (project 14-
07-0387) and Ministry of Education and Science of Kazakhstan (project 0115 RK
00532).
References
1. Allen J.A.: Maintaining Knowledge about Temporal Intervals. Communications of the
ACM, 20 (11), 832-843 (1983).
2. Allen J.W., Ferguson G.: Actions and Events in Interval Temporal Logic. Journal of Logic
and Computation, 4 (5), 531-579 (1994).
3. Perfilieva I., Mockor I.: Mathematical Principles of Fuzzy Logic, Kluwer Academic Pub-
lishers, Dordrecht, 1999.
4. Straccia U.: A fuzzy Description Logic: Proceedings of the National Conference on Artifi-
cial Intelligence, 594-599 (1988).
5. Straccia U.: Reasoning within Fuzzy Description Logics. Journal of Artificial Intelligence
Research Proceedings of the National Conference on Artificial Intelligence, 14 (1), 147-
176 (2001).
6. D’Aggostino, M., Gabbay D., Hahnle R., Possega J. (eds.): Handbook of Tableaux
Methods, Kluwer Academic Publishers, Dordrecht, 1999.
7. Plesniewicz G.S.: Query Answering over Fact Bases in Fuzzy Propositional Logic. 2013
IFSA Congress and NAFIPS Annual Meeting, Edmonton, Canada, June 24-28, 1252-1255
(2013).