Hexastore: sextuple indexing for semantic web data management

ABSTRACT

Despite the intense interest towards realizing the Semantic Web vision, most existing RDF data management schemes are constrained in terms of efficiency and scalability. Still, the growing popularity of the RDF format arguably calls for an effort to offset these drawbacks. Viewed from a relational-database perspective, these constraints are derived from the very nature of the RDF data model, which is based on a triple format. Recent research has attempted to address these constraints using a vertical-partitioning approach, in which separate two-column tables are constructed for each property. However, as we show, this approach suffers from similar scalability drawbacks on queries that are not bound by RDF property value. In this paper, we propose an RDF storage scheme that uses the triple nature of RDF as an asset. This scheme enhances the vertical partitioning idea and takes it to its logical conclusion. RDF data is indexed in six possible ways, one for each possible ordering of the three RDF elements. Each instance of an RDF element is associated with two vectors; each such vector gathers elements of one of the other types, along with lists of the third-type resources attached to each vector element. Hence, a sextuple-indexing scheme emerges. This format allows for quick and scalable general-purpose query processing; it confers significant advantages (up to five orders of magnitude) compared to previous approaches for RDF data management, at the price of a worst-case five-fold increase in index space. We experimentally document the advantages of our approach on real-world and synthetic data sets with practical queries.

REFERENCES

