research-article

How many and what types of SPARQL queries can be answered through zero-knowledge link traversal?

Authors:

Pavlos Fafalios,

Yannis TzitzikasAuthors Info & Claims

SAC '19: Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing

Pages 2267 - 2274

https://doi.org/10.1145/3297280.3297505

Published: 08 April 2019 Publication History

Abstract

The current de-facto way to query the Web of Data is through the SPARQL protocol, where a client sends queries to a server through a SPARQL endpoint. Contrary to an HTTP server, providing and maintaining a robust and reliable endpoint requires a significant effort that not all publishers are willing or able to make. An alternative query evaluation method is through link traversal, where a query is answered by dereferencing online web resources (URIs) at real time. While several approaches for such a lookup-based query evaluation method have been proposed, there exists no analysis of the types (patterns) of queries that can be directly answered on the live Web, without accessing local or remote endpoints and without a-priori knowledge of available data sources. In this paper, we first provide a method for checking if a SPARQL query (to be evaluated on a SPARQL endpoint) can be answered through zero-knowledge link traversal (without accessing the endpoint), and analyse a large corpus of real SPARQL query logs for finding the frequency and distribution of answerable and non-answerable query patterns. Subsequently, we provide an algorithm for transforming answerable queries to SPARQL-LD queries that bypass the endpoints. We report experimental results about the efficiency of the transformed queries and discuss the benefits and the limitations of this query evaluation method.

References

[1]

Angela Bonifati, Wim Martens, and Thomas Timm. 2017. An analytical study of large SPARQL query logs. VLDB Endowment 11, 2 (2017), 149--161.

Digital Library

[2]

Angela Bonifati, Wim Martens, and Thomas Timm. 2018. DARQL: Deep Analysis of SPARQL Queries. In Companion of the The Web Conference 2018. International World Wide Web Conferences Steering Committee, 187--190.

Digital Library

[3]

Paolo Bouquet, Chiara Ghidini, and Luciano Serafini. 2009. Querying the web of data: A formal approach. In Asian Semantic Web Conference. Springer, 291--305.

Digital Library

[4]

Carlos Buil-Aranda, Marcelo Arenas, Oscar Corcho, and Axel Polleres. 2013. Federating queries in SPARQL 1.1: Syntax, semantics and evaluation. Web Semantics: Science, Services and Agents on the World Wide Web 18, 1 (2013), 1--17.

Digital Library

[5]

Carlos Buil-Aranda, Aidan Hogan, Jürgen Umbrich, and Pierre-Yves Vandenbussche. 2013. SPARQL web-querying infrastructure: Ready for action?. In International Semantic Web Conference. Springer, 277--293.

Digital Library

[6]

P. Fafalios and Y. Tzitzikas. 2015. SPARQL-LD: A SPARQL Extension for Fetching and Querying Linked Data. In The Semantic Web-ISWC 2015 (Posters & Demonstrations Track). Bethlehem, Pennsylvania, USA.

[7]

Pavlos Fafalios, Thanos Yannakis, and Yannis Tzitzikas. 2016. Querying the Web of Data with SPARQL-LD. In International Conference on Theory and Practice of Digital Libraries. Springer, 175--187.

[8]

Lee Feigenbaum, Gregory Todd Williams, Kendall Grant Clark, and Elias Torres. 2013. SPARQL 1.1 Protocol. Recommendation, W3C, March (2013).

[9]

Valeria Fionda, Giuseppe Pirrò, and Claudio Gutierrez. 2015. NautiLOD: A formal language for the web of data graph. ACM Transactions on the Web (TWEB) 9, 1 (2015), 5.

Digital Library

[10]

Andreas Harth, Katja Hose, Marcel Karnstedt, Axel Polleres, Kai-Uwe Sattler, and Jürgen Umbrich. 2010. Data summaries for on-demand queries over linked data. In 19th international conference on World Wide Web. ACM, 411--420.

Digital Library

[11]

Andreas Harth and Sebastian Speiser. 2012. On Completeness Classes for Query Evaluation on Linked Data. In 26th AAAI Conference on Artificial Intelligence.

Digital Library

[12]

Olaf Hartig. 2011. Zero-knowledge query planning for an iterator implementation of link traversal based query execution. In Extended Semantic Web Conference. Springer, 154--169.

Digital Library

[13]

Olaf Hartig. 2012. SPARQL for a Web of Linked Data: Semantics and computability. In Extended Semantic Web Conference. Springer, 8--23.

Digital Library

[14]

