research-article

Towards Reconciling SPARQL and Certain Answers

Authors:

Shqiponja Ahmetaj,

Wolfgang Fischl,

Reinhard Pichler,

Mantas Šimkus,

Sebastian SkritekAuthors Info & Claims

WWW '15: Proceedings of the 24th International Conference on World Wide Web

Pages 23 - 33

https://doi.org/10.1145/2736277.2741636

Published: 18 May 2015 Publication History

Abstract

SPARQL entailment regimes are strongly influenced by the big body of works on ontology-based query answering, notably in the area of Description Logics (DLs). However, the semantics of query answering under SPARQL entailment regimes is defined in a more naive and much less expressive way than the certain answer semantics usually adopted in DLs. The goal of this work is to introduce an intuitive certain answer semantics also for SPARQL and to show the feasibility of this approach. For OWL 2 QL entailment, we present algorithms for the evaluation of an interesting fragment of SPARQL (the so-called well-designed SPARQL). Moreover, we show that the complexity of the most fundamental query analysis tasks (such as query containment and equivalence testing) is not negatively affected by the presence of OWL 2 QL entailment under the proposed semantics.

References

[1]

M. Arenas, G. Gottlob, and A. Pieris. Expressive languages for querying the semantic web. In Proc.,of PODS 2014, pages 14--26. ACM, 2014.

Digital Library

[2]

M. Arenas and J. Pérez. Querying semantic web data with SPARQL. In Proc.,of PODS 2011, pages 305--316. ACM, 2011.

Digital Library

[3]

F. Baader, D. Calvanese, D. L. McGuinness, D. Nardi, and P. F. Patel-Schneider, editors. The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press, 2003.

Digital Library

[4]

M. Bienvenu, T. Eiter, C. Lutz, M. Ortiz, and M.vSimkus. Query answering in the description logic $\mathcalS$. In Proc.,of DL 2010. CEUR-WS.org, 2010.

[5]

M. Bienvenu, M. Ortiz, M.vSimkus, and G. Xiao. Tractable queries for lightweight description logics. In Proc.,of IJCAI 2013. IJCAI/AAAI, 2013.

Digital Library

[6]

S. Bischof, M. Krötzsch, A. Polleres, and S. Rudolph. Schema-agnostic query rewriting in SPARQL 1.1. In Proc.,of ISWC 2014, pages 584--600. Springer, 2014.

Digital Library

[7]

D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, and R. Rosati. Tractable reasoning and efficient query answering in description logics: The DL-Lite family. J.,Autom.,Reasoning, 39(3):385--429, 2007.

Digital Library

[8]

A. K. Chandra and P. M. Merlin. Optimal implementation of conjunctive queries in relational data bases. In Proc.,of STOC 1977, pages 77--90. ACM, 1977.

Digital Library

[9]

T. Eiter, M. Ortiz, M.vSimkus, T. Tran, and G. Xiao. Query rewriting for Horn-SHIQ plus rules. In Proc.,of AAAI 2012. AAAI Press, 2012.

[10]

B. Glimm. Using SPARQL with RDFS and OWL entailment. In Reasoning Web 2011, Tutorial Lectures, pages 137--201. Springer, 2011.

Digital Library

[11]

B. Glimm, C. Lutz, I. Horrocks, and U. Sattler. Conjunctive query answering for the description logic SHIQ. J. Artif. Intell. Res. (JAIR), 31:157--204, 2008.

Digital Library

[12]

B. Glimm and C. Ogbuji. SPARQL 1.1 Entailment Regimes. W3C Recommendation, W3C, Mar. 2013. http://www.w3.org/TR/sparql11-entailment.

[13]

F. Goasdoué, I. Manolescu, and A. Roatis. Efficient query answering against dynamic RDF databases. In In Proc.,of EDBT 2013, pages 299--310. ACM, 2013.

Digital Library

[14]

I. Kollia and B. Glimm. Optimizing SPARQL query answering over OWL ontologies. J. Artif. Intell. Res. (JAIR), 48:253--303, 2013.

Digital Library

[15]

R. Kontchakov, C. Lutz, D. Toman, F. Wolter, and M. Zakharyaschev. The combined approach to query answering in DL-Lite. In Proc.,of KR 2010. AAAI Press, 2010.

[16]

R. Kontchakov, M. Rezk, M. Rodriguez-Muro, G. Xiao, and M. Zakharyaschev. Answering SPARQL queries over databases under OWL 2 QL entailment regime. In Proc.,of ISWC 2014, pages 552--567. Springer, 2014.

