Temporal ontologies contain events that are concepts and roles with references to temporal intervals. Therefore, a temporal ontology induces the interval ontology. We consider fuzzy interval ontologies written in a fuzzy Boolean 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 ontology 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.
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:
(
Gerald S. Plesniewicz et al.
(
(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+}.
The inverted relations are marked by asterisks: b* (after), m* (met-by), o* (overlapped-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 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 atomic sentences entering the formulas from O. Let В(О) = U{tr(β) | β ∈ А(О)}. For example, 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 <Y and Y ≤ X belong to В(О) then “X <Y” + “Y ≤ X” = 1; (b) If X =Y, X <Y and Y <X belong to В(О) then “X=Y”+ max{“X <Y”, “Y <X”}=1; (c) If X <Y, Y <Z and X <Z belong to В(О) then “X <Z” ≥ min{“X <Y” ,“Y <Z”}, and the similar constraints which are obtained by replacing signs “<” by signs “≤” or “=”.
We expand the function “...” to А(О) by “A θ B”= min{“V” | V ∈ tr(A θ B)}. Further, we expand “...” to formulas by the usual rules of Zadeh’s fuzzy logic: “~ φ” = 1 –“φ”, “φ /\ ψ” = min{“φ”,“ψ”}, “φ \/ ψ” = max{“φ”,“ψ”} [3].
Let r and s be numbers from [0,1] and φ be a ELA formula. Expressions of the forms φ > 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 consequence. Let E ⊆ EST and σ ∈ EST. We state E |= σ when there is no fuzzy interpretation “...”: 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 ontology 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 variables x1, x2,…, xn whose values are in Ω. A query is an expression of the form ? (x1, x2,…, xm) – ψ[ x1, x2,…, xm], (1.1) 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 expression ?(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 bilateral 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 answers 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 Example 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
formulas р → А 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(
At step 12, the rule T4(
At step 13, the rule T4(
(End of Example 3.)
Fig. 1. Deduction tree for Example 2
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 entering all these tables are formed a complete system for query answering over fact bases for ontologies written in the language ELA. Fragment of Allen’s table of compositions b b* b b Ω
d bdmos b*dfm*o* f b b* s b b*dfm*o* (A– ≥ X) < t -------------(A– ≥ X) < t (A– ≥ X) ≤ t -------------(A– ≥ X) ≤ t (A– ≥ X) < t -------------(A– ≥ X) < t
X ∈{B+, B–}
V ∈ {X ≥ Y, X > Y}) 3
We have defined the fuzzy Boolean extension of Allen’s interval logic and considered 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 tableaux method was applied.