Ontology-based data access (OBDA) assumes that data in a database are mediated with a conceptual layer, available for clients and hiding data storage details. Ontologies are good candidates for such a conceptual layer presentation, whereas databases are good for huge data storage. One of the interesting applications of OBDA is checking a finite set of constraints defined in some language against a temporally-ordered sequence of ABoxes sharing one TBox, where each constraint is considered as a conjunctive query. Presented is one algorithm of conjunctive query answering for such a language, proved are its termination, soundness and completeness.
Ontology-based data access (OBDA) [
The benefits from combination of databases and knowledge bases are as follows:
At the same time, employing such an approach is rather challenging due to significant differences between relational database systems and ontology languages, based on Description Logics, such as OWL. At first, relational databases adopt a closed-world semantics, i.e. all facts that are not explicitly stated to be true are assumed to be false. In contrast, OWL is based on an open world semantics which does not requre one to fix the truth value of every fact and is more similar to an incomplete database. Second, relational databases are unaware of the intensional part of a knowledge base (called a TBox).
Research has been done so far in the OBDA field considers only one ABox stored in
a data source, that is an actual set of assertions on individuals and their pairs. However,
real applications show that ABox is changing over time. The examples of such dynamic
systems can be easily found in practice: environmental conditions, air traffic load,
computer system load and performance, health control for the people suffering from serious
diseases. Therefore, in some applications of situation awareness [
The main results of the paper are: – for the point-based linear finite time structure elaborated is the language of unions of temporal conjunctive queries, which allows to evaluate atemporal unions of conjunctive queries at different time points; – proposed is an algorithm of answering a union of temporal conjunctive queries, which harnesses set-theoretic operations on atomic queries answer sets. Proved are its termination, soundness and completeness; The paper is organized as follows: in the next section a language of unions of temporal conjunctive queries is introduced and the definitions of main reasoning tasks available for such a query language are presented. In the section 3 the algorithm of answering temporal unions of conjunctive queries is presented and illustrated in examples. The section 4 is dedicated to the proofs of logical properties of the algorithm. The section 5 discusses the related work in the field of conjunctive queries answering. 2
Assume there is a knowledge base K = (A; T ), where T is a set of concept axioms (a
TBox), A is a set of assertional axioms (an ABox). Fix a language of a knowledge base
to ALC [
Query answering is the extension of a well known task of instance checking: given a knowledge base K and an assertion . Check whether this assertion is entailed by an ABox of K.
Let Vars(Q) be a set of all distinguished and non-distinguished variables which appear
in a query Q, let Inds(Q) to denote the set of all individual names which appear in
query Q and Terms(Q) to denote the set of all terms in Q, i.e. Vars(Q) [ Inds(Q).
Let us formally define conjunctive queries and Boolean conjunctive queries for a
wellelaborated language ALC [
Definition 1 (Conjunctive query, Union of conjunctive queries). Let x, y, c are respectively tuples of distinguished variables (answer variables), of non-distinguished variables and of individual names, and t, t1, t2 are terms in Terms(Q). A conjunctive query (CQ) is an expression of the form where conj(x; c) = 9y:q1 ^ : : : ^ qm;
qi ::= C(t) j r(t1; t2) A Boolean conjunctive query is a CQ without answer variables.
A union of conjunctive queries (UCQ) is a disjunction of conjunctive queries (CQs) of the form
Q(x) = fx j conj1(x; c) _ : : : _ conjn(x; c)g Example 1. The example of a query asking about all students that attend some courses and take some exams could be as follows:
Q(x) = fx j 9y:takeCourse(x; y) ^ takeExam(x; y)g
This query can be modified to a Boolean query by substitution of x with an individual name:
Q(x) = fj y:takeCourse("Eldora"; y) ^ takeExam("Eldora"; y)g We use jQj to denote the size of Q - the number of symbols required to build the query. The arity of a query will be the number of answer variables in the query. If all terms in Q are individual names, we say Q is ground. We write Q(c) for a query whose answer variables x are substituted by c, Q(x) for a conjunctive query and simply Q for a Boolean conjunctive query. Sometimes we write x1; : : : ; xn instead of x, and similarly for y and c.
Given an ALC-knowledge base K = hT ; Ai, an interpretation I satisfies a query Q(x) iff the interpretation function can be extended to the variables in Q(x) in such a way that I satisfies every term in Q(x). A query Q(x) is true w.r.t. K (written K j= Q) iff every interpretation that satisfies K also satisfies Q.
of answer variables x, and a knowledge base K, a tuple of individuals c with the same arity of x is an answer for Q in K if I j= Q(c) for every model I in K.
Given a Boolean conjunctive query Q, and a KB K, query entailment is a task to decide whether K j= Q if I j= Q for every model I of K.
Given a conjunctive query Q(x), a tuple of individuals a, and a KB K, query answering is a task to decide whether a is an answer for Q(x) in K. where
Let K = hT ; (Ai)0 i ni be a knowledge base with a sequence of ABoxes sharing
one TBox. Let’s describe a query language extending the language of conjunctions of
positive existential formulae built from query atoms. Having in mind linear temporal
logic LT L (see e.g. [
Definition 3. Temporal conjunctive query (TCQ) is an expression tconj(x; c) = 9y:q1 ^ : : : ^ qm;
qi ::= ' j ' ::= C(t) j r(t1; t2) ::= ' j 1 ^ 2 j # j # j 1 S 2 j 1 U 2 and C is a concept description, r is a role name, t; t1; t2 are terms in Terms(Q).
Derived temporal modalities like 3 (sometimes in the past), 2 (always in the
past), 3; 2 can be defined in a usual way (see, e.g. [
Example 2. A query asking about students who had defended their thesis some time ago and had been ex-matriculated since then is expressed as follows:
Q(x) = fx j 9y:3 Student(x) ^ exM atriculated(x) S hasDef ended(x; y)g The semantics of the TCQ is defined as follows.
Definition 4. A total function : Terms( ) ! is a binding for a query in an interpretation I, if (a) = a for all individuals a 2 dom( ), and the validity I; j= for atemporal CQ ' is defined inductively:
I; j= C(t) iff I j= C( (t)) I; j= r(t1; t2) iff I j= r( (t1); (t2)) I; j= '1 ^ '2 iff I; j= '1 and I; j= '2
I; j= 9y' iff 9e 2 : 0 = [y=e] and I; 0 j= ' where the notation [y=e] represents a binding extended with (y) = e if y is not in the domain of , otherwise the original value for y is replaced by e.
The validity for a TCQ and a KB K = hT ; (Ai)0 i ni is extended as follows: K; i; j= ' K; i; j= K; i; j= # K; i; j= # K; i; j= K; i; j=
iff 8I j=T Ai:I; j= ' 1 ^ 2 iff K; i; j= 1 and K; i; j= 2 iff i < n and K; i + 1; j= iff i > 0 and K; i 1; j= 1 U 2 iff 9k; i k n : K; k; j= 2
and 8j; i j < k : K; j; j= 1 1 S 2 iff 9k; 0 k i : K; k; j= 2
and 8j; k < j i : K; j; j= 1
For a binding , if, for every i, 8I j=T Ai:I j= K, this implies I j= . If such evaluation exists, we write K j= and we say is a match for in K. For a tuple of individuals c1; : : : ; cn mapped to a tuple of answer variables x1; : : : ; xn we say c1; : : : ; cn is a certain answer for in K, iff K j= [x1; : : : ; xn=c1; : : : ; cn]. We denote a set of certain answers for as Ans( ).
Definition 5. A union of temporal conjunctive queries (UTCQ) Q(x) is a disjunction of temporal conjunctive queries (see Definition 3):
Q(x) = fx j tconj1(x; c) _ : : : _ tconjn(x; c)g 4
4.1
The idea of answering a UTCQ against a set of ABoxes is to use temporal operators as the means of detection of time points at which atemporal CQs should be evaluated. Due to the recursive nature of such temporal operators as S ; U we have to store all the ABoxes and the values of particular CQs depending on the operator. Intuitively, given = # at a time point i, is evaluated at the time i + 1, and so on.
To be able to combine certain answers obtained from different CQs of one TCQ, let’s take a closer look at the nature of certain answers.
A certain answer to a CQ is a binding of each xi 2 x (distinguished variables) to some individual name that appeared in the KB K, such that in all models of K, K j= ( (x)). There could be more than one certain answer for a CQ , so further we shall consider a set of certain answers for a query (x). A correspondent set of matches for actually produces some k-ary relation, where k is the arity of a CQ .
A certain answer to a UCQ is a combination of answers of CQs in , i.e. c1 [: : :[ cn where n is a number of CQs in . For such a combination there are two possible situations: (i) disjuncts j1 , j2 in UCQ use pairwise disjoint sets of distinguished variables (i.e. there are no common distinguished variables in two arbitrary disjuncts of ); (ii) some disjuncts can share (some) distinguished variables of each other. To deal with sets of certain answers (that are actually relations) we adopt two operators of relational algebra, namely, - a cross-product, and ./ - a natural join.
Cross-product operator [
Definition 6. Given two bindings 1 : (x1; : : : ; xn) ! , 2 : (y1; : : : ; ym) ! , their cross-product, 1 2 is a binding : X ! where x; y are free variables that do not have any variables in common, and X = (x1; : : : ; xn; y1; : : : ; ym).
Join operator ./ [
Definition 7. Given two bindings 1 : (x1; : : : ; xn; z) ! , 2 : (y1; : : : ; ym; z) ! , their join, 1 ./ 2 is a binding : X ! where x; y; z are free variables and X = (x1; : : : ; xn; y1; : : : ; ym; z), iff every common variable z must be mapped to same constant c 2 .
A correspondent binding for
1 ./ : : : ./ n The following theorems show applications of will be: for (i) = 1 : : :
n , and for (ii) and ./ for bindings.
= 1 ./ 2 is a match for = 1 ^ 2, where 1, 2 are CQ formulas, a binding iff bindings 1, 2 are matches for 1, 2.
Proof. It is true based on the definition of the join operator.
= 1 2 is a match for match for 2.
= 1 _ 2, where 1, 2 are CQ formulas, a binding iff the binding 1 is a match for 1 or the binding 2 is a Proof. The ) direction is trivial.
For ( direction, assume 1 : (x1; : : : ; xn; z) 7! , 2 : (y1; : : : ; ym; z) 7! , and they are matches for 1 and 2. From the nature of disjuntion, we know that formula is satisfiable if either 1 or 2 is satisfiable. That means if there is a match for either 1 or 2. If z appears in both of the CQs, renaming z in one of the CQs does not change the validity. Therefore, we have that : (x1; : : : ; xn; z; y1; : : : ; ym; z0) 7! which is obtained from 1 2 is indeed a match for .
Now, consider a structure of a certain answer to a union of temporal CQs (UTCQ). It is a combination of answers to a (set of) TCQ obtained at proper time points, referred by temporal operators used in a UTCQ.
One more thing to be explicitly addressed is that known algorithms for conjunctive
query answering, such as [
Now, present the algorithm informally.
Eliminate temporal operators in a UTCQ The important step in our algorithm is to get a normal form where the temporal operators are used to decide at which time point should each CQ be evaluated. This is done by iterative applecation of the expansion rules Table 1. For every # and # operators, we just shift one point forward and backward. By doing these, we obtain a query that is in normal form whose atoms are UCQs, except some recursion atom which is a TCQ.
with join and every disjunction - with cross-product.
Retrieve an answer Use an arbitrary query answering algorithm [
For the illustration of Algorithm 1 consider some examples, assuming that Algorithm 1 returns a set Ans of answers to at the time point i.
Example 3. Given a TCQ query = # ( 1 U nmove forward one point by #
A more complex example is given below. Example 4. Given a TCQ query = 3 ( 1 U
There is one thing we have to ensure that in the intersection of two sets of answers for conjunction of CQs a certain answer is obtained, i.e. there is a common answer for both CQs, otherwise an empty set. One way to do this is to retrieve all answers for each CQ and then to intersect them to get some common answers. Another way is first to retrieve an answer of a UCQ and then to decide if this answer is also the answer for the other CQs in the conjunction, otherwise keep retrieving and deciding until there is no more answer obtained. The former way is preferred since it offers more practical solution. It means that we can deal with it using relational algebra operators or database language operators.
Definition 8. (UTCQ closure). Given a temporal union of conjunctive queries Q, its closure set, Cl(Q) is a set of query atoms closed under the following rules if q 2 Q then q 2 Cl(Q) if # q 2 Q then q 2 Cl(Q) if #q 2 Q then q 2 Cl(Q) if q1 ^ q2 then q1; q2 2 Cl(Q) if q1 _ q2 then q1; q2 2 Cl(Q) if q1 U q2 then q1; q2; #(q1 U q2) 2 Cl(Q) if q1 S q2 then q1; q2; # (q1 S q2) 2 Cl(Q)
Since a closure set for a UTCQ is finite, Algorithm 1 terminates after a finite number of steps. Theorem 3. (Local) termination. Given a UTCQ Q and a knowledge base
K = fT ; (Ai)0 i ng. Algorithm 1 always terminates.
Proof. We can show the local termination inductively.
Base case. Any query is also cointained in the closure set of itself.
(C(a), r(a1; a2)) If we have a query Q which is atomic, then the closure set contains C(a) or r(a1; a2).
(# T CQ) For such query Cl(Q) = fT CQ; # T CQg, i.e. evaluated are two elements, and in case of i = 0 the value of # T CQ is known to be ;, so Algorithm 1 stops after two evaluations.
(T CQ1 U T CQ2) For such query Cl(Q) = fT CQ2; T CQ1; T CQ1 U T CQ2; # (T CQ1 U T CQ2)g
(T CQ1 S T CQ2) For such query Cl(Q) = fT CQ2; T CQ1; T CQ1 S T CQ2; # (T CQ1 S T CQ2)g Theorem 4. Soundness. If for UTCQ Q its answer set Ans(Q(x); i), obtained with Algorithm 1, is not empty, then Q has at least those certain answers that are in Ans(Q; i). Proof. We prove by induction. We start with evaluating non-temporal query, i.e. a query containing no temporal operator.
Base case If we have an atomic query in the form of C(a), then using any approach of CQ answering we obtain all the answers for the query Q entailment over K = fT ; (Ai)0 i ng. If K j= C(a) and a 2 Ans(Q(x); i), the function returns a and this value is stored in Ans(Q(x); i). By Definition 4, this result tells us that the individual a is a certain answer to the query C(x) w.r.t. the match (x) = a. The same result is obtained if we have atomic query in the form of r(a; b).
Inductive case can be obtained by Definition 4.
Theorem 5. Completeness. If a UTCQ Q has a certain answer ans, then Algorithm 1 shows that this answer is in Ans(Q; i).
Proof. By contradiction. Assume that (i) Q(x) has a certain answer ans w.r.t , (ii) Ans(Q; i) - is a set of certain answers obtained by Algorithm 1, and (iii) ans 62 Ans(Q; i). By (i), we know that K j= Q(ans) and that for all time points 0 i n in all models I, such that I j= K, I j= Q(ans). By (ii), for Algorithm 1 to return Ans(Q; i) such that ans 62 Ans(Q; i) there are several reasons for it.
Q is atomic. If Q is atomic, i.e. in the form C(x) or r(x; y), then we know that Ans(Q; i) does not contain ans. This means that there is a model I of a knowledge base K which does not entail Q(ans). But this is a contradiction to our assumption (i).
(T CQ1 ^ T CQ2). If Ans(Q; i) does not contain ans, according to Algorithm 1 it means that ans 62 Ans(T CQ1; i) ./ Ans(T CQ2; i). This, in turn, leads to the existence of a model I of a knowledge base K such that I j= T CQ1(ans) and I 2 T CQ2(ans) or vice versa, that contradicts to (i).
(T CQ1 _ T CQ2). If Ans(Q; i) does not contain ans, according to Algorithm 1 it means that ans 62 Ans(T CQ1; i) Ans(T CQ2; i). This, in turn, leads to the existence of a model I of a knowledge base K such that either I 2 T CQ1(ans) or I 2 T CQ2(ans), that contradicts to (i). (# T CQ). If Ans(Q; i) does not contain ans, according to Algorithm 1 it means that ans 62 Ans(Q; i 1). This, in turn, leads to the existence of a model I of a knowledge base K such that I; i 1 2 Q(ans), that contradicts to (i).
(T CQ1 U T CQ2). If Ans(Q; i) does not contain ans, according to Algorithm 1 it means that ans 62 Ans(T CQ2; i) (Ans(T CQ1; i) ./ Ans(Q; i + 1). This, in turn, leads to the existence of a model I of a knowledge base K such that either I; i 2 T CQ2(ans) or I; i 2 T CQ1(ans) and I; i + 1 2 Q, that contradicts to (i).
(T CQ1 S T CQ2). If Ans(Q; i) does not contain ans, according to Algorithm 1 it means that ans 62 Ans(T CQ2; i) (Ans(T CQ1; i) ./ Ans(Q; i 1). This, in turn, leads to the existence of a model I of a knowledge base K such that either I; i 2 T CQ2(ans) or I; i 2 T CQ1(ans) and I; i 1 2 Q, that contradicts to (i).
The proof for the temporal operator # acting in the direction of future can be completed in the same manner. 5
Transition graphs for a temporal query language answering over a finite set of versions
of a database were investigated in [
Acknowledgements The presented results were obtained during the research visit of the author to the Chair of Automata Theory at Dresden University of Technology. The author is grateful to the group of Prof. Franz Baader, and in particular, Eldora, Marcel Lippmann and Anni-Yasmin Turhan for the fruitful discussions and ideas at the stage of early drafts of the paper.