Digital Library

[17]

E. V. Kostylev and B. C. Grau. On the semantics of SPARQL queries with optional matching under entailment regimes. In Proc.,of ISWC 2014, pages 374--389. Springer, 2014.

Digital Library

[18]

E. V. Kostylev and J. L. Reutter. Answering counting aggregate queries over ontologies of the DL-Lite family. In Proc.,of AAAI 2013. AAAI Press, 2013.

[19]

A. Letelier, J. Pérez, R. Pichler, and S. Skritek. Static analysis and optimization of semantic web queries. ACM Trans. Database Syst., 38(4):25, 2013.

Digital Library

[20]

L. Libkin. Incomplete data: what went wrong, and how to fix it. In Proc.,PODS 2014, pages 1--13. ACM, 2014.

Digital Library

[21]

C. Lutz. The complexity of conjunctive query answering in expressive description logics. In Proc.,of IJCAR 2008, pages 179--193. Springer, 2008.

Digital Library

[22]

B. Motik, Y. Nenov, R. Piro, I. Horrocks, and D. Olteanu. Parallel materialisation of datalog programs in centralised, main-memory RDF systems. In Proc.,AAAI 2014, pages 129--137. AAAI Press, 2014.

[23]

M. Ortiz, D. Calvanese, and T. Eiter. Data complexity of query answering in expressive description logics via tableaux. Journal of Automated Reasoning, 41(1):61--98, 2008.

Digital Library

[24]

M. Ortiz, S. Rudolph, and M.vSimkus. Query answering in the horn fragments of the description logics SHOIQ and SROIQ. In Proc.,of IJCAI 2011, pages 1039--1044. IJCAI/AAAI, 2011.

Digital Library

[25]

J. Pérez, M. Arenas, and C. Gutierrez. Semantics and complexity of SPARQL. ACM Trans. Database Syst., 34(3), 2009.

Digital Library

[26]

R. Pichler and S. Skritek. Containment and equivalence of well-designed SPARQL. In Proc.,of PODS 2014, pages 39--50. ACM, 2014.

Digital Library

[27]

R. Rosati. On conjunctive query answering in EL. In Proc.,DL 2007. CEUR-WS.org, 2007.

[28]

R. Rosati and A. Almatelli. Improving query answering over DL-Lite ontologies. In Proc.,of KR 2010. AAAI Press, 2010.

[29]

M. Schmidt, M. Meier, and G. Lausen. Foundations of SPARQL query optimization. In Proc.,of ICDT 2010, pages 4--33. ACM, 2010.

Digital Library

[30]

J. F. Sequeda, M. Arenas, and D. P. Miranker. OBDA: query rewriting or materialization? In practice, both! In Proc.,of ISWC 2014, pages 535--551. Springer, 2014.

Digital Library

Cited By

Console MGuagliardo PLibkin LToussaint ESuciu DTao YWei Z(2020)Coping with Incomplete Data: Recent AdvancesProceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3375395.3387970(33-47)Online publication date: 14-Jun-2020
https://dl.acm.org/doi/10.1145/3375395.3387970
Lenzerini MLepore LPoggi A(2020)Metamodeling and metaquerying in OWL2QLArtificial Intelligence10.1016/j.artint.2020.103432(103432)Online publication date: Nov-2020
https://doi.org/10.1016/j.artint.2020.103432
Ahmetaj S(2020)Rewriting Approaches for Ontology-Mediated Query AnsweringKI - Künstliche Intelligenz10.1007/s13218-020-00671-wOnline publication date: 11-Jun-2020
https://doi.org/10.1007/s13218-020-00671-w
Show More Cited By

Index Terms

Towards Reconciling SPARQL and Certain Answers
1. Computer systems organization
  1. Architectures
    1. Other architectures
      1. Heterogeneous (hybrid) systems
2. Information systems
  1. Data management systems

Recommendations

Foundations of SPARQL query optimization
ICDT '10: Proceedings of the 13th International Conference on Database Theory

We study fundamental aspects related to the efficient processing of the SPARQL query language for RDF, proposed by the W3C to encode machine-readable information in the Semantic Web. Our key contributions are (i) a complete complexity analysis for all ...
Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite Family

