We consider the problem of querying data sources that have limited capabilities and can thus only be accessed by complying with certain binding patterns for their attributes. This is often the case, e.g., in the context of data on the web queryable via web forms as well as in legacy data wrapped in relational tables. In such contexts, computing the answer to a user query cannot be done as in a traditional database; instead, a query plan is needed that takes the access limitations into account. In this paper, we develop a technique for producing a (possibly recursive) Datalog program that retrieves all obtainable answers for a query with limited source capabilities. In particular, we improve with respect to a previously published algorithm for optimizing query answering for conjunctive queries. Furthermore, we extend it to the context of unions of conjunctive queries. The algorithm exploits the structure of the query together with the binding patterns present in the source schema in order to compute an optimized query plan. The optimization excludes from the query plan the sources that are not relevant for the answer thus reducing the number of accesses to the sources.
In the context of integration of data over the Web [3], data are often accessible only via forms, where typically certain fields are required to be filled in by the user in order to obtain a result. Consider for example the web site of an online bookstore, where, in order to obtain a list of publications extracted from an underlying database, either an author or a title has to be specified, while it is not possible to ask directly, e.g., for all books of a certain publisher. Similarly, in legacy systems where data are scattered over several files, such data may be wrapped and masked as relational tables; however, such tables typically cannot be queried freely, since there may be access limitations due to the way the data are organized in the files.
Limitations on how sources can be accessed significantly complicate query processing [11, 7, 4, 2], since in this case the query plan may fail to comply with the access limitations. As shown in [11, 7, 9, 8], query answering in the presence of access limitations in general requires the evaluation of a recursive query plan, which can be suitably expressed in Datalog. The related problem of query containment in the presence of access limitations is addressed in [10].
Since source accesses are costly, an important issue is how to reduce the number of accesses to the sources while still obtaining all possible answers to a query. Several optimizations that can be made at compile time, during query plan generation, are discussed in [7, 9, 8]. However, the presented techniques are not applicable in the case where user queries and view definitions are arbitrary conjunctive queries. In particular, in [8], the presented optimization only considers a class of queries that is a proper subset of the class of union of conjunctive queries and that is not comparable with the class of conjunctive queries; there, the problem of optimizing query answering when the query over the sources is an arbitrary conjunctive query is left open.
In [6], the author addresses the issue of stability, i.e., determining whether the complete answer to a query (the one that would be obtained with no access limitations) can always be computed despite the access limitations.
Another relevant topic tightly connected with this research is the problem of run-time query plan optimization in the case where constraints over sources are asserted. In [1], functional and simple full-width inclusion dependencies have been addressed, and it is shown that the implication problem for such dependencies is decidable in polynomial time. There, a necessary and sufficient condition is presented that determines, given the dependencies, whether during query evaluation a planned access to a source is necessary for computing the answer.
In this paper we address the problem of query plan optimization for sources with limited capabilities for conjunctive queries and for unions of conjunctive queries. We present a technique to optimize a query plan at the time of its generation. Such an optimization technique exploits the knowledge about the structure of the query and the binding patterns of the sources to compute a query plan that eliminates dependencies between sources and thus avoids unnecessary accesses that may be performed at query plan execution time. Moreover, this allows one to exclude from the query plan those sources that cannot contribute to the result of the query.
The rest of the paper is organized as follows. In Section 2 we introduce the technical preliminaries. In Section 3 we present a technique to construct an optimized query plan for answering conjunctive queries in the presence of access limitations. We extend this technique to unions of conjunctive queries in Section 4. We conclude in Section 5, where we also indicate possible future directions of research. 2
We consider relations as sets of tuples of constants belonging to given domains and accessible via given binding patterns. Instead of using concrete domains, such as Integer or String, we deal with abstract domains, which have an underlying concrete domain, but represent information at a higher level of abstraction, which distinguishes, e.g., strings representing person names from strings representing plate numbers. A relational schema is a signature of the form r(A(1b|f), . . . , A(nb|f)), where r is the relation name, n is called the arity of the relation, each Ai is an abstract domain1, and the superscript, called the binding, indicates that the corresponding position in the relation is bound, if the binding is b, or free, if it is f ; the sequence of bindings for positions 1, . . . , n in the schema is called the binding pattern for r. In the following we will only indicate b bindings and will consider f as the default. A relation over a relational schema r(A[1b], . . . , A[nb]) is a set of tuples hc1, . . . , cni such that each ci is a constant belonging to abstract domain Ai. The binding pattern for a relation specifies which of the arguments of the relation must be bound by a constant in order to query the relation. For example, in relation r with schema r(A1, A2, Ab3), the first two arguments, corresponding resp. to abstract domains A1 and A2, are free, while the third argument, corresponding to A3, is bound.
A conjunctive query (CQ) q of arity n over a set R of relational schemata is written in the form
q(X1, . . . , Xn) ← conj (X1, . . . , Xn, Y1, . . . , Ym) where q(X1, . . . , Xn) is called the head of q, and conj (X1, . . . , Xn, Y1, . . . , Ym) is called the body of q. The body of q is a conjunction of atoms whose predicate symbols are in R, and that involve variables X1, . . . , Xn, Y1, . . . , Ym, and possibly some constants. We assume that the query is safe, i.e., that each variable Xj appears in at least one atom in the body.
Given a database DB , the answer qDB of q over DB is the set of tuples hc1, . . . , cni of constants in DB such that there are constants d1, . . . , dm for which each atom in conj (c1, . . . , cn, d1, . . . , dm) holds in DB .
A union of conjunctive queries (UoCQ) q of arity n over a set R of relational schemata is a set {q1, . . . , qk} of CQs, each with head predicate q and arity n. Given a database DB , the answer qDB of q over DB is the union of the answers to each conjunctive query qi in q.
In the presence of access limitations on the relations, we say that a tuple is obtainable in the answer to a query if there exists a query plan that retrieves it. A query plan is a sequence of valid accesses to the relations. By access we mean a request, sent to a relation, imposing a single specific value for some (possibly no) argument in the relation. An access is valid if the request imposes a value for each bound arguments; the response to a valid access is the (possibly empty) set of tuples in the relation that matches the request. We observe that, in order to retrieve all obtainable tuples, relations may need to be accessed in a particular order, as shown in the following example, adapted from [5].
Example 1. Suppose we have two relations: r1(Artist b, Nation), which stores artists with their nationality, and r2(Title, Year b, Artist ), which stores data 1 Note that we use a positional notation for relations, and that the Ais do not denote attributes. about songs. The query
q(T ) ← r1(A, italian), r2(T, 1998, A) asks for titles of songs interpreted by an Italian artist and produced in year 1998. Since r1 requires the first position to be bound to a constant, accessing it first would not be valid. However, we could use artist names extracted from r2 to access r1 and extract tuples that may contribute to the answer.
In [7] an algorithm is presented that, given a query over the relations, retrieves all the obtainable tuples in the answer to the query. Such an algorithm consists in the evaluation of a suitable Datalog program that extracts all obtainable tuples starting from a set of initial values. The Datalog program is constructed by encoding in Datalog clauses the limitations on the relations that must be respected during query evaluation. It is assumed that the strategy of enumerating all possible elements of a given domain to access a relation is not feasible and that, rather, the values for the bound positions of a relation are obtained either from constants in the query or from tuples retrieved from other relations. The evaluation of the Datalog program makes use of a set storing the values extracted from the relations (together with the constants appearing in the query) at a certain step, and of a cache that stores a partial copy of the relations, populated with the tuples extracted from the relations at a certain step. 1. Initialize B with the set of constants in the query 2. while there is a way of doing valid accesses with new constants (a) Access as many relations as possible, according to their binding patterns, using constants in B (b) Put the obtained tuples in the cache (c) Put the obtained constants in B 3. Evaluate the query over the cache
We call binding values the constants used to access a relation with access limitations; a binding tuple is a tuple, of the same arity as the number of bound arguments of a relation, whose values are binding values of the appropriate abstract domain that are used to access the same tuple. The algorithm extracts all tuples obtainable while respecting the binding patterns, performing a finite number of iterations of Step 2. Observe that there may be tuples in the relations that cannot be retrieved. We illustrate the extraction strategy by means of the following example.
Example 2. Consider the following set R of relational schemata Suppose we have the following conjunctive query over R:
R = { r1(Ab, C ), r2(C , B b), r3(B , C b) } q(B) ← r1(a1, C), r2(C, B) Now, assume a database in which the relations have the extension shown in Figure 1. Starting from a1, the only constant in the query, we access r1 getting the tuples ha1, c1i and ha1, c3i, whereas hc1, b1i in r2 is not (yet) accessible because of the binding patterns. But now we have c1 with which we can access r3 and retrieve hb2, c1i. With b2 we extract hc2, b2i from r2; then, with c2 we retrieve hb1, c2i from r3. Finally with b1 we extract hc1, b1i from r2 and obtain hb1i as the answer to q. Observe that ha3, c3i and hc3, b3i could not be extracted from r1 and r2 respectively and that answer hb3i is not obtainable. 3
Given a query q over a set of relations R, we want to construct a query plan that allows us to retrieve all obtainable answers to q. In this section we show how to generate an optimized query plan that avoids accesses that are not necessary for extracting all obtainable answers.
This problem has already been addressed for a subclass of UoCQs not covering CQs in [7, 8]. Building on a previous attempt to solve the problem for the full class of CQs [1], we improve on the techniques presented in [7] in two relevant directions.
– We consider queries that are in the full class of unions of conjunctive queries. – We exploit the knowledge about the structure of the query to exclude accesses that are unnecessary to answer the query.
With regard to the second issue, we observe that, having extracted a number of values at a certain point of the query answering process, and given a relation r to be accessed using the values extracted so far as binding values, some of the possible accesses to r may not be necessary in order to calculate the answer to the query. This is illustrated in the following example.
Example 3. Consider the following set R of relational schemata and the following CQ over R:
R = { r1(Ab, B ), r2(B b, C ), r3(C b, B ) } q(C) ← r1(a0, B), r2(B, C) We observe that r3 is not useful to answer the query. Using the values obtained from r2 to access r3 in order to obtain new values of domain B with which to access r2 again is pointless. Indeed, to the join condition between r1 and r2 guarantees that the only tuples extracted from r2 which can be used to construct a tuple of the answer to q are those obtained by binding the first argument of r2 with a value extracted from r1. 3.1
We want to be able to restrict our attention to queryable relations, i.e., the relations that can be accessed at least once for at least one database instance, starting from the values in the query.
Definition 1. Given a set R of relational schemata and a query q over R, a relation r in R is said to be queryable if there exist a database DB such that, starting from the constants in the query, there is a sequence of valid accesses to the relations in R such that r is eventually accessed.
Example 4. Let R be the following set of relational schemata: Given the query
R = { r1(Ab, B), r2(B b, C), r3(B, B, C b) } q() ← r3(X, Y, c1) we show that r2 and r3 are queryable. To do so, we exhibit a database in which the extensions of the relations is as follows.
Note that in the extraction process we start with the constant c1 and we are able to access r3, obtaining the tuple hb1, b2, c1i; then, with the constants b1 and b2 we access r2. This proves that r3 and r2 are queryable. Observe also that r1 is not queryable: whatever are the tuples in r2 and r3, we cannot extract in any way from r2 and r3 values that belong to the abstract domain of A, which would be necessary to access r1.
A correct and complete algorithm to calculate the queryable relations has been given in [7]. 3.2
We show now how to construct an optimized query plan for a CQ over some relations. We exclude a priori all non-queryable relations and therefore assume in the following that all the relations are queryable.
For our purposes, we define the dependency graph (or d-graph) of a CQ q with respect to a set R of relational schemata, denoted by GqR. A d-graph is the structure on which we operate in order to eliminate unnecessary accesses to the sources; then, an “optimized” version of the d-graph will be used to generate the query plan for q.
We will construct the graph starting from a query that contains no constant. We therefore first illustrate a preprocessing step that eliminates constants from the query as follows. For each constant a appearing in q in the position of a domain A, we introduce a new relation ra with a single free attribute, whose domain is that of A; the content of ra is the single tuple h i a . We then replace all occurrences of a appearing in the query in a position of domain A with a fresh new variable Xa, and we add the conjunct ra(Xa) to the body of q. The intuition is that a value acts as a relation whose content is completely known and accessible, and amounts only to the value itself.
The set GqR of nodes of the d-graph is determined as follows. For each atom in q, we have a set of nodes (called a source) in GqR, one for each argument of the corresponding relation. We call such nodes black. Moreover, for each relation not appearing in q, we have a set of nodes (also called a source), one for each argument of the relation. We call such nodes white. Both types of nodes have two labels: – The binding (“b” or “f”) of the corresponding argument in the relation. – The abstract domain of the corresponding argument in the relation. As for the arcs, GqR has an arc from a node u to a node v whenever the following three conditions hold: – u and v have the same abstract domain. – u is free. – v is bound.
Intuitively, the arcs denote dependencies between relation arguments, indicating that a relation with limited capabilities needs values which can be retrieved from other relations (or from constants in the query).
Our aim here is to optimize the set of arcs in GqR by removing dependencies that are actually not needed to retrieve all obtainable tuples.
For this purpose, let us indicate with outArcs(u, GqR) the set of outgoing arcs from a node in the same source as node u, for a d-graph GqR; we omit the second argument wherever the d-graph is understood. A sequence u1yv1, . . . , unyvn of arcs in GqR is called a dependency path (or d-path) for GqR if, for 2 ≤ i ≤ n, uiyvi ∈ outArcs(vi−1); to emphasize the first and last nodes in the sequence, the d-path can also be denoted u1y+ vn. Then, we can eliminate the arcs for which no d-path exists that reaches a black node, i.e., we must avoid accesses to relations that cannot provide values that can contribute to the answer.
Moreover, we may eliminate some arcs thanks to the presence of joins in the query. We say that an arc uyv is strong whenever (i ) both u and v are black, (ii ) u and v correspond to two variables which are joined in the query, and (iii ) v’s source is not needed to provide arbitrary values to other relations used in the query; all other arcs are called weak arcs. Now, in the presence of a strong arc, the join indicates that all the useful tuples that can be retrieved from v’s relation are extracted using only values coming from u. Therefore, whenever a node has an incoming strong arc, all the incoming weak arcs must be deleted, provided that this does not affect queryability of the relation as made precise below. We say that such weak arcs are dominated by the strong arc(s).
We say that a relation is free if all of its attributes are free; a source is free if all of its nodes correspond to free attributes. A bound node v in a d-graph is inductively defined as free-reachable, denoted as isFreeReachable(v), if either (i ) there is a weak arc uyv such that all bound nodes in u’s source are freereachable or (ii ) all strong arcs u1yv, . . ., unyv are such that all bound nodes in ui’s source are free-reachable, for 1 ≤ i ≤ n. Clearly, whenever the query is constant-free (like after the pre-processing step), a relation is queryable only if all of its bound nodes are free-reachable.
Let isBlack be a function that takes a node and returns true if and only if
the node is black, and let joined be a function that takes two nodes and returns
true if and only if the corresponding variables are joined in the query. Based
on the above observations, we characterize strong arcs and deleted arcs by the
following equations (
isStrong (uyv) = ¬isDeleted (uyv) ∧
isBlack (u) ∧ isBlack (v) ∧ joined (u, v) ∧
∀γ ∈ outArcs(v)(isStrong (γ) ∨ isDeleted (γ)) ∧
isFreeReachable(v)
isDeleted (uyv) = ¬isStrong (uyv) ∧
[isBlack (v) ∧ ∃(u0 6= u)(isStrong (u0yv)) ∨
¬isBlack (v) ∧ ∀γ ∈ outArcs(v)(isDeleted (γ))]
(
Ideally, for a given d-graph, we aim to determine two maximal sets
respectively of deleted arcs and strong arcs that satisfy the above equations. Let us
call candidate strong arc any arc whose nodes are black and whose corresponding
variables are joined in the query; let us indicate with arcs(GqR) the set of all arcs
in GqR and with cand(GqR) the set of all candidate strong arcs in GqR. Clearly,
(i ) only candidate strong arcs have the potential to become strong arcs and
(ii ) no candidate strong arc can ever be deleted, since, by definition, it reaches
a black node and is never dominated by another strong arc (for any given node
in GqR, its incoming arcs, if any, are either all strong or all weak). Therefore the
set of strong arcs and the set of deleted arcs must be disjoint; this is reflected
in the first conjunct of equation (
We call the pair (S, D) a solution for equations (
Proof. We first prove that a solution exists. Consider equations (
∀γ ∈ outArcs(v)(isStrong (γ) ∨ isDeleted (γ))
isDeleted (uyv) ≡ [isBlack (v) ∧ ∃u0(isStrong (u0yv))∨
¬isBlack (v) ∧ ∀γ ∈ outArcs(v)(isDeleted (γ))]
(
They induce the definition of two corresponding monotonic fixpoint operators
TS and TD. This in turn guarantees the existence of the greatest fixpoint for (
By Lemma 1, the largest set of strong arcs one can hope for is S0 = cand(G)\
circ(G), whereas the largest achievable set of deleted arcs is its complement
D0 = arcs(G) \ S0; clearly, S0 and D0 are disjoint. It now suffices to observe
that the fixpoint (Sω, Dω) for equations (
S , D0) is necessarily also a solution for equations (
To see that the maximal solution for (
Theorem 1 indicates that we can always find the largest sets of strong arcs and of deleted arcs possible for a given dependency graph. We present in Figure 2 an algorithm that determines such sets according to the above criteria. The algorithm calculates the initial sets of strong arcs (the non-circular candidate strong arcs) and deleted arcs (its complement) and then implements the TS and TD monotonic fixpoint operators used in the proof of Theorem 1 and applies them to the sets until a fixpoint is reached. This is stated below in Theorem 2, which trivially holds.
Theorem 2. The function calculateGFP(G) shown in Figure 2 computes the
maximal solution for equations (
An optimized d-graph generated via the result of the function calculateGFP trivially has the properties stated in Proposition 1 below.
Proposition 1. Consider an optimized d-graph GqR for a query q over a set R of relational schemata. We have that GqR has the following properties. 1. From each node in GqR it is possible to reach a black node through a d-path. 2. For each node u, its incoming arcs, if any, are either all strong or all weak. 3. There is no d-path that traverses a strong arc and successively a weak arc. 4. From every node of GqR, a free source is reachable through a d-path in reverse direction.
Example 5. Let R = {r1(Ab, B), r2(A, B b)} be a set of relational schemata and q(X) ← r1(a, X) a query over R. The d-graph GqR for q is shown in Figure 3, where we have named the sources as the corresponding relations, with a superscript indicating the occurrence number of that relation in the query. We first eliminate the constant a occurring in q by introducing a new relation ra with domain A and populated by the single tuple hai and by rewriting q as follows: q(X) ← ra(Y ), r1(Y, X).
Arc e1 is the only (non-circular) candidate strong arc and is, thus, in the initial
set of strong arcs; arcs e2 and e3 are therefore in the initial set of deleted arcs.
This is already the greatest fixpoint we were looking for, since equations (
calculateGFP (G : d-graph) : arc set × arc set
S := cand(G) \ circ(G) D := arcs(G) \ S do { (S0,D0) := (S,D) S := unmarkStrong(S0,D0,G)
D := unmarkDeleted(S0,D0,G) } while (S,D) 6= (S0,D0) return (S0,D0) unmarkStrong(S : arc set, D : arc set, G : d-graph) : arc set
S0 := S for each arc uyv ∈ S for each arc γ ∈ outArcs(v, G)
if (γ 6∈ S ∪ D) S0 := S0 \ {uyv}; break return S0 unmarkDeleted (S : arc set, D : arc set, G : d-graph) : arc set
D0 := D for each arc uyv ∈ D if (isBlack (v)) then bool strongExists := false for each arc u0yv0 ∈ S
if (v = v0) then strongExists := true ; break if (not strongExists) then D0 := D0 \ {uyv} else (v is white)
if (outArcs(v, G) \ D 6= ∅) then D0 := D0 \ {uyv} return D0 Now we come to the construction of the query plan. From the resulting optimized d-graph we construct the optimized query plan, expressed in Datalog notation, as shown in the algorithm of Figure 5. The Datalog program is evaluated according to the usual least fixpoint semantics; it is guaranteed by construction that the least fixpoint can be calculated by only making valid accesses.
The algorithm rewrites the original query over new versions of the relations in the body. For each predicate r in the body of the query, we introduce a new predicate with the same arity as r that acts as a sort of cache in which we store, during the query answering process, all the tuples extracted from r. This is done in step 1.2 of the algorithm of Figure 5. Note that different occurrences of the same predicate give rise to different names; in the examples we choose, e.g., to add a hat symbol to the predicate name as well as an occurrence number.
Each cache relation is defined in step 2 of the algorithm as the corresponding
original relation, but where each bound variable receives its binding values from
another new relation created for that purpose in step 2.3. Such relation takes
ra(
B A e2 e3 into account the arcs in the d-graph: if the corresponding incoming arcs are weak (resp., strong), then in step 2.3.2 (resp., step 2.3.3) the relation is defined as a disjunction (resp., conjunction) of the cache relations corresponding to the origin nodes, since any of them (resp., only their join) can provide binding values.
Finally, the program generated by the algorithm of Figure 5 is completed by adding a fact for each relation created in the preprocessing step to eliminate the constants from the query; the fact has the form ra(a), where ra is the created relation and a is the removed constant.
Example 6. We refer to Example 5. From the optimized dependency graph relative to q, the algorithm of Figure 5 generates the following plan: q(X) ← rˆa1(X), rˆ11(X, Y ) rˆa1(X1) ← ra(X1) rˆ1(X2, Y2) ← r1(X2, Y2), sX2 (X2) 1 sX2 (X2) ← rˆa1(X2)
ra(a) ← In this example, the support relation sX2 introduced by step 2.3.3 is defined as r1, since there is only one corresponding incoming strong arc. The third and a fourth rules could therefore more simply be written as the following single rule: rˆ11(X2, Y2) ← r1(X2, Y2), rˆa1(X2) The Datalog program above shows that relation r2, which could in principle provide useful values to r1, is not needed at all to answer the query because of the join between ra and r1.
ra(
B
A
Fig. 4. optimized d-graph for Example 5 INPUT: optimized d-graph GqR, query q, relations R OUTPUT: a Datalog program corresponding to the optimized query plan
We now state that the optimized query plan generated by our approach is both sound, i.e., it returns only tuples that are in the answer to the query, and complete, i.e., it does not miss any obtainable tuple, taking into account the binding patterns.
Theorem 4. Let q be a query over a set R of relational schemata, and let GqR be its d-graph and G = calculateGFP(GqR) the corresponding optimized d-graph. Then, the Datalog program constructed from q by the algorithm in Figure 5, based on G, computes all the answers to q obtainable from the relations in R, given the binding patterns on them. 4
In this section, we address the problem of finding a query plan for a UoCQ. Our approach is to transform a UoCQ into an appropriate CQ, so that the technique presented in Section 3 can be applied; the output is then adjusted so as to obtain a query plan for the original UoCQ (assumed, w.l.o.g., to be constant-free).
Let q be a constant-free UoCQ over a set R of relational schemata defined as follows: q(X1,1, . . . , Xn,1) ←
conj1 (X1,1, . . . , Xn,1, Y1,1, . . . , Yk,1), { { . . . . .
. q(X1,m, . . . , Xn,m) ←
conjm (X1,m, . . . , Xn,m, Y1,m, . . . , Yk,m) }
We first replace each rule in q with a variant thereof so that in the end all rules are standardized apart, as follows q(X10,1, . . . , Xn0,1) ←
conj1 (X10,1, . . . , Xn0,1, Y10,1, . . . , Yk0,1), q(X10,m, . . . , Xn0,m) ←
conjm (X10,m, . . . , Xn0,m, Y10,m, . . . , Yk0,m) } where each primed variable is a fresh new variable. Clearly, the expression above is equivalent to the original UoCQ.
We then generate the following CQ: q0(X10,1, ..., Xn0,1, ..., X10,m, ..., Xn0,m) ← conj1 (X10,1, ..., Xn0,1, Y10,1, ..., Yk0,1), . . . , conjm (X10,m, ..., Xn0,m, Y10,m, ..., Yk0,m)
Now we apply to q0 the technique developed for CQs in Section 3. We obtain as output a Datalog program Π whose first clause redefines q0 and has the following form: q0(X10,1, ..., Xn0,1, ..., X10,m, ..., Xn0,m) ← coˆnj 1 (X10,1, ..., Xn0,1, Y10,1, ..., Yk0,1), . . . , coˆnj m (X10,m, ..., Xn0,m, Y10,m, ..., Yk0,m) where the various coˆnji’s are as the conji’s, but refer to the cache relations instead, which are defined in the remainder of Π, which we denote as Π0.
Finally, from the rewritten query q0, we generate the following m rules. q(X10,1, ..., Xn0,1, ..., X10,m, ..., Xn0,m) ← q(X10,1, ..., Xn0,1, ..., X10,m, ..., Xn0,m) ← coˆnj 1 (X10,1, ..., Xn0,1, Y10,1, ..., Yk0,1) . . . , coˆnj m (X10,m, ..., Xn0,m, Y10,m, ..., Yk0,m) The above m rules together with Π0 constitute a Datalog program corresponding to an optimized query plan that computes all the answers to the original UoCQ q that are obtainable from the relations in R.
We have presented a technique that can be used to find all obtainable tuples belonging to the answer to a query formulated over relations with access limitations. Based on the binding patterns of a query, we construct a d-graph that indicates all possible ways in which bound arguments in a relation can receive useful values from free arguments with the same domain. The d-graph is optimized according to the joins included in the query and then used to generate a Datalog program that answers the query. The technique works for CQs as well as UoCQs.
Currently, we are working on an extension of our method to guarantee minimality of accesses; this requires considering the structure of the query in its entirety, including atoms that have no variable in common with the rest of the query. We are also aiming to cover full Datalog queries. The idea is that, before considering weak and strong arcs in the d-graph, one should take into account “unfolding” arcs, i.e., arcs that relate the arguments of an occurrence of an intensional predicate with the arguments of the predicates defining it.