Introduction

The use of ontologies in data access is based on semantic query answering, in particular on answering user queries expressed in terms of a terminology (that is connected to the data) and usually represented in the form of conjunctive queries (CQs) [6,1]. The main restriction of the applicability of the specific approach is that the problem of answering CQs in terms of ontologies represented in description logics (the underlying framework of the W3C's Web Ontology Language -OWL) has been proved to be difficult, suffering from very high worst-case complexity (higher than other standard reasoning problems) that is not relaxed in practice [6]. This is the reason that methods and techniques targeting the development of practical systems mainly follow two distinct directions. The first suggests the reduction of the ontology language expressivity used for the representation of CQs vocabulary, while the second sacrifices the completeness of the CQ answering process, providing as much expressivity as possible. Methods of the first approach mainly focus on decoupling CQ answering into (a) the use of terminological knowledge provided by the ontology (the reasoning part of query answering) and (b) the actual query execution (the data retrieval), thus splitting the problem into two independent steps [1,4,10]. During the first step (usually called query rewriting) the CQ is analysed with the aid of the ontology and expanded into a (hopefully finite) set of conjunctive queries, using all the constrains provided by the ontology. Then, the CQs of the above set are processed with traditional query answering methods on databases or triple stores, since terminological knowledge is no longer necessary. The main objective is to reduce the expressivity of the ontology language until the point that the procedure guarantees completeness. Late research in the area, introduced the DL-Lite family of description logics, underpinning W3C's OWL 2 QL Profile [4,3], in which the CQ answering problem is AC 0 w.r.t. data. Despite the obvious advantage of using the mature technology (more than 40 years research) of relational databases, there are also other major technological advantages of the specific approach, most of them connected with the use of first-order resolution-based reasoning algorithms [7][5,Ch.2]. The main restriction is that in the presence of large terminologies, the algorithm becomes rather impractical, since the exponential behaviour (caused by the exponential query complexity) affects the efficiency of the system.

The attempts to provide scalable semantic query answering over ontologies expressed in larger fragments of OWL introduced the notion of approximation. Approximate reasoning usually implies unsoundness and/or incompleteness, however in the case of semantic query answering most systems are sound. Typical examples of incomplete query answering systems are the well-known triple stores (Sesame, OWLIM, Virtuoso, AllegroGraph, Mulgara etc). The two main characteristics distinguishing incomplete semantic CQ answering systems is how efficient and how incomplete they are. The efficiency of semantic query answering is usually tested with the aid of real data of a specific application or using standard benchmarks [8]. Lately, a systematic approach of the study of incompleteness of semantic query answering systems has been also presented [9]. A major issue here is that the user should be aware of the type of lost correct answers, i.e. there should be a general deterministic criterion expressing a type of relevance, indicating how crucial is the loss of each correct answer.

Within the above framework, herein we present an alternative direction in scalably solving the problem of semantic query answering ensuring a safe approximation process that hopefully converges to a complete solution. The idea is to provide the user with correct answers as soon as they are derived and continue until all the correct answers are found, ensuring that the relevant correct answers will be first given. For example, in the case of the query rewriting approach this means that instead of clearly splitting the steps of query rewriting and query processing, whenever a new rewriting is found it can be evaluated against the database and the results can be presented to the user. In order for this idea to be successfully applied, several intuitive requirements should be fulfilled: the first correct answers should be given very fast; an important amount of correct answers should be found in a first small percentage of execution time; complete-ness should be ideally reached (or at least approximated); correct answers should be given following a degree of importance, according to a semantic preference criterion; the results should not be widely replicated.

In the present paper, we provide a systematic approach formalising the above idea. We introduce progressive semantic query answering based on the notion of CQ answering strides that are flows of correct answers with specific properties that formalise the intuitive meaning of the above criteria. We then provide a practical progressive semantic CQ answering algorithm that has some nice properties and is complete in OWL 2 QL and present the results of its implementation and evaluation (we call the implemented system ProgRes). The algorithm is based on a query rewriting resolution-based procedure that computes a sequence of rewritings, the elements of which have a decreasing importance according to a query similarity criterion (measuring the similarity of the rewriting with the user CQ). The order is proved to be ensured under a specific resolution rule application strategy that ProgRes follows. It is interesting that although the results are ordered (ranked) and given during the execution, the efficiency of the algorithm is not worse than other similar ones (like the one implemented in Requiem [7]).

Preliminaries

The most relevant with the problem of query answering OWL QL Profile is based on DL-Lite R [1,4]. A DL-Lite R ontology is a tuple T , A , where T is the terminology (usually called TBox) representing the entities of the domain and A is the assertional knowledge (usually called ABox) describing the objects of the world in terms of the above entities. Formally, T is a set of terminological axioms of the form C 1 C 2 or R 1 R 2 , where C 1 , C 2 are concept descriptions and R 1 , R 2 are role descriptions, employing atomic concepts, atomic roles and individuals that are elements of the denumerable, disjoint sets C, R, I, respectively. The ABox A is a finite set of assertions of the form A(a) or R(a, b), where a, b ∈ I, A ∈ C and R ∈ R. A DL-Lite R -concept can be either an atomic one or ∃R. . Negations of DL-Lite R -concepts can be used only in the right part of subsumption axioms. A DL-Lite R -role is either an atomic role R ∈ R or its inverse R − . A conjunctive query (CQ) has the form q : Q(x) ← n i C i (x; y), where Q(x) is the answering predicate (the head of the CQ), employing a finite set of variables, called distinguished, and the conjuncts C i (x; y) (forming the body of the CQ) are predicates possibly employing non-distinguished variables. We say that a CQ q is posed over an ontology O iff all the conjuncts of its body are concept or role names occurring in the ontology. A tuple of constants a is a certain answer of a conjunctive query Q posed over the ontology O = T , A iff O ∪ q |= Q(a), considering q as a universally quantified implication under the usual FOL semantics. The set containing all the answers of the query q over the ontology O is denoted with cert(q, O). A union of CQs q is a rewriting of q over a TBox T iff cert(q , ∅, A ) = cert(q, O), with O = T , A and A any ABox. We will denote the set of all CQs in the rewriting of q over the TBox T by rewr(q, T ). With a little abuse of notation we write rewr(q, O), meaning rewr(q, T ) (T is the TBox of O).

Semantic query answering strides

Semantic CQ answering systems are based on sophisticated algorithms that try to find as many certain answers of CQs as possible. Formally, any procedure A(q, O) that computes a set of tuples a for a CQ q posed over an ontology O is a CQ answering algorithm (CQA algorithm). A(q, O) is sound iff res(A(q, O)) ⊆ cert(q, O) and complete iff cert(q, O) ⊆ res(A(q, O)) (res( ) is the result of any algorithm ). Any procedure R(q, T ) computing a set of rewritings of q over a TBox T is a CQ rewriting algorithm. R(q, T ) can be the basis of a CQ answering algorithm A(q, O) with the aid of a procedure E(q, A) that evaluates the query and retrieves the data from the database. In this case, we write

A(q, O) = [R | E] (q, O). Obviously, it is res([R | E] (q, O)) = res (E(res (R(q, T )), A)).

With a little abuse of notation, we freely write A(U, O), R(U, T ) and E(U, A) for procedures computing answers to sets U of CQs. A natural question arising in cases where scalability is a major requirement is how to split the execution of a CQ query answering algorithm into parts enabling a progressive extraction of certain answers. Also, how to control the progress of the algorithm ensuring that certain answers extracted until any specific time have desirable characteristics. Let us now proceed to the definitions that form the framework of progressive CQ answering, covering the above intuition. Definition 1. Progressive CQ answering (PCQA) Any sequence P(q, O; i) = {A j } i , i ∈ N, i > 1 where A j are CQA algorithms for a query q posed over an ontology O = T , A , is a progressive CQ answering algorithm. The elements of P are its componets. If P is finite, we write

P(q, O) = [A 1 ; A 2 ; • • • ; A n ] (q, O).

It is important to notice that the components of PCQA algorithms can freely change inputs and outputs in a forward manner, leaving the sequence P(i) to possibly have a recursive character. The restriction is that any component should be considered as a CQA algorithm meaning that, at any time point, we can ask for the result of any subset of the components being able to compute it (possibly using the output of the previous components). We say that P(q, O) is sound iff res(P) ⊆ cert(q, O) and complete iff cert(q, O) ⊆ res(P). Since our intention is to provide users with correct answers during the execution of P, we need refer to the result set of a subset of components of P stratifying the desired answer flow. Definition 2. PCQA Strides Let P(q, O) be a PCQA algorithm. A stride s(P; i : j), i, j ∈ N, i ≤ j of P (if it is infinite j can be equal to ∞) is the result of the execution of its components

A i to A j , i.e. s(P; i : j) = [i,j] res(A k ).

Let Σ(P) denote the set of all strides of P. Obviously, res(A) ∈ Σ(P), for any component A of P and also res(P) ∈ Σ(P). We will refer to the former as a single stride and to the latter as the total stride. A stratification of P is a sequence s 1 , s 2 , ..., s k of strides of P. Now, we turn our attention to the study of PCQA algorithms the strides of which provide answers with decreasing relevance to the user query posed. The first step is to rank the elements of the strides according to the query posed by the user. Let σ(O; a, q) be a relevance measure expressing the importance of the tuple a ∈ s, with s ∈ Σ(P), i.e. the degree in which the specific tuple ideally (and with the less risk) fits to the user query.

The nature of the relevance measure may differ from one application to another. In the present paper we consider the case of a measure representing the possibility of correctness of a specific answer. Similar measures play an important role in information retrieval systems, in the process of ranking the results of query answering (see for example [12,[14][15][16]). Intuitively, here we consider that some axioms of the TBox are not always valid for the specific data, i.e. some exceptions may exist in the large data set making the specific axiom typically inconsistent. The effect is that some answers derived from the query answering process are not correct. This could be a result of untrusted knowledge or by the nature of the specific axiom that is only usually valid. For example, although we know that all professors are teaching some courses, there could be the case that some professors (for some reasons) are not teaching. The problem could be solved if we had some additional information about the correctness of the TBox axioms (the provenance of the specific axiom implying a degree of trust etc). If we do not have any additional information, the only rule that we could follow is that the answer is more safe if we use less knowledge to derive it, i.e. the less reasoning the most relevance. We will further clarify this later that we focus to query rewriting PCQAs.

Definition 3. Stride Ordering

Let P(q, O) be a PCQA algorithm and Σ(P) the set of its strides after the execution of the query q over the ontology O. Let also σ(a, q) be a relevance measure of the elements of the total stride and the CQs. We say that a stride s 1 (P; i : j) σ-precedes a stride s 2 (P; i : j ) for the query q and we write s 1 q σ s 2 iff for all a 1 ∈ s 1 , a 2 ∈ s 2 we have σ(a 1 , q) ≥ σ(a 2 , q). If σ(a 1 , q) > σ(a 2 , q), we say that s 1 strictly σ-precedes s 2 and we write s 1 ≺ q σ s 2 . If neither s 1 q σ s 2 nor s 2 q σ s 1 , we have s 1 ⊀ q σ s 2 (they are σ-irrelevant for q). It is not difficult to see that Σ(P) forms a lattice under any ≺ q σ operator, where ∅ is its infimum and cert(q, O) is its supremum (supposing that P is sound and complete). Now that we have an ordering of strides, we are ready to proceed to the definition of progressive algorithms the strides of which are ordered. Algorithms of this type ensure that the answer blocks are ordered according to a specific relevance measure. Therefore, they can be considered as approximation algorithms with deterministically controllable behaviour. Definition 4. Sorted PCQA Algorithms Let P(q, O) be a PCQA algorithm, = s 1 , s 2 , ..., s k a stratification of P and ≺ q σ an ordering relation over Σ(P). We say that P is σ-sorted under iff for any successive strides s i , s j of it is s i q σ s j . It is strictly σ-sorted iff s i ≺ q σ s j otherwise it is σ-unsorted for q.

Example 1. Consider the simple DL-Lite R ontology O = T , A , with PCQA algorithms ensure that the results are given in a specific order that the user knows before the query answering process, according to a specific relevance criterion. For example, we could develop P = A 1 ; A 2 ; A 3 ; A 4 ; A 5 with a stratification s 1 ; s 2 ; s 3 , where s 1 (P; 1 : 1)) = res(A 1 ) = {John}, s 2 (P; 2 : 3) = res(A 3 ) ∪ res(A 4 ) = {John, Alan} and s 3 (P; 4 : 5) = res(A 5 ∪ A 5 ) = {John, Sofia, Ema}.

T = {PhDStudent

Here, we consider that data is more strong than the knowledge, meaning that there could be possible exceptions in some restrictions expressed as TBox axioms. Thus, an obvious solution is that John should be the first answer (explicitly given), Alan employs a bit more risk (some reasoning is needed), while Sofia and Ema are the most risky answers (for example it could be the case that Sofia does not advise anyone for some reasons). It is not difficult to see that P is sorted according to the above intuitive measure.

Practical progressive query answering

The problem of progressive query answering is more difficult than the nonprogressive one, since the extracted results should be ranked according to a specific criterion and the ranking should be ensured during the query answering process (without knowledge of all the results). Obviously, the difficulty strongly depends on the expressivity of the ontology language and the specific relevance measure. Here, we focus on query rewriting PCQA algorithms for DL-Lite R , i.e. on cases where the components of P are based on query rewriting algorithms. We follow a resolution-based FO rewriting strategy (more details can be found in [7]). Intuitively, algorithms of this category are based on the translation of the terminology into a set of FOL axioms and the repeated application of a set of resolution rules employing the query and the FOL axioms until no rule can be applied. It is ensured that when the algorithm stops it has produced all the rewritings of the user query. The idea is to stratify the application of the resolution rules in order to ensure that the rewritings will be extracted according to a specific order, following a similarity criterion in comparison to the user query. Thus, we can evaluate against the database the fresh queries (rewritings) as they are derived and provide the user with a set of fresh answers. The proposed algorithm remains sound and complete and, although it solves a more difficult problem, in several cases it is more efficient than the respective non-progressive algorithm proposed in [7].

We will use a graph representation of the CQs that is more convenient for the definition of similarity measures. Let q : Q(x) ← n i C i (x; y) posed over an ontology O. Since the conjuncts of q are entities of the terminology, they can only employ one (if they are concepts) or two (if they are roles) variables (distinguished or not). A non-distinguished variable that appears only once in the query body is called unbound, otherwise it is bound. We represent a CQ as an undirected graph G q (V q , E q , L Vq , L Eq ), where V q is the set of nodes representing the variables of the query, E q is the set of edges, L Vq is the set of node labels (representing the set of concept conjuncts employing each variable) and L Eq = L + Eq , L − Eq is the tuple of sets of edge labels (representing the set of role conjuncts employing each variable pair in L + Eq and its inverse in L − Eq ). The nodes corresponding to unbound variables are called blank nodes. Moreover, let

V (b) q (V (u)

q ) denote the set of bound (unbound) variable nodes and

E (b) q (E (u)

q ) denote the set of edges employing two bound (at least one unbound) variable node(s). Obviously,

L Vq (x) = ∅ and |L + Eq (x, y) ∪ L − Eq (x, y)| = 1, for each x ∈ V (u)

q , y ∈ V q . We can easily extend the above notations to represent general terms instead of simple variables. The only issue that needs more attention is that in this case a node is blank only if it represents a term employing functions and variables that do not appear in any other term. For simplicity, we can delete the blank nodes of the graph and add the role name that appears in L + Eq (x, y) (or its inverse if it appears in L − Eq (x, y)) in the label of the node x that is connected with the specific blank node. In this case, the node label sets can also include role names (or inverse role names). We will make use of this simplifying convention in the sequel, in the description of our algorithm. There are several graph similarity measures (relations between graphs that are reflexive and symmetric) proposed in the literature, especially in the framework of ontology matching [11,13]. Here, we will introduce a new measure that captures the intuitive meaning of the query similarity that is useful in query rewriting PCQA algorithms. Definition 5. Query Similarity Let q 1 and q 2 be two non-empty conjunctive queries and G q1 (V q1 , E q1 , L Vq 1 , L Eq 1 ), G q2 (V q2 , E q2 , L Vq 2 , L Eq 2 ) their graph representations. Their similarity can be defined as follows (up to variable renaming):

σ(q 1 , q 2 ) = 1 − λv+λ vmin+ min + (δ v + δ ) |V (b) q 1 | + |V (b) q 2 | + |E (b) q 1 | + |E (b) q 2 | + 1 (1)

where v min = min (|V (b)

q 1 |, |V (b) q 2 |), min = min (|E (b) q 1 |, |E (b) q 2 |), δ v = |V (b) q 1 V (b) q 2 |, δ = |E (b) q1 E (b) q2 | ( computes the non-common elements of the two sets), λ v = | x : x ∈ V (b) q 1 ∧ x ∈ V (b) q 2 ∧ L Vq 1 (x) = L Vq 2 (x) ∨ L (u) q 1 (x, y) = L (u) q 2 (x, y) | and λ = |{(x, y) : (x, y) ∈ E (b) q1 ∧ (x, y) ∈ E (b) q2 ∧ L Eq 1 (x, y) = L Eq 2 (x, y)}|.

The first term of the numerator of the similarity measure (Eq. 1) captures the node and edge labeling differences, the second term the structure difference, while the denominator normalises the values between 0 and 1. The main intuition behind Eq. 1 is that the labeling differences should be counted as a secondary dissimilarity cause, while the primer one should be the difference in structure. Thus, the maximum value of the first term of the fraction should not exceed the value of the second term (cannot exceed the value 1, which is the lowest structural difference). The computation of differences ignores all the unbound variables (the blank nodes of the graph), that are only involved in the computation of λ v (summarising the node label differences). The intuition behind this is that blank nodes are introduced only by unqualified existentials (∃R. ) and thus the specific unbound variable could be rejected without any problem if we just remember the role of the existential. It is important to notice that in the presence of role inverse, the bound variable could be either in the subject or in the filler part of the role; this is the reason why we consider undirected graphs and L (u) q (considering both L (u)+ q and L (u)− q ) is involved in the computation of λ v . Finally, we should notice that with a little abuse of notation, we introduced the similarity between two queries and not between queries and answers (as imposed in the previous section), implicitly meaning that the similarity is between the first query and the answers of the second one. In this way, we significantly simplified the notation in the case of query rewriting based PCQA algorithms.

P R − S(x, y) ← P (y, x) R P R − P ∃P A A(x) ← P (x, y) (3) ∃P − A A(x) ← P (y, x) A ∃P P (x, f (x)) ← A(x) (4) A ∃P − P (f (x), x) ← A(x) A ∃P.B P (x, f (x)) ← A(x) (4) A ∃P − .B P (f (x), x) ← A(x) B(f (x)) ← A(x) (5) B(f (x)) ← A(x)(2)

We are now ready to introduce a PCQA algorithm, which we call ProgResAns and is sorted according to σ(q 1 , q 2 ). In order to compute the query rewritings of a user query q, the algorithm employs a set of resolution rules. The main premise is always a query (q or a subsequently computed query rewriting) and the side premise a clause of Ξ(O). Ξ(O) is obtained from ontology O as described in Table 1 [7]. The idea of the algorithm is the following: start from the user query; apply the resolution rule using side premises that preserve the structure of the query (we call this step structure preserving resolution or sp-resolution); apply the resolution rule using side premises that minimally change the structure of the query (we call this step structure reducing resolution or sr-resolution); apply anew sp-resolution to the query rewritings produced by sr-resolution, and so on; at each step evaluate the queries against the database and provide the user with the results. sp-and sr-resolution are performed by procedures sp-Resolve and sr-Resolve, respectively. sp-Resolve takes as input a query q and an element s of G q (i.e. either a node or an edge), and computes all possible rewritings of q, by iteratively applying the resolution rule using as side premises the clauses of Ξ(O) that are of type ( 1)-( 4) (see Table 1). Initially, the main premise is q and the resolution rule is applied for all atoms in q that correspond to s. The same process is iteratively applied to all the resulting rewritings, until no more rewritings can be obtained. The clauses of type ( 4) are used only if the skolemized term f (x) unifies with an unbound variable of the main premise. sp-Resolve preserves the query structure, since resolution with clauses of type ( 1) or ( 2) affects only the sets L V and L E , respectively. Clauses of type ( 3) and ( 4) introduce and eliminate blank nodes.

sr-Resolve takes as input a query q and an element s of G q (i.e. either a node or an edge) and computes all possible rewritings of q, by iteratively applying the resolution rule using as side premises the clauses of Ξ(O) that are of type ( 4) and (5). Clauses of type ( 4) are used only if f (x) unifies with a bound variable of the query. In terms of graphs, sr-Resolve deletes a node together with the edges that connect it to the rest of the graph. ProgResAns applies sr-Resolve only on selected atoms (the atoms that correspond to the elements s of G q mentioned above) of q, called the sink node atoms of q. Sink nodes s correspond to non distinguished terms and are determined by the following condition concerning their labels: L ± E (s, y) = ∅ and L ∓ E (s, y) ≥ 1. The selective application of the resolution rule only to the sink node atoms is proved to suffice for the production of eventually all the possible query rewritings which can be evaluated against the database (i.e. query rewritings that do not contain functional terms).

We now provide the full definition of ProgResAns. Its components are the query rewriting procedures (sp-Rewrite and sr-Rewrite) and the procedure Eval, which evaluates a set of rewritings against the database:

ProgResAns = Eval ; {{[sp-Rewrite | Eval ]} nj i=1 ; [sr-Rewrite | Eval ]} m j=1

sp-Rewrite and sr-Rewrite are defined by algorithms 1 and 2. sp-Rewrite employs sp-Resolve to perform exhaustive sp-resolution for all queries in the input set Q sp in . Therefore, the queries in res(sp-Resolve) have the same structure (up to blank nodes) with the queries in Q sp in , but each one of them is the result of the exhaustive application of sp-resolution on a single node or edge. The node or edge whose label is modified is annotated, so that by recursively applying sp-Resolve we can compute all possible rewritings that have the same number of different has changed only sink node atoms, so that, as mentioned before, sr-resolution is applied only on these atoms. As soon as sp-Rewrite or sr-Rewrite return, Eval computes cert(res(sp-Rewrite), O) and cert(res(sr-Rewrite), O), respectively. The following theorem can be proved: Theorem 1. ProgResAns terminates and it is sound, complete and σ-sorted.

Proof. The proof is omitted due to restricted space.

Example 2. (continued) Table 2 summarises the results of applying ProgResAns to the input of Example 1 (all the single strides are shown).

Q(x) ← advise(x, y) ∧ advise(y, z) 1.000 John 2 Q(x) ← supervise(x, y) ∧ advise(y, z) 0.952 Q(x) ← advise(x, y) ∧ ResCoordinator(y) 0.952 John Q(x) ← advise(x, y) ∧ ResDirector(y) 0.952 Q(x) ← advise(x, y) ∧ supervise(y, z) 0.952 Alan Q(x) ← advise(x, y) ∧ SeniorResearcher(y) 0.952 Alan Q(x) ← advise(x, y) ∧ Professor(y) 0.952 3 Q(x) ← supervise(x, y) ∧ ResCoordinator(y) 0.905 Q(x) ← supervise(x, y) ∧ ResDirector(y) 0.905 Q(x) ← supervise(x, y) ∧ supervise(y, z) 0.905 Q(x) ← supervise(x, y) ∧ SeniorResearcher(y) 0.905 Q(x) ← supervise(x, y) ∧ Professor(y) 0.905 4 Q(x) ← ResDirector(x) 0.400 John 5 Q(x) ← Professor(x) 0.400 Sofia, Emma

System evaluation

We now present an empirical evaluation of ProgRes, which implements the ProgResAns algorithm, assuming that ABoxes are stored in a relational database. Our goal is to evaluate the performance of ProgRes and investigate whether the ranked computation of the answers introduces a significant time overhead. Given the progressive nature of ProgRes, meaning that each rewriting should be evaluated against the database upon its computation, our implementation follows a producer/consumer approach: A thread computes the rewritings and adds them to an execution queue, while another thread implementing the Eval procedure, retrieves the rewritings from the queue, translates them into SQL, dispatches them to the database, and collects the answers. We compare ProgRes with Requiem (implementation of the algorithm in [7]), which is the most similar non-progressive DL-Lite R query answering system. We should point out, however, that a fair comparison is not possible since we are comparing a ranking, progressive algorithm with a non-ranking, non-progressive one. For an as fair as possible comparison, we reimplemented the greedy unfolding strategy of Requiem within our programming framework. This was mainly done for the comparison of the time performance to be done on equal terms and did not alter in any way the Requiem algorithm (although as we shall see in the sequel in one case our implementation performed significantly better than the original one). Nevertheless, we have to notice that the results should be interpreted only as indicative of the relative performance of the two systems.

An important issue our system had to face is the fact that, due to the realtime orientation of ProgRes, many redundant rewritings (i.e. rewritings that are structurally subsumed by subsequent, not yet computed rewritings) may be obtained. If all of them are dispatched to the database, performance may be significantly compromised. For this reason we slightly delay the addition of the new rewritings to the execution queue, by computing first all the rewritings of a stride, check for redundancies and add only the non-redundant ones to the queue. The structure of the Requiem algorithm does not allow for a directly comparable optimization strategy. In fact, the last step of Requiem is precisely a final query redundancy check step, in which any redundant queries are discarded all together. Therefore, in our evaluation of Requiem, following the original implementation, all the queries are added to the queue after the entire algorithm has finished and the final redundancy check has been performed.

We present the results for the A and S ontologies [7], as well as for P5S, a modified version of P5, in which we have included some subconcepts for the PathX concepts of P5. Briefly, ontology A is an ontology that models information about abilities, disabilities and related devices developed for the South African National Accessibility Portal. Ontology S is an ontology that models information about European Union financial institutions. Ontology P5 is a synthetic ontology developed by the authors of [7] that models information about graphs (nodes and vertices) and contains classes that represent paths of length 1-5.

We evaluate ontology A with queries AQ4 and AQ5 (of size 3 and 5, respectively), ontology S with query SQ5 (of size 7) and P5S with queries PQ4 and PQ5 (of size 4 and 5, respectively). Due to restricted space we do not present the results of all ontologies and queries in [7], we choose the particular combinations as most representative of several diverse cases. We populated the ABoxes according to [9]. The results are shown in Fig. 1. In each row, the lhs graphs present the total number of retrieved answers vs time and the rhs graphs the evolution of similarity as new answers are retrieved. Execution time is total time, including both query rewriting computation and answer retrieval time. The small vertical bars at the two horizontal dotted lines on the top of the lhs graphs indicate the time points at which one or more new rewritings become available for execution. The upper line corresponds to ProgRes, the lower to Requiem. Table 3 presents the number of rewritings and inferences. Within parentheses are the no. of inferences during sp-resolution (which corresponds roughly to the unfolding of Requiem) and the no. of inferences during sr-resolution (which corresponds roughly to the saturation step of Requiem). Note that some of the inferences 3 presents the time required for the computation of the rewritings (not including the query execution) for ProgRes and Requiem. For Requiem two times are given: the first refers to our implementation of Requiem (which we used in all other parts of the evaluation), and the second one, within parenthesis, to the original implementation (obtained from http://www.comlab.ox.ac.uk/projects/requiem). We note that in one case, in particular for ontology S, our implementation performs significantly better. This is due to the fact that it handles more effectively and removes at an earlier stage atoms that happen to be redundant within a single rewriting; as we shall also mention in the sequel, SQ5 happens to be a query that produces a lot of rewritings that contain several redundant atoms. Ontology A is to a large extent taxonomic. Both queries AQ4 and AQ5 produce many non-redundant rewritings, after a long sp-resolution/unfolding phase. In AQ4, ProgRes produces more queries (some redundant ones) and in AQ5 it performs more inferences than Requiem. This is due to the structured pattern followed in the computation of the rewritings, which as mentioned before may introduce more redundancies. This is more obvious in ontology S, where ProgRes produces a lot of redundant queries. This is however an extreme degenerate case: SQ5 is a bad query, as half of its atoms are essentially redundant. Back to ontology A, we note that although ProgRes needs slightly more time to compute the rewritings, it terminates faster. This is due to the progressive nature of ProgRes. While the producer thread computes the query rewritings, the consumer thread executes the already available ones, so there is no significant idle time for the consumer thread. In contrast, in Requiem the rewritings are obtained at the end, all together. This demonstrates the significant benefit from progressively computing and evaluating the query rewritings. The situation is quite different in ontology P5S, in which the inference procedure consist mainly of a chain of sr-reduction/saturation steps. Here, the strategy of ProgRes is much more efficient and scalable. It avoids a very large number of inference sequences that are guaranteed to give no new queries, by applying sr-resolution only on sink atoms. As a result, it finishes almost instantly, while for query PQ5 Requiem needs significantly more time and inferences. It is important to note, that in this case the performance of Requiem is not scalable in the size of the query, as it is easy to see by comparing the results for queries PQ4 and PQ5 (in PQ5 we search for all graph paths of length 5, while in PQ4 for paths of length 4). In contrast to Requiem, almost the entire execution time of ProgRes is answer retrieval time. The synthetic nature of P5S allows us to comment also on the evolution of the similarity of the answers. In (the original) ontology P5, only sr-resolution/saturation steps are involved, hence we expect ProgRes and Requiem to compute the rewritings in the same order (but not the same fast). In ontology P5S, however, for each rewriting produced at a sr-reduction step, ProgRes computes immediately all its sp-resolutions, and so the progressive decrease of similarity is achieved. Requiem computes first all the rewritings resulting from the saturation step and then all the unfoldings, hence no ranking of the answers is possible. Similar is the situation for query AQ4. In the case of AQ5, all the rewritings have the same graph structure, so the slight fluctuations in the similarity graph for Requiem are due to the non-ordered computation of the unfoldings. A steep decrease in the similarity measure occurs only when the structure of a rewriting w.r.t the original query changes.

Conclusions and future work

We have presented a systematic approach to the problem of stratifying over time the execution of CQA algorithms. We introduced the notions of progressive CQA algorithms (sequences of CQAs -its components), of strides (result sets of subsets of the components), of ordering of strides measuring the relevance of the answers with the user query and of sorted progressive CQAs ensuring a controllable approximation of the correct answer set. We have also presented a practical algorithm for progressive CQA in DL-Lite R that implements the above ideas and showed that it is possible to develop progressive algorithms that are efficient. Actually, it has been found that in the presence of large queries and TBoxes that are not simple taxonomies of atomic concepts the proposed algorithm can be much more efficient than the similar non-progressive ones (overcoming a strong limitation of some DL-Lite R CQA systems). An obvious advantage of the specific approach is the ability to be responsive even in cases of huge databases under a predetermined approximation strategy. A second advantage is that in case of inconsistency and considering data as stronger than theory (in information retrieval this is reasonable), PCQAs ensure a decreased possibility of incorrect answers. Finally, PCQA have ideal structure for parallel processing. The main disadvantage is that it is difficult to reduce the redundancies, since the complete set of answers is not available before the output. The present work can be extended in several directions. We could take advantage of the ideas presented in [10] and dramatically improved the performance of DL-Lite R CQAs. Also, we could develop PCQA algorithms and systems for more expressive DLs. Finally, we could try to stratify smaller strides in ProgRes avoiding wide replications by applying sophisticated redundancy checking.