• 1: Longwell browser, http://simile.mit.edu/longwell.
• 2: MIT Libraries Barton Catalog Data. http://simile.mit.edu/rdf-test-data/barton/.
• 3: The SIMILE Project, http://simile.mit.edu/.
• 4: Daniel Abadi , Samuel Madden , Miguel Ferreira, Integrating compression and execution in column-oriented database systems, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142548]
• 5: 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
• 6: D. J. Abadi, A. Marcus, S. R. Madden, and K. Hollenbach. Using the Barton Libraries dataset as an RDF benchmark. Technical Report MIT-CSAIL-TR-2007-036, MIT, 2007.
• 7: D. J. Abadi, D. S. Myers, D. J. DeWitt, and S. Madden. Materialization strategies in a column-oriented DBMS. In ICDE, 2007.
• 8: S. Alexaki, V. Christophides, G. Karvounarakis, and D. Plexousakis. On storing voluminous RDF descriptions: The case of web portal catalogs. In WebDB, 2001.
• 9: S. Alexaki, V. Christophides, G. Karvounarakis, D. Plexousakis, and K. Tolle. The ICS-FORTH RDFSuite: Managing voluminous RDF description bases. In SemWeb, 2001.
• 10: R. Angles and C. Gutiérrez. Querying RDF data from a graph database perspective. In ESWC, 2005.
• 11: David Beckett, The design and implementation of the redland RDF application framework, Proceedings of the 10th international conference on World Wide Web, p.449-456, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372099]
• 12: Jennifer L. Beckmann , Alan Halverson , Rajasekar Krishnamurthy , Jeffrey F. Naughton, Extending RDBMSs To Support Sparse Datasets Using An Interpreted Attribute Storage Format, Proceedings of the 22nd International Conference on Data Engineering, p.58, April 03-07, 2006 [doi>10.1109/ICDE.2006.67]
• 13: T. Berners-Lee, J. Hendler, and O. Lassila. The Semantic Web. Scientific American, 284(5):34--43, 2001.
• 14: Peter A. Boncz , Martin L. Kersten, MIL primitives for querying a fragmented world, The VLDB Journal — The International Journal on Very Large Data Bases, v.8 n.2, p.101-119, October 1999 [doi>10.1007/s007780050076]
• 15: P. A. Boncz, M. Zukowski, and N. Nes. MonetDB/X100: Hyper-pipelining query execution. In CIDR, 2005.
• 16: V. Bönström, A. Hinze, and H. Schweppe. Storing RDF as a graph. In LA-WEB, 2003.
• 17: 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
• 18: K. Selçuk Candan , Huan Liu , Reshma Suvarna, Resource description framework: metadata and its applications, ACM SIGKDD Explorations Newsletter, v.3 n.1, July 2001 [doi>10.1145/507533.507536]
• 19: Jeremy J. Carroll , Ian Dickinson , Chris Dollin , Dave Reynolds , Andy Seaborne , Kevin Wilkinson, Jena: implementing the semantic web recommendations, Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters, May 19-21, 2004, New York, NY, USA [doi>10.1145/1013367.1013381]
• 20: 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
• 21: Shaul Dar , Raghu Ramakrishnan, A performance study of transitive closure algorithms, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.454-465, May 24-27, 1994, Minneapolis, Minnesota, United States
• 22: R. V. Guha. rdfDB: An RDF database. http://www.guha.com/rdfdb/.
• 23: Y. Guo, J. Heflin, and Z. Pan. Benchmarking DAML+OIL repositories. In ISWC, 2003.
• 24: Y. Guo, Z. Pan, and J. Heflin. An evaluation of knowledge base systems for large OWL datasets. In ISWC, 2004.
• 25: S. Harris and N. Gibbins. 3store: Efficient bulk RDF storage. In PSSS, 2003.
• 26: S. Harris and N. Shadbolt. SPARQL query processing with conventional relational database systems. In SSWS, 2005.
• 27: Andreas Harth , Stefan Decker, Optimized Index Structures for Querying RDF from the Web, Proceedings of the Third Latin American Web Congress, p.71, October 31-November 02, 2005 [doi>10.1109/LAWEB.2005.25]
• 28: J. Hayes and C. Gutiérrez. Bipartite graphs as intermediate model for RDF. In ISWC, 2004.
• 29: S. Idreos, M. L. Kersten, and S. Manegold. Database cracking. In CIDR, 2007.
• 30: Stratos Idreos , Martin L. Kersten , Stefan Manegold, Updating a cracked database, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247527]
• 31: Yannis Ioannidis , Raghu Ramakrishnan , Linda Winger, Transitive closure algorithms based on graph traversal, ACM Transactions on Database Systems (TODS), v.18 n.3, p.512-576, Sept. 1993 [doi>10.1145/155271.155273]
• 32: M. L. Kersten and S. Manegold. Cracking the database store. In CIDR, 2005.
• 33: C. Kiefer, A. Bernstein, and M. Stocker. The fundamentals of iSPARQL - a virtual triple approach for similarity-based Semantic Web tasks. In ISWC, 2007.
• 34: Y. Kim, B. Kim, J. Lee, and H. Lim. The path index for query processing on RDF and RDF Schema. In ICACT, 2005.
• 35: E. Liarou, S. Idreos, and M. Koubarakis. Continuous RDF query processing over DHTs. In ISWC, 2007.
• 36: Li Ma , Zhong Su , Yue Pan , Li Zhang , Tao Liu, RStar: an RDF storage and query system for enterprise resource management, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031264]
• 37: F. Manola and E. Miller, editors. RDF Primer. W3C Recommendation. WWW Consortium, 2004.
• 38: Akiyoshi Matono , Toshiyuki Amagasa , Masatoshi Yoshikawa , Shunsuke Uemura, A path-based relational RDF database, Proceedings of the 16th Australasian database conference, p.95-103, January 01, 2005, Newcastle, Australia
• 39: Z. Pan and J. Heflin. DLDB: Extending relational databases to support Semantic Web queries. In PSSS, 2003.
• 40: Milenko Petrovic , Haifeng Liu , Hans-Arno Jacobsen, G-ToPSS: fast filtering of graph-based metadata, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060824]
• 41: 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]
• 42: Mike Stonebraker , Daniel J. Abadi , Adam Batkin , Xuedong Chen , Mitch Cherniack , Miguel Ferreira , Edmond Lau , Amerson Lin , Sam Madden , Elizabeth O'Neil , Pat O'Neil , Alex Rasin , Nga Tran , Stan Zdonik, C-store: a column-oriented DBMS, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 43: Jeffrey D. Ullman , Mihalis Yannakakis, The input/output complexity of transitive closure, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.44-53, May 23-26, 1990, Atlantic City, New Jersey, United States
• 44: R. Volz, D. Oberle, S. Staab, and B. Motik. KAON SERVER - A Semantic Web Management System. In WWW (Alternate Paper Tracks), 2003.
• 45: K. Wilkinson. Jena property table implementation. In SSWS, 2006.
• 46: K. Wilkinson, C. Sayers, H. A. Kuno, and D. Reynolds. Efficient RDF storage and retrieval in Jena2. In SWDB, 2003.
• 47: D. Wood, P. Gearon, and T. Adams. Kowari: A platform for Semantic Web storage and analysis. In XTech, 2005.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

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.2 Information Storage
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Algorithms, Design, Management, Performance