GUN: An efficient execution strategy for querying the web of data

Gabriela Montoya, Luis Daniel Ibáñez, Hala Skaf-Molli, Pascal Molli, Maria Esther Vidal

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

1 Citation (Scopus)

Abstract

Local-As-View (LAV) mediators provide a uniform interface to a federation of heterogeneous data sources to attempt the execution of queries against the federation. LAV mediators rely on query rewriters to translate mediator queries into equivalent queries on the federated data sources. The query rewriting problem in LAV mediators has shown to be NP-complete, and there may be an exponential number of rewritings, making unfeasible the execution or even generation of all the rewritings for some queries. The complexity of this problem can be particularly impacted when queries and data sources are described using SPARQL conjunctive queries, for which millions of rewritings could be generated. We aim at providing an efficient solution to the problem of executing LAV SPARQL query rewritings while the gathered answer is as complete as possible. We formulate the Result-Maximal k-Execution problem (ReMakE) as the problem of maximizing the query results obtained from the execution of only k rewritings. Additionally, a novel query execution strategy called GUN is proposed to solve the ReMakE problem. Our experimental evaluation demonstrates that GUN outperforms traditional techniques in terms of answer completeness and execution time.

Original languageEnglish
Title of host publicationDatabase and Expert Systems Applications - 24th International Conference, DEXA 2013, Proceedings
Number of pages15
Publication date25 Sep 2013
EditionPART 1
Pages180-194
ISBN (Print)9783642402845
DOIs
Publication statusPublished - 25 Sep 2013
Event24th International Conference on Database and Expert Systems Applications, DEXA 2013 - Prague, Czech Republic
Duration: 26 Aug 201329 Aug 2013

Conference

Conference24th International Conference on Database and Expert Systems Applications, DEXA 2013
Country/TerritoryCzech Republic
CityPrague
Period26/08/201329/08/2013
SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume8055 LNCS
ISSN0302-9743

Fingerprint

Dive into the research topics of 'GUN: An efficient execution strategy for querying the web of data'. Together they form a unique fingerprint.

Cite this