A complete translation from SPARQL into efficient SQL

ABSTRACT

This paper presents a feature-complete translation from SPARQL, the proposed standard for RDF querying, into efficient SQL. We propose "SQL model"-based algorithms that implement each SPARQL algebra operator via SQL query augmentation, and generate a flat SQL statement for efficient processing by relational database query engines. SPARQL-to-SQL translation presented is feature-complete, since it applies to all SPARQL language features. Finally, we demonstrate the performance and scalability of our method by an extensive evaluation using recent SPARQL benchmark queries, and a benchmark dataset, as well as a real-world photo dataset.

REFERENCES

• 1: Abadi, D. J., Marcus, A., Madden, S. R. and Hollenbach, K. Scalable Semantic Web Data Management Using Vertical Partitioning. In Proc. of VLDB, 2007, 411--422.
• 2: Broekstra, J., Kampman, A. and Harmelen, F. Sesame: A generic architecture for storing and querying RDF and RDF Schema. In Proc. of ISWC, 2002, 54--68.
• 3: Chebotko, A., Lu, S. and Fotouhi, F. Semantics Preserving SPARQL-to-SQL Translations, Technical Report, TR-DB-112007-CLF, 2007.
• 4: Cyganiak, R. A relational algebra for SPARQL. Technical Report, HP Laboratories Bristol.
• 5: Erling, O. Implementing a SPARQL compliant RDF triple store using a SQL-ORDBMS. OpenLink Software Virtuoso. 2001. http://virtuoso.openlinksw.com/wiki/main/Main/VOSRDFWP
• 6: Groppe, S., Grope, J. and Linnemann, V. Using an Index of Precomputed Joins in order to speed up SPARQL Processing. In Proceedings of the 9th International Conference on Enterprise Information Systems, 2007, 13--20.
• 7: Harris, S. and Gibbins, N. 3store: Efficient bulk RDF storage. In Proceedings of the International Workshop on Practical and Scalable Semantic Systems, 2003, 1--15.
• 8: Harris, S. and Shadbolt, N. SPARQL query processing with conventional relational database systems. In Proceedings of the International Workshop on Scalable Semantic Web Knowledge Base Systems, 2005.
• 9: Harth, A. and Decker, S. Optimized Index Structures for Querying RDF from the Web. In Web Congress, LA-WEB 2005.
• 10: Hartwig, O. and Heese, R. The SPARQL Query Graph Model for Query Optimization. In Proceeding of the 4th European Semantic Web Conference, 2007.
• 11: H. L. S. W. R. Group. Jena -- A Semantic Web Framework for Java. Online only, 2004. Available at: http://jena.sourceforge.net/
• 12: Klyne, G. and Carroll, J. J. (ed.). Resource Description Framework (RDF): Concepts and Abstract Syntax, W3C Recommendation, 10 February 2004. Latest version: http://www.w3.org/TR/rdf-concepts/
• 13: Lu, J., Cao, F., Ma, L., Yu, Y. and Pan, Y. An Effective SPARQL Support over Relational Databases, SWEB-ODBIS 2007, 57--76.
• 14: Ma, L., Wang, C., Lu, J., Cao, F., Pan, Y. and Yu, Y. Effective and Efficient Semantic Web Data Management over DB2, In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, 2008, 1183--1194.
• 15: Manola, F. and Miller, E. RDF Primer. W3C Recommendation, World Wide Web Consortium, Feburary 2004. Latest version: http://www.w3.org/TR/rdf-primer/
• 16: McBride, B. Jena: Implementing the RDF model and syntax specification. Hewlett Packard Laboratories. 2001. http://www.hpl.hp.com/personal/bwm/papers/20001221-paper/
• 17: Prud'hommeaux, E. and Seaborne, A. SPARQL Query Language for RDF. W3C, 2008. http://www.w3.org/TR/rdf-sparql-query/
• 18: RDFLib. http://rdflib.net/
• 19: Schmidt, M., Hornung, T., Lausen, G. and Pinkel, C. SP2Bench: A SPARQL Performance Benchmark, In Proceedings of the 25th International Conference on Data Engineering, 2009
• 20: Sidirourgos, L., Goncalves, R., Kersten, M., Nes, N. and Manegold, S. Column-store support for RDF data management: not all swans are white. In Proceedings of the 34th international conference on Very large data bases, 2008, 1553--1563.
• 21: Stocker, M., Seaborne, A., Bernstein, A., Kiefer, C. and Reynolds, D. SPARQL Basic Graph Pattern Optimization Using Selectivity Estimation, In Proceeding of the 17th international conference on World Wide Web, 2008, 595--604.
• 22: Theoharis, Y., Christophides, V. and Karvounarakis, G. Benchmarking database representations of RDF/S stores. In Proceeding of the International Semantic Web Conference, 2005.
• 23: Wilknson, K., Sayers, C., Kuno, H. and Reynolds, D. Efficient RDF storage and retrieval in Jena2. In Proceedings of the International Workshop on Semantic Web and Databases, 2003, 131--150.
• 24: Bizer, C. and Seaborne, A. D2RQ-treating non-RDF databases as virtual RDF graphs. In Proc. of ISWC, 2004
• 25: Barrasa, J., Corcho, O., and Gomez-Perez, A. R2O, an extensible and semantically based database-to-ontology mapping language. 2004.
• 26: OpenLink, "Virtuoso RDF Views -- Getting Started Guide"
• 27: Polleres, A. From SPARQL to rules (and back).

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Design, Experimentation, Languages, Management, Performance

Keywords:
RDF, SPARQL, SQL, semantic web