Nikolay Yakovets
ABSTRACT
The extension of SPARQL in version 1.1 with property paths offers a type of regular path query for RDF graph databases. Such queries are difficult to optimize and evaluate efficiently, however. We have embarked on a project, Waveguide, to build a cost-based optimizer for SPARQL queries with property paths. Waveguide builds a query plan--- which we call a waveplan (WP)--- which guides the query evaluation. There are numerous choices in the construction of a plan, and a number of optimization methods, so the space of plans for a query can be quite large. Execution costs of plans for the same query can vary by orders of magnitude. A WGP's costs can be estimated, which opens the way to cost-based optimization. We demonstrate that the plan space of Waveguide properly subsumes existing techniques and that the new plans it adds are relevant.
- S. Abiteboul, R. Hull, and V. Vianu. Foundations of databases, volume 8. Addison-Wesley, 1995. Google Scholar
Digital Library
- S. Abiteboul, D. Quass, J. McHugh, J. Widom, and J. L. Wiener. The Lorel query language for semistructured data. International Journal on Digital Libraries, 1(1):68--88, 1997.Google ScholarCross Ref
- R. Agrawal. Alpha: An extension of relational algebra to express a class of recursive queries. Software Engineering, IEEE Transactions on, 14(7):879--885, 1988. Google ScholarDigital Library
- P. Barcelo, L. Libkin, A. W. Lin, and P. T. Wood. Expressive languages for path queries over graph-structured data. Transactions on Database Systems, 37(4):31, 2012. Google ScholarDigital Library
- M. Bojanczyk. Automata for data words and data trees. In RTA, pages 1--4, 2010.Google ScholarCross Ref
- P. Buneman, S. Davidson, G. Hillebrand, and D. Suciu. A query language and optimization techniques for unstructured data. SIGMOD Record, 25(2):505--516, 1996. Google ScholarDigital Library
- D. Calvanese, G. De Giacomo, M. Lenzerini, and M. Y. Vardi. Rewriting of regular expressions and regular path queries. In Proceedings of the Symposium on Principles of Database Systems, pages 194--204. ACM, 1999. Google ScholarDigital Library
- J. J. Carroll, I. Dickinson, C. Dollin, D. Reynolds, A. Seaborne, and K. Wilkinson. Jena: implementing the semantic web recommendations. In Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters, pages 74--83. ACM, 2004. Google ScholarDigital Library
- M. P. Consens, A. O. Mendelzon, D. Vista, and P. T. Wood. Constant propagation versus join reordering in datalog. In Rules in Database Systems, pages 245--259. Springer, 1995. Google ScholarDigital Library
- The DBpedia knowledge base. http://dbpedia.org/.Google Scholar
- S. Dey, V. Cuevas-Vicenttın, S. Köhler, E. Gribkoff, M. Wang, and B. Ludascher. On implementing provenance-aware regular path queries with relational query engines. In Proceedings of the Joint EDBT/ICDT 2013 Workshops, pages 214--223. ACM, 2013. Google ScholarDigital Library
- O. Erling and I. Mikhailov. Virtuoso: RDF Support in Native RDBMS. Semantic Web Information Management, 1:501, 2010.Google ScholarCross Ref
- D. Florescu, A. Y. Levy, and A. O. Mendelzon. Database techniques for the world-wide web: A survey. SIGMOD Record, 27(3):59--74, 1998. Google ScholarDigital Library
- S. Harris and A. Seaborne. SPARQL 1.1 query language. W3C working draft. http://www.w3.org/TR/sparql11-query/, November 2012.Google Scholar
- K. J. Kochut and M. Janik. Sparqler: Extended sparql for semantic association discovery. In The Semantic Web: Research and Applications, pages 145--159. Springer, 2007. Google ScholarDigital Library
- A. Koschmieder and U. Leser. Regular path queries on large graphs. In Scientific and Statistical Database Management, pages 177--194. Springer Berlin Heidelberg, 2012. Google ScholarDigital Library
- K. Losemann and W. Martens. The complexity of evaluating path expressions in SPARQL. In Proceedings of the 31st symposium on Principles of Database Systems, pages 101--112. ACM, 2012. Google ScholarDigital Library
- A. Mendelzon and P. Wood. Finding regular simple paths in graph databases. SIAM Journal on Computing, 24(6):1235--1258, 1995. Google ScholarDigital Library
- J. Pérez, M. Arenas, and C. Gutierrez. nSPARQL: A navigational language for rdf. Web Semantics: Science, Services and Agents on the World Wide Web, 8(4):255--270, 2010. Google ScholarDigital Library
- E. Prud'Hommeaux, A. Seaborne, et al. SPARQL query language for RDF. W3C Recommendation, 15, 2008.Google Scholar
- W3C: Resource Description Framework (RDF). http://www.w3.org/TR/rdf-concepts/, 2004.Google Scholar
- L. Segoufin. Automata and logics for words and trees over an infinite alphabet. In Computer Science Logic, pages 41--57. Springer, 2006. Google ScholarDigital Library
- L. Segoufin. Static analysis of XML processing with data values. ACM Sigmod Record, 36(1):31--38, 2007. Google ScholarDigital Library
- YAGO2s: A high-quality knowledge base. http://yago-knowledge.org/resource/. Max Planck Institut Informatik.Google Scholar
- N. Yakovets, P. Godfrey, and J. Gryz. Evaluation of SPARQL property paths via recursive SQL. In L. Bravo and M. Lenzerini, editors, AMW, volume 1087 of CEUR Workshop Proceedings. CEUR-WS.org, May 2013.Google Scholar
- N. Yakovets, P. Godfrey, and J. Gryz. WAVEGUIDE: evaluating SPARQL property path queries. In Proceedings of the 18th International Conference on Extending Database Technology, EDBT 2015, Brussels, Belgium, March 23--27, 2015., pages 525--528, 2015.Google Scholar
- H. Zauner, B. Linse, T. Furche, and F. Bry. A RPL through RDF: expressive navigation in RDF graphs. In Web Reasoning and Rule Systems, pages 251--257. Springer, 2010. Google ScholarDigital Library
Index Terms
- Query Planning for Evaluating SPARQL Property Paths
Recommendations
Foundations of SPARQL query optimization
ICDT '10: Proceedings of the 13th International Conference on Database TheoryWe 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 ...
SPARQL-to-SQL Query Translation: Bottom-Up or Top-Down?
SCC '11: Proceedings of the 2011 IEEE International Conference on Services ComputingEmerging Semantic Web Services rely on the availability of metadata that describes various functional and non-functional characteristics of computational resources. A number of semantic vocabularies and datasets describing existing services and ...
gTop: An Efficient SPARQL Query Engine
Web and Big DataAbstractIn this demonstration, we present gTop, a top-k query engine based on gStore which supports SPARQL queries over RDF databases. gTop can answer top-k queries with high efficiency and scalability. We use the DP-B algorithm for top-k queries and the ...
Comments