Description logic is widely used to describe and represent knowledge in the Semantic Web. It is a modern and powerful mechanism that provides the possibility of extracting knowledge from already existing ones. Thanks to this, conceptual modeling of subject areas has become one of the fields of application of description logic. Conceptual modeling is used to create databases and knowledge bases. A key issue in of the subject area modeling is the ability to monitor the dynamics of changes in the state of the subject area over time. It is necessary to describe not only the current actual state of the database/knowledgebase but also timevarying states. Temporal description logic is used to solve this problem. It has the same set of algorithmic problems that are presented in traditional description logic, but there are additional issues related to the description of knowledge in time. This refers to the form of time (continuous or discrete), time structure (moments of time, intervals, chains of intervals), time linearity (linear or branched), domain (present, past, future), the concept of "now", etc. An urgent task today is to develop approach of such interpretation of temporal description logic that may be supported by databases. The paper presents an algorithm of tabular interpretation of the temporal description logic LTLALC. Only the future tense is considered. The algorithm contains tabular notations of the following components of the LTLALC: concepts, concept constructors, roles, role constructors, TBox and ABox. Numerous examples are used to illustrate the application of the algorithm.
Description logics (DL) are a family of knowledge representation formalisms. They have different application areas, including semantic web ontologies. Particularly, OWL and OWL 2 of the W3C are grounded on the corresponding DL. Conceptual domain modeling problem that considers the use of withdrawal mechanisms became one of the DL application areas. Specially, it refers to the database and data knowledge issues. For example, extended ER-modeling language and extended UML class diagram were described with the help of DL. This allowed to use DL reasoners to check the software descriptions consistency (integrity) and perform influence of new implicitly specified knowledge.
Tracking the dynamics of software state changes over time is the key problem during the software conceptual modeling. That is the situation, when software conceptual informational model and the correspondence database track both the current state and all the prehistory. Such a temporal database should both allow an ability to fix a lot of states in the past (and probably in the future) and give an opportunity to operate these sets of states with their temporal integrity constraints descriptions. To satisfy these needs, a big number of publications on the temporal DL (TDL) theme have been appeared the last several years.
For example, such TDLs were proposed and discovered in modern literature: ITL
temporal logic) [
2022 Copyright for this paper by its authors.
(Timestamp temporal logic) [
This paper is dedicated to the table interpretation of the temporal description logic LTLALC. A survey of the LTL temporal description logic is also given. Publication includes the designation of the database that supports the interpretation of LTL and a set of temporal operations in such a database. The results are presented in a table form.
To define temporal interpretation of any DL there are three main questions: 1. What DL will be used? 2. What TDL will be used? 3. What interpretation of time is chosen?
According to the first question, there is a whole DL family characterized by the composition of elements (individuals, concepts, roles) and a set of constructors and axioms defined on these elements. About the second question, a choice of the TDL depends on the goals of the research. Third question can be answered according to the set of aspects: • continuous and discrete time, • linear and branching time, • present, past, future, • definition of “now”, • time structure (points of time, intervals, chains of intervals), • ways to measure time.
As for this research, the following variants were chosen: 4. Linear discrete non-branching time, represented as an integer time axis with a linear ordering specified on it. (N<). Only the future time is considered. 5. LTL (Linear time temporal logic).
6. ALC (Attributive Language with Complements).
In this research the focus is made on the issues that related to informational models. The list of issues looks like below: syntax and semantics of the language, data model (data structure, operations, integrity constraints) and query language.
The aim of the present work is to show the algorithm for application the temporal logic LTL to the DL ALC. Section 2 is dedicated to some preliminaries that touch a brief survey of DL ALC and LTL basics. The rules of the DL temporal interpretation presented in Section 3. The temporal DL LTLALC interpretation (including concepts, roles, Tbox, Abox) can be found in Section 4. Section 5 is dedicated to the main conclusions and future research.
LTL (Linear time temporal logic) is the logic that considers causal relationships in terms of time. The concepts of LTL are formed using the concept constructors of DL ALC enriched with the temporal constructors. This logic is used to describe the sequence of events and their relationship over time.
There are such temporal operators in the LTL logic: ◊ (◊φ) – existence in some moment of time in future (φ) – global existence in some moment of time (forever) (φ) – existence in the next moment of time in future (φ ψ) – until. φ exists until ψ in the current moment of time or in the future (φ ψ) – release. ψ has to be true until and including the point where φ first becomes true.
Every temporal operator can be written with the help of operators “Until” ( ) and “Next” (). For example, existence and global existence operators can be written like below: ◊φ ≡ ⊤ φ φ ≡ ¬◊¬φ ≡ ⊥ φ
There are many ways to use standard temporal logic operators in DL. The following way is chosen in this paper. Temporal operators are used as additional concept constructors that allows to describe temporal behavior of individuals which belong to concepts. In addition, temporal operators can be applied to the roles, TBoxes, and ABoxes. All these options are united by a single notion of temporal DL interpretation.
DL temporal interpretation = (∆, . ) consists of non-empty domain ∆ and . – interpretation function, which maps: • each individual name a ∊ NI into element a ∊ ∆; • each concept name А ∊ NC into subset А ⊆ ℕ × ∆; • each role name R ∊ NR into subset R ⊆ ℕ × ∆ × ∆.
Here time is presented with natural numbers ℕ. On these numbers the order is given < (ℕ, <). For example, (n, d) ∊ А means that individual d in the interpretation is an element of A at time point n. 2 In the paper version of the article, red cells are represented in black.
D D o o m m a a i i n n D D o o m m a a i i n n
o o
Temporal concept “Department staff” (Concept C). Table representation of the temporal concept “Department staff” (Concept C) is shown on Figure 3.
Domain
Temporal concept “Articles publication by department staff” (Concept С ⊓ D). Table representation of the temporal concept “Articles publication by department staff” (Concept С ⊓ D) is shown on Figure 5.
In previous section we described the meaning of the temporal DL interpretation and showed how the concept constructors are used. Concept constructors are operations over the columns of the tables (in examples, given in this paper). In turn, to use LTL it is requires include to the DL temporal operators (constructors). They are operations over the rows of the table.
The syntax for including temporal statements in DL is very simple. If C and D are concepts (atomic or arbitrary) then C, ◊C, C, С D и С D are also concepts. These operators have the following semantics: (C) = {(n, d) | (n+1, d) ∊ C } – Next (◊C) = {(n, d) | ∃m ≥ n (m, d) ∊ C } – Exist (C) = {(n, d) | ∀m ≥ n (m, d) ∊ C } – Always (С D) = {(n, d) | ∃m ≥ n ((m, d) ∊ D ⋀ (k, d) ∊ C for n ≤ k < m)} – Until (С D) = (¬ (¬C ¬D)) – Release Let us explain the essence of these operators with examples.
C means that “in the next moment of time C will take place”. The following Figure 7 shows five examples where a pair of rows represent the separate example. The first row is the meaning of C, and the second one is the meaning of C. As can be seen from the examples, the operator means shifting the red cells C to the left.
C C C C C C C C C C
The following two figures show the temporal meanings of the concepts C (Figure 8) and ◊C (figure 9). The action of the operator ◊ can be described by the following procedure: • for each individual (row) the first red cell from the right side is found and all subsequent cells, up to the first, are converted to red; • if there is no such cell, then the entire row remains white.
С (◊C) = {(n, d) | ∃m ≥ n (m, d) ∊ C }
The following two figures show the temporal meanings of the concepts C (Figure 10) and C (Figure 11). The action of the operator can be described by the following procedure: • for each individual (row) the first white cell from the right side is found and all subsequent cells, up to the first, are converted to white; • if there is no such cell, then the entire row remains red.
С (C) = {(n, d) | ∀m ≥ n (m, d) ∊ C } As can be seen from these examples, the operators and ◊ are dual, that is: ¬С ≡ ◊¬С С ≡ ¬◊¬С ¬◊С ≡ ¬С ◊С ≡ ¬¬С
The following Figure 12 shows an example of the operator. The result of the operator's action is those red cells C that are obtained by executing the following procedure. For each continuous range of red cells of C: • within this range the rightmost red cell of D is found. The range of C is cut from the right side by the rightmost red cell of D; • if there is no red cell of D within the range of red cells of C, then this range is not included into the result of .
In other words, sometime in the future D will be true, and until then C will be true.
(С D) = {(n, d) | ∃m ≥ n ((m, d) ∊ D ⋀ (k, d) ∊ C for n ≤ k < m)} С
D С D
Role R is a binary relation. The first members (from the left side) of the role will be called "predecessors" (R-predecessors) in this paper. The second members (from the right side) of the role will be called "followers" (R-followers). In the general case, a role is a binary relation of the m:n type. That means many R-successors can correspond to each R-predecessor and vice versa. Concept constructor ∃R.C build a concept from the role (R) and concept (C) in the following way. The result of the operation is such a set of R-predecessors for which at least one R-follower belongs to the concept C. In turn, the constructor ∀R.C defines such a set of R-predecessors, in which all Rsuccessors belong to the concept C.
These constructors are dual. That means: ∀R.C ≡ ¬∃R.¬C, ∃R.C ≡ ¬∀R.¬C
Figure 14 illustrates the essence of these constructors. The following image illustrates the meaning of the temporal role R. X-axis means role followers; Y-axis means role predecessors. Red cells of the table mean which R-predecessor and which R-follower are in the R relation.
∃R.С – employees, that participate at least in one NASU project
Domain Projects
The temporal interpretation of the constructor ∃R.C is as follows: (∃R.С) = {(n, d) ∊ ∆ | ∃(n, c) ∊ C ⋀ (n, d, c) ∊ R } 4.2.
In terms of temporal interpretation and application of temporal operators role and concept have similar meaning. Temporal interpretation for concepts defines with the help of individuals. Temporal interpretation for roles defines with the help of pair of individuals. Formal interpretation of the role temporal interpretation:
R ⊆ ℕ × ∆ × ∆
Here is an example. The subject area is the same (participation of department staff in projects). Role is participation of employees in projects. Domain of the role is the following set of pairs: Smith, project1 Smith, project2 Cruz, project1 Cruz, project2 Robbins, project1 Robbins, project2
The temporal interpretation of the role looks like this (fig.16):
Role constructors are absent in the DL ALC. Traditional temporal operators can be applied to the roles in TLTALC. Semantics is the following: (R) = {(n, d, d’) | (n+1, d, d’) ∊ R } (◊R) = {(n, d, d’) | ∃m ≥ n (m, d, d’) ∊ R } (R) = {(n, d) | ∀m ≥ n (m, d, d’) ∊ R } (R S) = {(n, d, d’) | ∃m ≥ n ((m, d, d’) ∊ S ⋀ (k, d, d’) ∊ R for n ≤ k < m)} Figure 17–20 shows how to use these operators over the roles.
Smith, project1
Development over time of concepts and roles in TDL was shown in previous sections. But there are such temporal statements that can’t be described with the help of temporal concepts and roles. They require terminological axiom (concept inclusion) usage. For example, fixed concept means, that concept doesn’t change in time. It keeps the set of its individuals regardless of time. In other words, the fixed concept will be interpreted as a row with all the red cells or a row with all the white cells. The fixed concept can be represented with the following concept inclusion: С ⊑ C, ¬С ⊑ ¬C
TTBox definition requires to define TTBox formulas, which involve the use of temporal operators. There are two situations: • temporal operators are applied only to the terminological axiom in general, but aren`t applied to their concepts. This situation is called temporal ALC TBox (ALC TBox). • temporal operators are applied both to the terminological axiom and to their concepts (except roles). This situation is called temporal LTLALC TBox (LTL TBox).
С ⊑ D, ¬φ, φ ⋀ ψ, φ, φ ψ where: C and D – atomic concepts with temporal interpretation φ and ψ – temporal TBox
Semantics of these formulas defines as follows: , n ⊨ С ⊑ D ⇔ {d | (n, d) ∈ С } ⊆ {d | (n,d) ∈ D } , n ⊨ ¬ φ ⇔ , n ⊭ φ , n ⊨ φ ∧ ψ ⇔ , n ⊨ φ and , n ⊨ ψ , n ⊨ φ ⇔ , n+1 ⊨ φ , n ⊨ φ ψ ⇔ ∃m ≥ n { , m ⊨ ψ and ∀n≤ k< m , k ⊨ φ}
The record , n ⊨ φ means: φ is true in the n moment of time in interpretation . Definition if the terminological axiom is true or false depends on each moment of time (locally). It is not a general definition (globally). Here are graphical examples of temporal ALC TBox and the result of temporal axioms. Figures 21–23 demonstrate temporal concepts “Institute staff” (C), “Department staff” (D) and “Project staff” (E).
Here are examples of the result of the different terminological axioms. Result contains its truth values at the corresponding time. In these examples result is shown as a concept, that contains single individual, that belongs to this concept in the corresponding moment of time, when the terminological axiom is true.
1. Axiom С ⊑ D is true for all the moments of time. It means that all the department staff employees are institute employees.
С ⊑ D Time 2. Axiom D ⊑ С is true for 1,5,8,9 moments of time. So, department will include all the institute staff on that moments of time.
D ⊑ С Time
1 2 3 4 5 6 7 8 9 3. Axiom E ⊑ D is true for 1–7 moments of time. So, only institute staff will work on the project on that moment of time.
E ⊑ D Time
1 2 3 4 5 6 7 8 9 4. Axiom D ⊑ E is true for 1, 8, 9 moments of time. In the moment 1 axiom E ⊑ D is true. So, at this moment only institute employees will work on the project and no one else. As for 8 and 9 moments of time, all the institute staff and someone else will work on the project.
D ⊑ E Time
1 2 3 4 5 6 7 8 9 5. Axiom C ⊑ E is true for 1, 2, 3, 5, 7, 8, 9 moments of time. So, only department staff will work on the project at these moments of time.
С ⊑ E Time
1 2 3 4 5 6 7 8 9 6. Axiom Е ⊑ С is true for 1, 4, 5, 7 moments of time. In the moments of time 1, 5, 7 С ⊑ E is true. So, at these moments of time only department staff will work on the project and no one else. At the 4th moment of time only department employees, but not all of them will work on the project.
Е ⊑ С
7. Axiom E ⊑ D ∧ D ⊑ E is true for 1 moment of time. In this moment of time all the institute, but no one else will work on the project.
E ⊑ D ∧ D ⊑ E Time
1 2 3 4 5 6 7 8 9 8. Axiom С ⊑ Е ∧ E ⊑ D is true for the 1–7 moments of time. So, at these moments of time only employees that are both department employees and institute employees will work on the project.
С ⊑ Е ∧ E ⊑ D
1 2 3 4 5 6 7 8 9
Expressive possibilities obtained when the temporal operators are applied to concepts are
incomparable (mismatched) in comparison when temporal operators are applied to the terminological
axioms. Here is an example in LTLALC TBox (next two examples are taken from [
It say that the extension of the concept "independent_country" cannot decrease, but this cannot be expressed by a temporal ALC TBox. On the other hand, the assertion that eventually all European countries will be EU members forever can be expressed by the temporal ALC TBox: ◊(european_country ⊑ member_EU) But it is not expressible in the non-temporal LTLALC TBox.
If temporal operators are applied only to the concepts and terminological axioms. interaction between TL and DL components in TDL is severely limited. In its turn it can be expressed quite developed types of relationships in the temporal LTLALC TBox. For example:
¬(⊤ ⊑ А) ⇔ ¬(⊤ ⊑ А) 4.4.
To define temporal ABox two options should be considered: • ABox that has temporal interpretation. It is called non-temporal ABox. • ABox that has temporal interpretation and temporal operators. It is called temporal ABox.
Usual ABox contains the following types of predicates: C(a) and R(A, b). There are no constructors for them as for concepts. As regards to their temporal interpretation, its semantics defines as follows: , n ⊨ С(а) ⇔ (n, a ) ∈ С , n ⊨ R(a, b) ⇔ (n, a , b ) ∈ R
Note that the truth value of ABox is determined for each point of time (locally), and not in general (globally).
The temporal ABox assumes the use of the same temporal operators as TBox: С(а), R(a,b), ¬φ, φ ⋀ ψ, φ, φ ψ where: • C(A) and R(a, b) – atomic statements ABox with temporal interpretation • φ and ψ – temporal ABox Semantics of these formulas defines as follows: , n ⊨ ¬φ ⇔ ,n ⊭ φ , n ⊨ φ ∧ ψ ⇔ ,n ⊨ φ and ,n ⊨ ψ , n ⊨ φ ⇔ , n+1 ⊨ φ , n ⊨ φ ψ ⇔ ∃m ≥ n { ,m ⊨ ψ and ∀n≤ k< m ,k ⊨ φ} Here are several examples: • C(Smith) – becomes true in the moments 1, 7, 8. • C(Cruz) – becomes true in the moments 1, 4, 5. • E(Smith) – becomes true in the moments 1, 2, 7. • E(Robbins) – becomes true in the moments 2, 3, 4, 8, 9. • C(Smith) ∧ C(Cruz) – becomes true in the moment 1. This is the moment when these two employees work at the same time. • C(Smith) ∧ E(Cruz) – becomes true in the moment 8. This is the moment when Smith was a department employee and Cruz worked on the project. • C(Smith) ∧ E(Smith) – becomes true in the moment 1 and 7. These are moments, when Smith was a department employee and worked on the project. • C(Smith) ∧ ¬E(Smith) – becomes true in the moment 8. These are moments when Smith was a department employee and didn’t work on the project. • ◊С(Smith) – becomes true in the moment 1–5. • E(Robbins) – becomes true in the moments 8, 9.
By using numerous examples, the paper briefly describes the possibilities of applying the LTL logic to the description logic ALC. There are following issues for the future research: • applying DL to the temporal logic CTL; • extension of the DL family logic to which temporality is applied; • temporal query languages syntax and semantics.