We propose a new family of description logics (DLs), called DL-Lite , specifically tailored to capture basic ontology languages, while keeping low complexity of reasoning. Reasoning here means not only computing subsumption between concepts and ...
Optimized query rewriting for OWL 2 QL
CADE'11: Proceedings of the 23rd international conference on Automated deduction

The OWL 2 QL profile has been designed to facilitate query answering via query rewriting. This paper presents an optimized query rewriting algorithm which takes advantage of the special characteristics of the query rewriting problem via first-order ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

WWW '15: Proceedings of the 24th International Conference on World Wide Web

May 2015

1460 pages

ISBN:9781450334693

General Chairs:
Aldo Gangemi
National Research Council, Italy & Paris 13 University-CNRS, France
,
Stefano Leonardi
Sapienza University of Rome, Italy
,
Alessandro Panconesi
Sapienza University of Rome, Italy

Copyright © 2015 Copyright is held by the International World Wide Web Conference Committee (IW3C2).

Sponsors

IW3C2: International World Wide Web Conference Committee

In-Cooperation

SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web

Publisher

International World Wide Web Conferences Steering Committee

Republic and Canton of Geneva, Switzerland

Publication History

Published: 18 May 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Vienna Science and Technology Fund (WWTF)
Austrian Science Fund (FWF)

Conference

WWW '15

Sponsor:

IW3C2

WWW '15: 24th International World Wide Web Conference

May 18 - 22, 2015

Florence, Italy

Acceptance Rates

WWW '15 Paper Acceptance Rate 131 of 929 submissions, 14%;

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

30
Total Citations
View Citations
314
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)1

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Console MGuagliardo PLibkin LToussaint ESuciu DTao YWei Z(2020)Coping with Incomplete Data: Recent AdvancesProceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3375395.3387970(33-47)Online publication date: 14-Jun-2020
https://dl.acm.org/doi/10.1145/3375395.3387970
Lenzerini MLepore LPoggi A(2020)Metamodeling and metaquerying in OWL2QLArtificial Intelligence10.1016/j.artint.2020.103432(103432)Online publication date: Nov-2020
https://doi.org/10.1016/j.artint.2020.103432
Ahmetaj S(2020)Rewriting Approaches for Ontology-Mediated Query AnsweringKI - Künstliche Intelligenz10.1007/s13218-020-00671-wOnline publication date: 11-Jun-2020
https://doi.org/10.1007/s13218-020-00671-w
Corman JXiao G(2020)Certain Answers to a sparql Query over a Knowledge BaseSemantic Technology10.1007/978-3-030-41407-8_21(320-335)Online publication date: 14-Feb-2020
https://doi.org/10.1007/978-3-030-41407-8_21
Pujol-Tost L(2019)Did We Just Travel to the Past? Building and Evaluating With Cultural Presence Different Modes of VR-Mediated Experiences in Virtual ArchaeologyJournal on Computing and Cultural Heritage 10.1145/323067812:1(1-20)Online publication date: 13-Feb-2019
https://dl.acm.org/doi/10.1145/3230678
Amendola GLibkin L(2018)Explainable certain answersProceedings of the 27th International Joint Conference on Artificial Intelligence10.5555/3304889.3304893(1683-1690)Online publication date: 13-Jul-2018
https://dl.acm.org/doi/10.5555/3304889.3304893
Liu SFan HNiu XNg HChu YLUK W(2018)Optimizing CNN-based Segmentation with Deeply Customized Convolutional and Deconvolutional Architectures on FPGAACM Transactions on Reconfigurable Technology and Systems10.1145/324290011:3(1-22)Online publication date: 20-Dec-2018
https://dl.acm.org/doi/10.1145/3242900
Boutros AYazdanshenas SBetz V(2018)You Cannot Improve What You Do not MeasureACM Transactions on Reconfigurable Technology and Systems10.1145/324289811:3(1-23)Online publication date: 12-Dec-2018
https://dl.acm.org/doi/10.1145/3242898
Muller SAcar UHarper R(2018)Competitive parallelism: getting your priorities rightProceedings of the ACM on Programming Languages10.1145/32367902:ICFP(1-30)Online publication date: 30-Jul-2018
https://dl.acm.org/doi/10.1145/3236790
Barceló PKröll MPichler RSkritek S(2018)Efficient Evaluation and Static Analysis for Well-Designed Pattern Trees with ProjectionACM Transactions on Database Systems10.1145/323398343:2(1-44)Online publication date: 21-Aug-2018
https://dl.acm.org/doi/10.1145/3233983
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents