Redundant data processing is a key problem in SPARQL to SQL query translation in Ontology Based Data Access (OBDA) systems. Many optimizations that aim to minimize this problem have been proposed and implemented. However, a large number of redundant duplicate answers are still generated in many practical settings, and this is a factor that impacts query execution. In this work we identify speci c query traits that lead to duplicate introduction and we track down the mappings that are responsible for this behavior. Through experimental evaluation using the OBDA system Ontop, we exhibit the bene ts of early duplicate elimination and show how to incorporate this technique into query optimization decisions.
Ontology Based Data Access (OBDA) is an approach for data integration in which an ontology is linked to underlying data sources through mappings. An end user can pose queries over the ontology, which we assume to represent a familiar vocabulary and conceptualization of the user domain. The OBDA system automatically translates the query and sends it for execution to the underlying data sources, providing the end user with a convenient abstraction over possibly complex schemas and details about the data storage and query processing. The query translation involves query rewriting, where the initial query is transformed in order to take into consideration the ontology axioms, and query unfolding where the rewritten query is transformed into another query expressed in the query language of the underlying data sources. In what follows we consider an OBDA setting, where an OWL ontology is linked through mappings to data stored in a relational database management system (RDBMS) providing the user with access to a virtual RDF graph. The original query is expressed over this virtual RDF graph in the SPARQL query language, and the result of rewriting and unfolding is a SQL query. As an example consider the relational table from Figure 1a and the mapping from Figure 1c. In this mapping hasDirector is a property de ned in the ontology, whereas f and g are functions responsible for constructing an object that acts as an ontology instance out of values occurring in the database. In our setting, they construct an RDF term represented by an IRI.
If an RDF graph is lean (i.e., if it has no instance which is a proper subgraph of itself), evaluation of a basic graph pattern on this graph can never result in duplicate answers [7]. However, duplicates in SPARQL query evaluation can be introduced from the operations of projection and union. Therefore, it is crucial that SQL query fragments resulting from the translation of basic graph patterns are also duplicate-free when evaluated in a source database. Note also that, as there is no restriction regarding the multiplicity of the results of SQL queries used in a mapping, duplicates may be introduced even during evaluation of a single triple pattern.
In this setting, duplicates are redundant answers whose impact can be detrimental for query evaluation, as the size of intermediate results can increase exponentially in the number of triple patterns, in a query that involves several joins. Even if the nal SQL query produced by an OBDA system dictates that the result should be duplicate-free using the SQL DISTINCT or UNION keyword, relational systems rarely consider early duplicate elimination (DE) in order to limit the size of intermediate results, but only perform the task on the nal query result. This behavior is justi ed by the fact that DE is a costly blocking operation [1] and also that the SQL queries are usually formulated by expert users who take into consideration the integrity constraints of normalized relational schemas. Under these assumptions, considering early DE options during optimization is not usually regarded worthy. Contrary to this situation for SQL queries, it has been ascertained [4] that in real world OBDA settings, duplicate answers frequently dominate query results and also that this appears as \noise" to end users that might be using a visual query formulation tool. In what follows we brie y identify reasons for this behavior.
In a normalized relational schema duplicates usually show up in SQL queries due to projections. As long as an OBDA mapping that generates virtual triples uses a column or combination of columns whose values are unique, e.g. a primary key of a table as the subject or object of each triple, then all triples coming from this mapping will be distinct. However, a denormalized schema or mappings that do not use unique columns can lead to duplicate introduction even during evaluation of a single triple pattern. One more case in which duplicates are introduced has to do with the use of property rdf :type. Mappings de ning rdf :type property should also be duplicate-free, but as OBDA systems employ reasoning with respect to domain and range of properties, part of the mapping that de nes a property could be used for evaluating a triple pattern with rdf :type. Then the other part of the mapping is projected out, which can lead to a large number of duplicates as illustrated in Example 1.
Example 1. Consider the mapping from Figure 1c and also that the ontology de nes the range of property hasDirector to be the class Director. Now consider a triple pattern ?x rdf :type Director that asks for the entities that belong to the class Director. One way to obtain such entities is to use the entities participating as objects to the property hasDirector. As we are not interested in the subjects of the generated triples, we are projecting out the title column, adding only a
SELECT ' IRI ' j j d i r e c t o r FROM movies
WHERE t i t l e IS NOT NULL (a) Table movies(title, director) (b) SQL query movies(t; d) ! hasDirector(f(t); g(d))
(c) Example Mapping condition that this column should not be null. The resulting SQL to be sent for evaluation is shown in Figure 1b.
This can become a heavy burden for query evaluation, especially when the query involves several joins, as all these duplicate values need to be joined with other tables, that may as well contain redundant values, and as a result, the overall cost can be increased by orders of magnitude, depending on the exact number of duplicates. A second issue is that, as the nal answers need to be distinct, DE has to be performed on the nal query result that consists of tuples of RDF terms instead of database values, making the relational engine perform this over (usually large) unindexed string values.
In this work we present e cient solutions to the described problems, considering ontologies belonging to the OWL 2 QL language, as the W3C recommendation for query answering against datasets stored in relational back-ends. We start by providing some preliminaries regarding ontologies, mappings and relational databases (Section 2) and then proceed to describe a process, that given an initial mapping collection, identi es the (possibly modi ed) mapping assertions which are responsible for introduction of duplicates (Section 3). Duplicate-free results of these assertions can be materialized o ine and replace the original assertions during query execution. In case materialized views are not a viable option, for example because of read-only access to data or for e ciency reasons, we proceed to deal with the problem of duplicates during query execution.
In Section 4, we describe how a structural optimization of pushing DE before IRI construction can be applied and obtain an equivalent query with the one produced during unfolding. Then, in Section 5 we propose a heuristic that can help an OBDA system acting outside the relational engine to take decisions regarding the DE of intermediate results. Having implemented our optimizations in the state of the art OBDA system Ontop [9], in Section 6 we present their impact on NPD and LUBM benchmarks using four di erent relational back-ends. Speci cally we show that duplicates are present in many mappings from both benchmarks and that speci c queries are heavily impacted by this fact, leading to evaluation times of more than 20 minutes, which in some cases can be reduced to a few seconds. Excluding the queries that give a timeout in the unoptimized setting, the overall improvement for the rest of the queries can be more than 60%. Finally, we evaluate our heuristic and show that its usage is justi ed and that for query mixes from the two benchmarks, such that low selectivity queries do not dominate execution time, it can lead to overall improvement of up to 25%. 2
We consider the following pairwise disjoint alphabets: O of ontology predicates,
R of database relation predicates, Const of constants, V ar of variables and of function symbols where each function symbol has an associated arity. We also consider that Const is partitioned into DBConst of database constants and OConst of ontology constants. As in [8], we use functions with symbols from in order to solve the so called impedance mismatch problem of constructing ontology objects from values occurring in the database.
Databases and Queries. We start by giving de nitions for database instances and queries over them, following the bag semantics from [2]. A bag B is a pair (A; ), where A is a set called the underlying set of B and is a function from elements of A to the positive integers, which gives the multiplicities of elements of A in B. The underlying set of a bag B will be denoted by U SB. A relation instance is a bag of tuples of xed arity using constants from DBConst. A source schema S is a set of relation names from R. A database instance D for a source schema S is a mapping from relation names in S to relation instances.
A SQL query over a relational schema S is an expression of form: Query(x) , where is a rst order expression containing predicates from R, which are among the relations that belong to S, Query 2 R, Query 62 S and x is a vector of constants from DBConst and variables from V ar that appear in . A conjunctive query CQ over a relational schema S is a SQL query, where has the form R1(x1) ^ ::: ^ Rn(xn), where x1; :::; xn are vectors of constants from DBConst and variables from V ar, and R1; :::; Rn 2 S. Variables from x1; :::; xn that do not appear in x are existentially quanti ed, but we omit the quanti ers in order to simplify the reading. CQs roughly correspond to SQL Select-FromWhere queries. Let q be the SQL query Query(x) , we will denote by Qi(q) the query resulting from the projection of the i-th answer term of q, that is the query: Query(xi) . The duplicate-tuple ratio DT RR of a relation instance R is equal to Pt2jUUSSRRj (t) . A relation instance with DT R equal to 1, will be called a duplicate-free relation instance.
Later on, in Section 3, when we will want to see if the result of a mapping assertion is duplicate-free, we will use the following important proposition of [6]: Proposition 1. Let Q be a conjunctive query over a source schema S. Then, if for each Ri(ui) in the body of Q there is a key dependency X ! Y in S and for each element uij 2 X (R(ui)), either uij 2 DBConst or uij appears in Query(x), then the result of Query(x) is a duplicate-free relation instance on any database instance for S.
Ontology and Mappings. A T Box is a nite set of ontology axioms. An ABox is a nite set of membership assertions A( ) or role lling assertions P ( ; 0), where ; 0 2 OConst and A; P 2 O denote a concept name and role name respectively. A DL ontology O is a pair hT ; Ai where T is a T Box and A an
A mapping assertion m from a source schema S to a T Box T has the form: (x) ! , where (x) will be denoted by body(m) and it is a SQL query over a database instance D, has the form P (cc1(x1); cc2(x2)) or C(cc1(x1)) with P ( respectively C) 2 O a property (respectively concept) name, and each ccj 2 is a function with arity equal to the length of xj and range a subset of OConst. All variables in also appear in x. The right hand side will be denoted by head(m). A mapping M is a nite set of such mapping assertions. Note that according to this de nition, in this paper we consider only global-as-view (GAV) mappings. We will use the symbol MCQ to denote the assertions from M whose body is a CQ over the database schema.
In correspondence with CQs over a relational schema, we de ne a CQ over an ontology O as an expression of the form: Query(x) P1(x1) ^ ::: ^ Pn(xn) where x1; :::; xn are vectors of constants from OConst and variables from V ar, x is a vector of constants from OConst and variables from V ar that appear in x1; :::; xn, and P1; :::; Pn 2 O are ontology predicates that appear in O. A union of conjunctive queries U CQ over an ontology O is an expression of the form Query(x) CQ1(x) _ ::: _ CQn(x), where each CQi for i = 1:::n is an expression of the form P1i(xi1) ^ ::: ^ Pni (xin) as in the previous de nition.
Query Rewriting and Unfolding As we mentioned in Section 1, query answering in OBDA involves query rewriting and query unfolding. During query rewriting, an initial CQ over an ontology is rewritten in order to take into consideration the ontological axioms. The result of this process is a query, that when posed over the ABox (that is by disregarding all the ontological axioms), will return the same answers as the initial query posed over the ontology. This is done using the notion of certain answers, that is answers present in every model of the ontology [8]. We omit details, as in this work we mainly consider the result query of this process. We just need to note that several methods exist for query rewriting over OWL 2 QL ontologies. In this work we consider that the result of this step is a UCQ over the ontology.
Regarding query unfolding with respect to a mapping M, a method based on partial Datalog evaluation with functional terms is presented in [8]. As before, we omit a detailed description and note that the result of this process is a query over the relational schema that has the form
Query(x) Q1(x) _ ::: _ Qn(x) (
O ine DE
One solution to the problem of duplicates, is to track down the mapping assertions which are responsible for duplicates, create materialized views with the distinct results, possibly with indexes, and then use these views instead of the original assertions during query unfolding. It is reasonable to expect that this solution will give the best performance during query execution, but on the other hand this incurs expensive preprocessing and also, using materialized views in the database increases the database maintenance load, especially for frequently updated tables, as well as the database size. Also, this solution will not take into consideration duplicates due to projections in the SPARQL query and nally, it is not in line with the overall approach of providing the end user with access to several underlying data sources, without the need to modify data, and on a practical level, such access may not be even possible. Nevertheless, even in the case where one chooses to use materialized views, it is not straightforward exactly which of the mapping assertions should be chosen. In the rest of this section we describe a process to nd the exact assertions for this setting, whereas in the following sections we consider the case where no materialization happens and all processing needs to be done during query execution.
Given a mapping M and a database instance D over a schema S, a straightforward solution is to materialize all m 2 M such that DT Rhead(m)(D) > 1, but as the query produced after rewriting takes into consideration the ontology axioms, implied assertions may be used, such that a speci c variable has been projected out from the outputs of the body of an existing assertion due to reasoning for class instances with respect to domain or range of a property. Situations like this can be identi ed o ine, by analyzing the ontology and the original mapping. The rst step is to nd the ontology axioms of the form 9P:> v C and 9P :> v C (or equivalently > v 8P:C) that de ne the domain and range of some property P to be a class C in our ontology. Then we identify the mapping assertion in M that generates RDF triples which have as predicate the property P and we modify the target SQL query of the mapping, by projecting out the columns used for the subject or object respectively. At this point, we can skip certain mappings that are covered by the corresponding rdf :type mapping for a given class, as OBDA systems eliminate the usage of the property triple pattern for these cases based on foreign key relationships [9]. Consider again the case of Example 1: if we had one more database table director inf o which has a primary key id and we also know that director in movies is a foreign key that references this primary key, then if we also had the mapping director inf o(id; :::) ! Director(f (id)) the previously obtained mapping can be skipped as it is redundant and will not be used by the OBDA system.
The method is described in Algorithm 1. ComputeDT R is a function that returns the DTR for the query passed as argument. If DT R = 1 according to proposition 1, then access to data in order to collect statistical information is avoided altogether, otherwise the actual DTR is computed by sending two count queries: with and without the distinct modi er. Later, when the DTR needs to be determined during query optimization, an estimation based on data Algorithm 1: Track down SQL queries that contain duplicates summarization is used instead (Section 5). Function ExistsF K returns true if a foreign key exists between the output column of the query passed as second argument and the output column of the query passed as third argument. The result of this algorithm is a set of mapping assertions, possibly annotated with information about the projection of a column. Modi cation of the produced SQL query in order to take into consideration the views created for these mappings, instead of the original body of the mapping, can simply be performed in the nal step of the query unfolding, where each Auxj is replaced by the corresponding SQL, and as a result it is independent of the query rewriting method. 4
In SPARQL to SQL approaches, pushing joins inside unions is a well known
structural optimization, so that joins over IRIs are avoided and relational columns,
whose values are possibly indexed, are used instead. Methods for unfolding based
in partial datalog evaluation (see Section 2) produce such queries, where
additionally, union subqueries that contain joins between incompatible IRIs, that
when evaluated will produce an empty result, are completely discarded. In a
similar manner, it can be very useful to perform DE before IRI construction. In
this section we discuss the process of transforming the unfolded query that has
the form shown in formula (
Query(x) U CQ1(x) _ ::: _ U CQl(x) (
U CQi(fi(vi)) Qi1(vi) _ ::: _ Qli(vi) (
Qij (vi) Aux1(vi1) ^ ::: ^ Auxn(vik) ^ EQ: (
In this section we consider a query that has the form shown in formula (
As a result, we can consider that each union subquery has the form
Q(x) Aux1(x1) ^ ::: ^ Auxn(xn) ^ R1(xn+1) ^ ::: ^ Rm(xn+m) (
Let us suppose for now that we have a single SQL subquery coming from the translation of a SPARQL query and we have to take the decision regarding a single input table (either \real" primitive table or virtual view) used in this subquery. In this case, it may be bene cial to dictate the RDBMS to perform the DE on projection query of the speci c input table at the beginning of query execution, store the duplicate-free intermediate result in a temporary table and use it for the speci c query. This can be done in several ways depending on the exact SQL dialect and capabilities of the underlying system. For example one can use (non-recursive) common table expressions or temporary table de nitions. Of course the exact decisions as to when this should happen depend on several factors, including the exact query, the DTR of the projection query of the input table, the number of uses of the speci c input table in the query, the choice to save the temporary table on disk or keep it in memory and several other factors that depend on the database physical design, database tuning parameters, the exact query execution plan and the evaluation methods chosen by the optimizer of the RDBMS. Uncertainty about query execution costs is an inherent problem in data integration and as the OBDA system operates outside the database engine, knowing all these factors is di cult or even impossible. In what follows, we propose to take this decision according to a heuristic that depends only on the size of the data and the DTR of the input table, whose estimation can be obtained using data summarization.
The main assumption that we make and will help us take decisions regarding DE states that the impact of an input table with DTR equal to a constant number n in the number of tuples of the nal query result is proportional to n. As a result of this assumption, the selectivity of the query plays the most important role regarding the DE decisions. Intuitively, a query whose result size is much larger than the size of the intermediate result for which we examine the DE option, it is expected to be faster if we rst perform the elimination, as each tuple of the intermediate result has as impact the creation of a large number of tuples in the nal result. On the other hand, when we have very selective queries with few results, whereas the size of the intermediate result under consideration is much larger, one would expect that each tuple of the intermediate result does not add that much to the total cost of the query in order to counterbalance the cost of a DE, especially when expecting the optimizer to limit the sizes of intermediate query results as soon as possible.
>
A Heuristic Regarding DE. Given a database instance D, a query q that has
the form (
where relation instance Ans is the result of the projection query of Ii(xi) from q on D and SizeQ and SizeAns are the estimated sizes of relation instances Q and Ans respectively. That is, DE should be performed if it is expected that the reduction on the size of the nal result will be bigger than the size of the intermediate result with DE.
When more than one input tables with DT R > 1 exist for a query a greedy approach is used, choosing at rst the one that gives the biggest gain according to the heuristic (considering the heuristic as a fraction instead of an inequality). Then the chosen input table is excluded and a new estimation for the nal result is made, considering that DE is performed on the chosen input table and this step is repeated until none of the rest input tables gives gain according to the heuristic. Also, when dealing with multiple subqueries of a UNION query the heuristic must be modi ed such that the left hand side is replaced by a sum over all subqueries. Details can be found in a technical report available online1. 6
We have implemented all the described optimizations in an prototype extension of Ontop version 1.18.0. Our extension is available in github2, as a fork of the o cial Ontop repository. All experiments were carried out on a machine with an Intel Core i7-3770K processor with 8 cores and 16 GB of RAM running UBUNTU 16.04. As our intention was to examine how our optimizations perform in di erent underlying systems, we used four di erent back-ends: PostgreSQL (version 9.3), MySQL (version 5.7) and two of the most widely used proprietary RDBM systems, which due to their license we will call System I and System X. We have performed an experimental evaluation of our techniques using the LUBM [3] and NPD [5] benchmarks. For LUBM benchmark in total 84 mapping assertions were produced as T -Mappings from Ontop. Out of these, we only needed to make DTR estimations using statistics for 15, as we found all the others to have DTR=1 according to Proposition 1. O ine gathering and building of statistics for the columns referenced in the candidate mapping assertions took 28 sec. Making DTR estimations for the result of the 15 mappings took less that 0.5 seconds. For NPD, out of 1091 produced assertions in T -Mappings 1 https://github.com/dbilid/ontop/tree/version3/results/de-tech.pdf 2 https://github.com/dbilid/ontop 112 where found to have DT R > 1. Building statistics took 45 sec. and making DTR estimations about 2 sec.
E ects of Early DE. We examined the e ect of early DE on several queries from these two benchmarks such that our optimization is applicable. In order to isolate the impact of early DE, we executed the queries with the optimization for pushing IRI construction before DE disabled. Results for all systems are presented in Table 1, where SI-D stands for System-I with only early DE enabled and SI for the execution without any optimization in System I. Same holds for System X (SX), PostgreSQL (PG) and MySQL (MS). For all systems, queries for both settings produced identical results. All produced queries are available in github. From the results we can see that the impact of early DE varies depending on each query and each system. For example, in query USER19 (from [10] coming from user requirements), the decision leads to a slight increase in execution time for both systems I and X, but it is very bene cial for PostgreSQL. On a closer inspection, we saw that both these systems do take advantage of early DE opportunities in some cases, such as when distinct rows can be obtained without extra e ort using an index of a base table for all projected columns. Learning exactly when these system consider early DE can lead to even larger improvement, if it is taken into consideration from our method as system-speci c optimization. In any case, from our experiments it seems that even these systems miss many opportunities for early DE that lead to better plans and certainly do not consider using the same duplicate elimination result for di erent union subqueries. As a result, even with the system-agnostic version, our method e ectively eliminates most timeouts. Even in System X, where no timeout occurs in the unoptimized setting, early DE alone leads to a decrease of 38% in total execution time.
We have also evaluated our DE heuristic by applying extra lters in several query fragments upon which DE is applicable, in order to test our heuristic with di erent selectivities. We have executed these queries following three di erent strategies regarding DE: always-perform, never-perform and perform according to heuristic. The never-perform has the worst performance overall due to low selectivity queries dominating the execution times, but it is often better than never-perform for highly selective queries. Our heuristic is always better from the other two strategies on average for all tested queries, leading to an improvement of up to 25% for query mixes where low selectivity queries do not dominate execution time.