We formally introduce ontology-based data federation (OBDF), to denote a framework combining ontology-based data access (OBDA) with a data federation layer, which virtually exposes multiple heterogeneous sources as a single relational database. In this setting, the SQL queries generated by the OBDA component by translating user SPARQL queries are further transformed by the data federation layer so as to be eficiently executed over the data sources. The structure of these SQL queries directly afects their execution time in the data federation layer and their optimization is crucial for performance. We propose here novel optimizations specific for OBDF, which are based on “hints” about existing data redundancies in the sources, empty join operations, and the need for materialized views. Such hints can be systematically inferred by analyzing the OBDA mappings and ontology and exploited to simplify the query structure. We also carry out an experimental evaluation in which we show the efectiveness of our optimizations.
Ontology-based data access (OBDA) [
T
SQL q
sub-queries V D
B
answers
answers
sub-answers
…
Sophisticated optimization techniques have been proposed and actually implemented in most
commercial and open source OBDA systems that are currently available [
So far, such techniques have been tailored towards optimizing queries that are executed over
a single data source to which the OBDA system is mapped. In many settings, however, there
is the need to virtually access multiple, possibly heterogeneous, data sources in an integrated
way. In this case, one can resort to data federation [
Data federation systems are already supported by OBDA systems, by accessing them as if they were a single relational data source2. However, to the best of our knowledge, in current OBDA systems no provision is taken for the optimization of the generated SQL query, to account for the fact that the evaluation of a SQL query in a data federation system is fundamentally diferent from query evaluation by a standard relational DBMS engine. Essentially, this is due to federated joins, i.e., joins that involve diferent data sources of the federation.
In this work, we consider specifically this setting, which we call Ontology-based Data Federation (OBDF), and provide the following contributions. (i) We formalize OBDF systems, where a collection of multiple, possibly heterogeneous and federated data sources are accessed via mappings from an ontology. (ii) We study query optimization in OBDF, by devising a set of optimization techniques specifically tailored towards federated data sources. (iii) We carry out an experimental evaluation in which we assess the efectiveness of the proposed optimizations.
Data Federation. We first formalize data federation, where multiple, possibly heterogeneous data sources are integrated in a unified view, usually called virtual database (VDB). A data source can be an RDB, a NoSQL DB, a CSV source, or of some other type, with the only requirement that it supports a query language. Given a set S = {1, . . . , } of sources to be federated, and a function (given implicitly with S) transforming the (possibly, non-relational) schema of each source into a corresponding relational schema Σ , a VDB schema (for S) is the disjoint union Σ = ⋃︀=1 Σ . In the following, we use letters , to denote database tables, and the subscript (e.g., ) to indicate that table belongs to source . A data federation 1E.g., Denodo (www.denodo.com), Dremio (www.dremio.com), and Teiid (teiid.io).
2See, e.g., ontop-vkg.org/tutorial/federation/. instance D for Σ is the relational instance ⋃︀ made of the union of all instances of the source schemas in Σ . For a query , ans(, D) denotes the set of answers of evaluated over the data federation instance D.
OBDF. Given an ontology , a VDB schema Σ for a set S of data sources, and a set ℳ of mappings from Σ to , an ontology-based data federation specification is the OBDA specification ℱ = ( , ℳ, Σ ). The notions of OBDF instance and answers to a query over an OBDF instance coincide with their OBDA counterpart. Figure 1 depicts the OBDF approach, where query answering is carried out by translating an input SPARQL query into a SQL query over the VDB, and then having the federation system evaluate such query.
Challenges. In OBDF, multiple sources are mapped to the same ontology, therefore the translated SQL query typically contains federated joins, i.e., joins involving diferent data sources. Computing such joins is expensive [13], since they cannot be evaluated locally and may cause large amounts of data to be transfered from the sources to the federation system. Besides, as also observed in our preliminary experiments, evaluating queries over ineficient sources (e.g., CSV files) slows down the overall query answering significantly. This problem is not addressed by optimization techniques in current OBDA systems, since they treat all tables present in the VDB schema in the same way. Therefore, new techniques to optimize query answering in OBDF are needed.
We study query optimization in OBDF, by devising a set of optimization techniques specifically tailored to federated data sources. We propose a set of “hints” based on empty federated joins, data redundancy, and materialized views, which can be pre-computed by analyzing the sources, the mappings, and the ontology, and we provide a novel optimized query unfolding algorithm that minimizes the number of federated joins and reduces the access to ineficient data sources. Method. The overall method consists of two parts: (1) an of-line hint pre-computation part, and (2) an on-line translation optimization part. We provide an algorithm to pre-compute the mentioned types of “hints”, based on a static analysis of the mappings and the ontology. The number of hints is bound to 2, where is the number of attributes in the DB schema. If the datasource is updated, then the hints are no-longer valid. Hence, our approach works best in mostly static scenarios, e.g., where new data undergoes a period of validation before being released.
Our concrete approach to query optimization consists of a set of query optimization rules that take into account the pre-computed hints, a simple cost model that distinguishes eficient/ineficient and static/dynamic data sources, and a novel optimized query unfolding algorithm that minimizes the number of federated joins and the access to ineficient data sources. Example. Consider an OBDF specification ℱ = ( , ℳ, Σ ) and a data federation instance D of Σ containing the static sources 1–4 to be federated. The VDB schema Σ contains, possibly among others, the following relation schemas, which are mapped to the ontology : Product1(id , name, reviewer ) for 1, Product2(num, nam, rew ) for 2 (where id and num are primary keys of Product1 and Product2 respectively) Person3(pid , pname) for 3, and PerInf4(id , name, address) for 4. We also assume to have the empty federated join hint Product1 ⋊⋉id=num Product2 =D ∅ and the redundancy hint pid,pname (Person3) ≡ D !,#,$,%# (( !/!' (Product1) ∪ !/#() (Product2) )⋈!*!+ ( !+/!',#/#,)- (Product1) ∪ !+/#(),#/#,) (Product2)) ⋈!+*!. ( !./!',$/$-/!-0-$ (Product1) ∪ !./#(),$/$-0(Product2)) ⋈$*%! ( %!/%!',%#/%#,)- (Person3) ∪ %!/!',%#/#,)- (PerInf4))) q !,#,$,%# (( !/!',!+/!',#/#,)- (Product1) ∪ !/#(),!+/#(),#/#,) (Product2)) ⋈!+*!. q1 ( !./!',$/$-/!-0-$ (Product1) ∪ !./#(),$/$-0(Product2)) ⋈$*%! ( %!/%!',%#/%#,)- (Person3) ∪ %!/!',%#/#,)- (PerInf4))) S?ExLaECPTro*dWuHcEt;RpEr{oName ?y; hasReviewer ?Qz. ?z preName ?n } !,#,$,%# ((!/!',#/#,)- ,$/$-/!-0-$ (Product1) ∪ q3 !,#,$,%# ( q2 !/#(),#/#,) ,$/$-0 (Product2)) ⋈$*%! ( !/!',#/#,)- ,$/$-/!-0-$ (Product1) ∪ !/#(),#/#,) ,$/$-0 (Product2)) ⋈$*%! (%!/%!',%#/%#,)- (Person3))) ( %!/%!',%#/%#,)- (Person3) ∪ %!/!',%#/#,)- (PerInf4))) pid/id,pname/name (PerInf4), and that 1, 2, and 3 are labelled as eficient , while 4 as ineficient.
Figure 2 illustrates how the above hints and labelling are exploited to unfold a SPARQL query . The translation proceeds as follows, where we assume that query operators are processed from left to right. (1) The federated join ⋊⋉=1 is first unfolded into a union of 4 joins and then traslated into /,1/id,/name(Product1) ∪ /num,1/num,/nam(Product2) on the basis of the empty federated join hint and the elimination of self-joins. (2) Similarly to the previous step, the intermediate query 1 is translated into 2. (3) Finally, on the basis of the data redundancy hint and the given source labeling, the union between Person3 and PerInf4 is removed, and only the projection over the eficient source Person3 is kept in the resulting query 3. Each step reduces the cost of .
Experimentation. We have carried out an extensive experiment to verify the efectiveness of the proposed optimizations, where we have employed main-stream DB engines (like PostgreSQL, MySQL, and MongoDB), the OBDA system Ontop, and the data federation engine Teiid. Based on the BSBM benchmark [14], we have created two OBDF specifications: a homogeneous one, where we have used as sources five relational databases, and a heterogeneous one, where some of these five data sources are translated into NoSQL DBs and CSV files. For scalability testing, we have generated three groups of instances using the BSBM data generation tool, setting the number of products to be 20K, 200K, and 2M, respectively. Thus, each OBDF specification has three instances. For space reasons, we show in Figure 3 only the results of evaluating the SQL translations of 12 SPARQL queries in BSBM for the instances with 200K and 2M products, where hom and het denote the results of evaluating the SQL queries translated by Ontop over the homogeneous and heterogeneous situation respectively, and homopt and hetopt denote the results of evaluating the optimized SQL queries over the two situations. From Figure 3, we can observe that our optimization strategies are efective for OBDF (e.g, for 200K products and 2, we observe a reduction from 2942.2 ms to 24.9 ms in query answering time for the homogeneous situation)
This research has been partially supported by the EU H2020 project INODE (grant agreement No. 863410), by the Italian PRIN project HOPE (2019-2022), by the Free University of BozenBolzano through the project MP4OBDA, and by the “Fusion Grant” project HIVE. D. Calvanese is supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation. We thank our colleagues, in particular Francesco Corcoglioniti, for their discussions and feedback. [12] L. M. Haas, E. T. Lin, M. A. Roth, Data integration through database federation, IBM
Systems J. 41 (2002) 578–596. [13] A. Schwarte, P. Haase, K. Hose, R. Schenkel, M. Schmidt, FedX: Optimization techniques for federated query processing on linked data, in: Proc. of the 10th Int. Semantic Web Conf. (ISWC), volume 7031 of Lecture Notes in Computer Science, Springer, 2011, pp. 601–616. [14] C. Bizer, A. Schultz, The Berlin SPARQL benchmark, Int. J. on Semantic Web and Information Systems 5 (2009) 1–24.