Olaf Hartig. 2013. An overview on execution strategies for Linked Data queries. Datenbank-Spektrum 13, 2 (2013), 89--99.

[15]

Olaf Hartig, Christian Bizer, and Johann-Christoph Freytag. 2009. Executing SPARQL queries over the web of linked data. In International Semantic Web Conference. Springer, 293--309.

Digital Library

[16]

Olaf Hartig and Johann-Christoph Freytag. 2012. Foundations of traversal based query execution over linked data. In Proceedings of the 23rd ACM conference on Hypertext and social media. ACM, 43--52.

Digital Library

[17]

Olaf Hartig and Jorge Pérez. 2016. LDQL: A query language for the web of linked data. Web Semantics: Science, Services and Agents on the World Wide Web 41 (2016), 9--29.

[18]

Tom Heath and Christian Bizer. 2011. Linked Data: Evolving the web into a global data space. Synthesis lectures on the semantic web: theory and technology 1, 1 (2011), 1--136.

[19]

Andreas Langegger, Wolfram Wöß, and Martin Blöchl. 2008. A semantic web middleware for virtual data integration on the web. In European Semantic Web Conference. Springer, 493--507.

Digital Library

[20]

Markus Luczak-Roesch, Saud Aljaloud, Bettina Berendt, Laura Hollink, et al. 2016. USEWOD 2016 Research Dataset (http://usewod.org/). (2016).

[21]

Daniel P Miranker, Rodolfo K Depena, Hyunjoon Jung, Juan F Sequeda, and Carlos Reyna. 2012. Diamond: A SPARQL query engine, for linked data based on the rete match. In Workshop on Artificial Intelligence meets the Web of Data.

[22]

Jorge Pérez, Marcelo Arenas, and Claudio Gutierrez. 2009. Semantics and complexity of SPARQL. ACM Transactions on Database Systems 34, 3 (2009), 16.

Digital Library

[23]

Bastian Quilitz and Ulf Leser. 2008. Querying distributed RDF data sources with SPARQL. In European Semantic Web Conference. Springer, 524--538.

Digital Library

[24]

Sherif Sakr, Marcin Wylot, Raghava Mutharaju, Danh Le Phuoc, and Irini Fundulaki. 2018. Centralized RDF Query Processing. Springer, 33--49.

[25]

Muhammad Saleem, Muhammad Intizar Ali, Aidan Hogan, Qaiser Mehmood, and Axel-Cyrille Ngonga Ngomo. 2015. LSQ: the linked SPARQL queries dataset. In International Semantic Web Conference. Springer, 261--269.

Digital Library

[26]

Muhammad Saleem, Yasar Khan, Ali Hasnain, Ivan Ermilov, and Axel-Cyrille Ngonga Ngomo. 2016. A fine-grained evaluation of SPARQL endpoint federation systems. Semantic Web 7, 5 (2016), 493--518.

Digital Library

[27]

Yuan Tian, Jürgen Umbrich, and Yong Yu. 2011. Enhancing source selection for live queries over linked data via query log mining. In Joint International Semantic Technology Conference. Springer, 176--191.

Digital Library

[28]

Y. Tzitzikas, N. Minadakis, Y. Marketakis, P. Fafalios, C. Allocca, M. Mountantonakis, and I. Zidianaki. 2014. MatWare: Constructing and Exploiting Domain Specific Warehouses by Aggregating Semantic Data. In 11th Extended Semantic Web Conference (ESWC'14).

[29]

Jürgen Umbrich, Aidan Hogan, Axel Polleres, and Stefan Decker. 2015. Link traversal querying for a diverse web of data. Semantic Web 6, 6 (2015), 585--624.

[30]

Ruben Verborgh, Olaf Hartig, Ben De Meester, Gerald Haesendonck, Laurens De Vocht, Miel Vander Sande, Richard Cyganiak, Pieter Colpaert, Erik Mannens, and Rik Van de Walle. 2014. Querying datasets on the web with high availability. In International Semantic Web Conference. Springer, 180--196.

Digital Library

[31]

Ruben Verborgh, Tobias Kuhn, and Andrei Sambra. 2017. Proceedings of the Workshop on Decentralizing the Semantic Web. In Workshop on Decentralizing the Semantic Web, co-located with ISWC 2017.

[32]

Ruben Verborgh, Miel Vander Sande, Olaf Hartig, Joachim Van Herwegen, Laurens De Vocht, Ben De Meester, Gerald Haesendonck, and Pieter Colpaert. 2016. Triple Pattern Fragments: a low-cost knowledge graph interface for the Web. Web Semantics: Science, Services and Agents on the World Wide Web 37 (2016), 184--206.

Digital Library

[33]

Andreas Wagner, Thanh Tran Duc, Günter Ladwig, Andreas Harth, and Rudi Studer. 2012. Top-k linked data query processing. In Extended Semantic Web Conference. Springer, 56--71.

Digital Library

[34]

T. Yannakis, P. Fafalios, and Y. Tzitzikas. 2018. Heuristics-based Query Reordering for Federated Queries in SPARQL 1.1 and SPARQL-LD. In 2nd Workshop on Querying the Web of Data (QuWeDa'18). Heraklion, Greece.

Cited By

Gu ZCorcoglioniti FLanti DMosca AXiao GXiong JCalvanese D(2024)A systematic overview of data federation systemsSemantic Web10.3233/SW-22320115:1(107-165)Online publication date: 12-Jan-2024
https://doi.org/10.3233/SW-223201
Stadler CSaleem MMehmood QBuil-Aranda CDumontier MHogan ANgonga Ngomo A(2024)LSQ 2.0: A linked dataset of SPARQL query logsSemantic Web10.3233/SW-22301515:1(167-189)Online publication date: 12-Jan-2024
https://doi.org/10.3233/SW-223015
Lourdusamy RMattam X(2021)A Knowledgebase Model Using RDF Knowledge Graph for ClinicalDecision Support SystemsSemantic Web for Effective Healthcare10.1002/9781119764175.ch10(215-247)Online publication date: 11-Nov-2021
https://doi.org/10.1002/9781119764175.ch10
Show More Cited By

Index Terms

How many and what types of SPARQL queries can be answered through zero-knowledge link traversal?
1. Information systems
  1. Data management systems
    1. Query languages

Recommendations

Answering SPARQL queries on the web of data through zero-knowledge link traversal

Link traversal has emerged as a SPARQL query processing method that exploits the Linked Data principles to dynamically discover data relevant for answering a query by dereferencing online Web resources (URIs) at query execution time. While several ...
What are real SPARQL queries like?
SWIM '11: Proceedings of the International Workshop on Semantic Web Information Management

We present statistics on real world SPARQL queries that may be of interest for building SPARQL query processing engines and benchmarks. In particular, we analyze the syntactical structure of queries in a log of about 3 million queries, harvested from ...
QueryVOWL: Visual Composition of SPARQL Queries
The Semantic Web: ESWC 2015 Satellite Events
Abstract
In order to make SPARQL queries more accessible to users, we have developed the visual query language QueryVOWL. It defines SPARQL mappings for graphical elements of the ontology visualization VOWL. In this demo, we present a web-based prototype ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SAC '19: Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing

April 2019

2682 pages

ISBN:9781450359337

DOI:10.1145/3297280

Conference Chairs:
Chih-Cheng Hung
Kennesaw State University, Marietta, Georgia
,
George A. Papadopoulos
University of Cyprus, Nicosia, Cyprus

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGAPP: ACM Special Interest Group on Applied Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 April 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SAC '19

Sponsor:

SIGAPP

SAC '19: The 34th ACM/SIGAPP Symposium on Applied Computing

April 8 - 12, 2019

Limassol, Cyprus

Acceptance Rates

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
73
Total Downloads

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

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gu ZCorcoglioniti FLanti DMosca AXiao GXiong JCalvanese D(2024)A systematic overview of data federation systemsSemantic Web10.3233/SW-22320115:1(107-165)Online publication date: 12-Jan-2024
https://doi.org/10.3233/SW-223201
Stadler CSaleem MMehmood QBuil-Aranda CDumontier MHogan ANgonga Ngomo A(2024)LSQ 2.0: A linked dataset of SPARQL query logsSemantic Web10.3233/SW-22301515:1(167-189)Online publication date: 12-Jan-2024
https://doi.org/10.3233/SW-223015
Lourdusamy RMattam X(2021)A Knowledgebase Model Using RDF Knowledge Graph for ClinicalDecision Support SystemsSemantic Web for Effective Healthcare10.1002/9781119764175.ch10(215-247)Online publication date: 11-Nov-2021
https://doi.org/10.1002/9781119764175.ch10
Fafalios PTzitzikas Y(2019)Answering SPARQL queries on the web of data through zero-knowledge link traversalACM SIGAPP Applied Computing Review10.1145/3372001.337200319:3(18-32)Online publication date: 8-Nov-2019
https://dl.acm.org/doi/10.1145/3372001.3372003

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