OPT+: A Monotonic Alternative to OPTIONAL in SPARQL

  • Sijin Cheng Department of Computer and Information Science (IDA), Linköping University, Sweden
  • Olaf Hartig Department of Computer and Information Science (IDA), Linköping University, Sweden
Keywords: OPT, Monotonic Alternative to OPTIONAL

Abstract

Due to the OPTIONAL operator, the core fragment of the SPARQL query language is non-monotonic. That is, some solutions of a query result can be returned to the user only after having consulted all relevant parts of the queried dataset(s). This property presents an obstacle when developing query execution approaches that aim to reduce responses times rather than the overall query execution times. Reducing the response times–i.e., returning as many solutions as early as possible– is important in particular in Web-based client-server query processing scenarios in which network latencies dominate query execution times. Such scenarios are typical in the context of integration of Web data sources where a data integration component executes queries over a decentralized federation of such data sources. In this paper we introduce an alternative operator that is similar in spirit to OPTIONAL but without causing non-monotonicity. We show fundamental properties of this operator and observe that the downside of achieving the desired monotonicity property is a potentially significant increase in query result sizes. We study the extend of this trade-off in practice. Thereafter, we introduce different algorithms to implement the new operator and evaluate them regarding their potential to reduce response times. Keywords: Semantic web, linked data, query language, optimization.

Downloads

Download data is not yet available.

Author Biographies

Sijin Cheng, Department of Computer and Information Science (IDA), Linköping University, Sweden

Sijin Cheng is a Ph.D. student at Linköping University since Spring 2019. She holds a double Master’s degree in Computer Science and Software Engineering from Linköping University, Sweden, and the Harbin Institute of Technology, China. Sijin’s Ph.D. work focuses on problems related to querying federations of graph data sources with heterogeneous forms of data access interfaces.

Olaf Hartig, Department of Computer and Information Science (IDA), Linköping University, Sweden

Olaf Hartig is an Associate Professor in Computer Science at Linköping University. He holds a Ph.D. in Computer Science from the Humboldt-Universität zu Berlin and has been awarded the academic qualification Docent in Computer Science from Linköping University.

His research focuses on data on the Web and on graph data, as well as on problems in which the data is distributed over multiple, autonomous and/or heterogeneous sources. Regarding these topics, Olaf’s interests range from systems-building related research to theoret-ical foundations. For his Ph.D. dissertation “Querying a Web of Linked Data: Foundations and Query Execution” he was honored with the 2015 Distinguished Dissertation Award of the Semantic Web Science Foundation (SWSA), and he has received several best research paper awards (ESWC2009, ESWC2015, ISWC2017, Semantics2018).

References

Maribel Acosta, Olaf Hartig, and Juan Sequeda. Federated RDF Query Processing. In Sherif Sakr and Albert Zomaya, editors, Encyclopedia of Big Data Technologies. Springer, 2018.

Maribel Acosta, Maria-Esther Vidal, Tomas Lampo, Julio Castillo, and Edna Ruckhaus. ANAPSID: An Adaptive Query Processing Engine for SPARQL Endpoints. In The Semantic Web – ISWC 2011 – 10th International Semantic Web Conference, Bonn, Germany, October 23–27, 2011, Proceedings, Part I, pages 18–34, 2011.

Renzo Angles and Claudio Gutiérrez. The expressive power of SPARQL. In The Semantic Web – ISWC 2008, 7th International Semantic Web Conference, ISWC 2008, Karlsruhe, Germany, October 26–30, 2008. Proceedings, pages 114–129, 2008.

Javier D. Fernández, Miguel A. Martínez-Prieto, Claudio Gutiérrez, Axel Polleres, and Mario Arias. Binary RDF representation for publication and exchange (HDT). J. Web Sem., 19:22–41, 2013.

Goetz Graefe. Query Evaluation Techniques for Large Databases. ACM Comput. Surv., 25(2):73–170, 1993.

