RDF-3X: a RISC-style engine for RDF

ABSTRACT

RDF is a data representation format for schema-free structured information that is gaining momentum in the context of Semantic-Web corpora, life sciences, and also Web 2.0 platforms. The "pay-as-you-go" nature of RDF and the flexible pattern-matching capabilities of its query language SPARQL entail efficiency and scalability challenges for complex queries including long join paths. This paper presents the RDF-3X engine, an implementation of SPARQL that achieves excellent performance by pursuing a RISC-style architecture with a streamlined architecture and carefully designed, puristic data structures and operations. The salient points of RDF-3X are: 1) a generic solution for storing and indexing RDF triples that completely eliminates the need for physical-design tuning, 2) a powerful yet simple query processor that leverages fast merge joins to the largest possible extent, and 3) a query optimizer for choosing optimal join orders using a cost model based on statistical synopses for entire join paths. The performance of RDF-3X, in comparison to the previously best state-of-the-art systems, has been measured on several large-scale datasets with more than 50 million RDF triples and benchmark queries that include pattern matching and long join paths in the underlying data graphs.

REFERENCES

• 1: Daniel J. Abadi , Adam Marcus , Samuel R. Madden , Kate Hollenbach, Scalable semantic web data management using vertical partitioning, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 2: S. Alexaki et al. The ics-forth rdfsuite: Managing voluminous rdf description bases. In SemWeb, 2001.
• 3: Kemafor Anyanwu , Angela Maduko , Amit Sheth, SPARQ2L: towards support for subgraph extraction queries in rdf databases, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242680]
• 4: S. Auer et al. Dbpedia: A nucleus for a web of open data. In ISWC/ASWC, 2007.
• 5: L. Baolin and H. Bo. Path queries based rdf index. In SKG, 2005.
• 6: L. Baolin and H. Bo. Hprd: A high performance rdf database. In NPC, 2007.
• 7: BioPAX: Biological Pathways Exchange. http://www.biopax.org/.
• 8: Jeen Broekstra , Arjohn Kampman , Frank van Harmelen, Sesame: A Generic Architecture for Storing and Querying RDF and RDF Schema, Proceedings of the First International Semantic Web Conference on The Semantic Web, p.54-68, June 09-12, 2002
• 9: Surajit Chaudhuri , Kyuseok Shim, Optimization of queries with user-defined predicates, ACM Transactions on Database Systems (TODS), v.24 n.2, p.177-228, June 1999 [doi>10.1145/320248.320249]
• 10: Surajit Chaudhuri , Gerhard Weikum, Rethinking Database System Architecture: Towards a Self-Tuning RISC-Style Database System, Proceedings of the 26th International Conference on Very Large Data Bases, p.1-10, September 10-14, 2000
• 11: Eugene Inseok Chong , Souripriya Das , George Eadon , Jagannathan Srinivasan, An efficient SQL-based RDF querying scheme, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 12: Eric Chu , Jennifer Beckmann , Jeffrey Naughton, The case for a wide-table approach to manage sparse relational data sets, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247571]
• 13: David DeHaan , Frank Wm. Tompa, Optimal top-down join enumeration, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247567]
• 14: André Eickler , Carsten Andreas Gerlhof , Donald Kossmann, A Performance Evaluation of OID Mapping Techniques, Proceedings of the 21th International Conference on Very Large Data Bases, p.18-29, September 11-15, 1995
• 15: César A. Galindo-Legaria , Arjan Pellenkoft , Martin L. Kersten, Fast, Randomized Join-Order Selection - Why Use Transformations?, Proceedings of the 20th International Conference on Very Large Data Bases, p.85-95, September 12-15, 1994
• 16: Lise Getoor , Christopher P. Diehl, Link mining: a survey, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.3-12, December 2005 [doi>10.1145/1117454.1117456]
• 17: Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993 [doi>10.1145/152610.152611]
• 18: Alon Halevy , Michael Franklin , David Maier, Principles of dataspace systems, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.1-9, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142352]
• 19: A. Harth, J. Umbrich, A. Hogan, and S. Decker. Yars2: A federated repository for querying graph structured data from the web. In ISWC/ASWC, 2007.
• 20: Olaf Hartig , Ralf Heese, The SPARQL Query Graph Model for Query Optimization, Proceedings of the 4th European conference on The Semantic Web: Research and Applications, June 03-07, 2007, Innsbruck, Austria [doi>10.1007/978-3-540-72667-8_40]
• 21: A. Hogan and A. Harth. The expertfinder corpus 2007 for the benchmarking development of expert-finding systems. In International ExpertFinder Workshop, 2007.
• 22: David Huynh , Stefano Mazzocchi , David Karger, Piggy Bank: Experience the Semantic Web inside your web browser, Web Semantics: Science, Services and Agents on the World Wide Web, v.5 n.1, p.16-27, March, 2007 [doi>10.1016/j.websem.2006.12.002]
• 23: Jena: a Semantic Web Framework for Java. http://jena.sourceforge.net/.
• 24: M. Kersten and A. P. Siebes. An organic database system. Technical report, CWI, 1999.
• 25: Angela Maduko , Kemafor Anyanwu , Amit Sheth , Paul Schliekelman, Estimating the cardinality of RDF graph patterns, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242782]
• 26: Guido Moerkotte , Thomas Neumann, Analysis of two existing and one new dynamic programming algorithm for the generation of optimal bushy join trees without cross products, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 27: Monetdb. http://monetdb.cwi.nl/.
• 28: Openrdf. http://www.openrdf.org/index.jsp.
• 29: Oracle technical network, semantic technologies center. http://www.oracle.com/technology/tech/semantic_technologies/index.html.
• 30: W3C: Resource Description Framework (RDF). http://www.w3.org/RDF/.
• 31: RDFizers. http://simile.mit.edu/wiki/RDFizers.
• 32: ICS-FORTH RDF suite. http://athena.ics.forth.gr:9090/RDF/.
• 33: Falk Scholer , Hugh E. Williams , John Yiannis , Justin Zobel, Compression of inverted indexes For fast query evaluation, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564416]
• 34: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 35: David Simmen , Eugene Shekita , Timothy Malkemus, Fundamental techniques for order optimization, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.57-67, June 04-06, 1996, Montreal, Quebec, Canada
• 36: W3C: SPARQL Query Language for RDF. http://www.w3.org/TR/rdf-sparql-query/.
• 37: Michael Steinbrunn , Klaus Peithner , Guido Moerkotte , Alfons Kemper, Bypassing Joins in Disjunctive Queries, Proceedings of the 21th International Conference on Very Large Data Bases, p.228-238, September 11-15, 1995
• 38: Markus Stocker , Andy Seaborne , Abraham Bernstein , Christoph Kiefer , Dave Reynolds, SPARQL basic graph pattern optimization using selectivity estimation, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367578]
• 39: M. Stonebraker et al. One size fits all? part 2: Benchmarking studies. In CIDR, 2007.
• 40: Fabian M. Suchanek , Gjergji Kasneci , Gerhard Weikum, Yago: a core of semantic knowledge, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242667]
• 41: Y. Theoharis, V. Christophides, and G. Karvounarakis. Benchmarking database representations of rdf/s stores. In International Semantic Web Conference, 2005.
• 42: O. Udrea, A. Pugliese, and V. S. Subrahmanian. Grin: A graph based rdf index. In AAAI, 2007.
• 43: uniprot RDF. http://dev.isb-sib.ch/projects/uniprot-rdf/.
• 44: N. Vanetik , E. Gudes, Mining Frequent Labeled and Partially Labeled Graph Patterns, Proceedings of the 20th International Conference on Data Engineering, p.91, March 30-April 02, 2004
• 45: Till Westmann , Donald Kossmann , Sven Helmer , Guido Moerkotte, The implementation and performance of compressed databases, ACM SIGMOD Record, v.29 n.3, p.55-67, Sept. 2000 [doi>10.1145/362084.362137]
• 46: K. Wilkinson et al. Efficient rdf storage and retrieval in jena2. In SWDB, 2003.
• 47: W3C: RDF/OWL representation of WordNet. http://www.w3.org/TR/wordnet-rdf/.
• 48: Yars2. http://sw.deri.org/svn/sw/2004/06/yars.
• 49: F. Zhu, X. Yan, J. Han, and P. S. Yu. gprune: A constraint pushing framework for graph pattern mining. In PAKDD, 2007.
• 50: Justin Zobel , Alistair Moffat, Inverted files for text search engines, ACM Computing Surveys (CSUR), v.38 n.2, p.6-es, 2006 [doi>10.1145/1132956.1132959]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.1 Single Data Stream Architectures
          Subjects: RISC/CISC, VLIW architectures

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
      H.2.4 Systems
          Subjects: Query processing
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Design, Management, Performance