Steve Harris, Andy Seaborne, and Eric Prud’hommeaux. SPARQL 1.1 Query Language. W3C Recommendation, Online at http://www.w3.org/TR/sparql11-query/, March 2013.

Olaf Hartig. Querying a Web of Linked Data: Foundations and Query Execution. PhD thesis, Humboldt-Universität zu Berlin, Germany, 2014.

Olaf Hartig, Christian Bizer, and Johann Christoph Freytag. Executing SPARQL Queries over the Web of Linked Data. In The Semantic Web – ISWC 2009, 8th International Semantic Web Conference, ISWC 2009, Chantilly, VA, USA, October 25–29, 2009. Proceedings, pages 293–309, 2009.

Olaf Hartig and M. Tamer Özsu. Walking without a map: Ranking-based traversal for querying linked data. In The Semantic Web – ISWC 2016 – 15th International Semantic Web Conference, Kobe, Japan, October 17–21, 2016, Proceedings, Part I, pages 305–324, 2016.

Lars Heling, Maribel Acosta, Maria Maleshkova, and York Sure-Vetter. Querying large knowledge graphs over triple pattern fragments: An empirical study. In The Semantic Web – ISWC 2018 – 17th International Semantic Web Conference, Monterey, CA, USA, October 8–12, 2018, Proceedings, Part II, pages 86–102, 2018.

Markus Luczak-Roesch, Saud Aljaloud, Bettina Berendt, and Laura Hollink. USEWOD 2016 Research Dataset. University of Southampton, 10.5258/SOTON/385344, 2016.

Stanislav Malyshev, Markus Krötzsch, Larry González, Julius Gonsior, and Adrian Bielefeldt. Getting the Most Out of Wikidata: Semantic Technology Usage in Wikipedia’s Knowledge Graph. In The Semantic Web – ISWC 2018 – 17th International Semantic Web Conference, Monterey, CA, USA, October 8–12, 2018, Proceedings, Part II, pages 376–394, 2018.

Jorge Pérez, Marcelo Arenas, and Claudio Gutierrez. Semantics of SPARQL. Technical Report TR/DCC-2006-17, Department of Computer Science, University of Chile, 2006.

Jorge Pérez, Marcelo Arenas, and Claudio Gutierrez. Semantics and Complexity of SPARQL. ACM Trans. Database Syst., 34(3):16:1–16:45, 2009.

Eric Prud’hommeaux and Carlos Buil-Aranda. SPARQL 1.1 Federated Query. W3C Recommendation, Online at http://www.w3.org/TR/sparql11-federated-query/, March 2013.

Muhammad Saleem, Muhammad IntizarAli,Aidan Hogan, Qaiser Mehmood, and Axel-Cyrille Ngonga Ngomo. LSQ: The Linked SPARQL Queries Dataset. In The Semantic Web – ISWC 2015 – 14th International Semantic Web Conference, Bethlehem, PA, USA, October 11–15, 2015, Proceedings, Part II, pages 261–269, 2015.

Muhammad Saleem, Yasar Khan, Ali Hasnain, Ivan Ermilov, and Axel-Cyrille Ngonga Ngomo. A Fine-Grained Evaluation of SPARQL Endpoint Federation Systems. Semantic Web, 7(5): 493–518, 2016.

Jürgen Umbrich, Katja Hose, Marcel Karnstedt, Andreas Harth, and Axel Polleres. Comparing Data Summaries for Processing Live Queries over Linked Data. World Wide Web, 14(5–6): 495–544, 2011.

Ruben Verborgh, Miel Vander Sande, Olaf Hartig, Joachim Van Herwegen, Laurens De Vocht, Ben De Meester, Gerald Haesendonck, and Pieter Colpaert. Triple Pattern Fragments: A Low-Cost Knowledge Graph Interface for the Web. J. Web Sem., 37–38:184–206, 2016.

Published
2019-01-01
Section
Articles