Scalable join processing on very large RDF graphs

ABSTRACT

With the proliferation of the RDF data format, engines for RDF query processing are faced with very large graphs that contain hundreds of millions of RDF triples. This paper addresses the resulting scalability problems. Recent prior work along these lines has focused on indexing and other physical-design issues. The current paper focuses on join processing, as the fine-grained and schema-relaxed use of RDF often entails star- and chain-shaped join queries with many input streams from index scans.

We present two contributions for scalable join processing. First, we develop very light-weight methods for sideways information passing between separate joins at query run-time, to provide highly effective filters on the input streams of joins. Second, we improve previously proposed algorithms for join-order optimization by more accurate selectivity estimations for very large RDF graphs. Experimental studies with several RDF datasets, including the UniProt collection, demonstrate the performance gains of our approach, outperforming the previously fastest systems by more than an order of magnitude.

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. Auer et al. Dbpedia: A nucleus for a web of open data. In ISWC/ASWC, 2007.
• 3: Ron Avnur , Joseph M. Hellerstein, Eddies: continuously adaptive query processing, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.261-272, May 15-18, 2000, Dallas, Texas, United States
• 4: Philip A. Bernstein , Dah-Ming W. Chiu, Using Semi-Joins to Solve Relational Queries, Journal of the ACM (JACM), v.28 n.1, p.25-40, Jan. 1981 [doi>10.1145/322234.322238]
• 5: Bio2RDF, semantic web atlas of postgenomic knowledge about human and mouse. http://www.bio2rdf.org/.
• 6: Uldis Bojārs , John G. Breslin , Vassilios Peristeras , Giovanni Tummarello , Stefan Decker, Interlinking the Social Web with Semantics, IEEE Intelligent Systems, v.23 n.3, p.29-40, May 2008 [doi>10.1109/MIS.2008.50]
• 7: J. Broekstra et al. Sesame: An architecture for storing and querying rdf data and schema information. In Spinning the Semantic Web, 2003.
• 8: 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
• 9: Dbpedia 3.2 downloads. http://wiki.dbpedia.org/Downloads32.
• 10: 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]
• 11: Amol Deshpande , Zachary Ives , Vijayshankar Raman, Adaptive query processing, Foundations and Trends in Databases, v.1 n.1, p.1-140, January 2007 [doi>10.1561/1900000001]
• 12: Open directory RDF dump. http://rdf.dmoz.org/.
• 13: Metaweb technologies: Freebase data dumps. http://download.freebase.com/datadumps/.
• 14: 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
• 15: 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]
• 16: 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]
• 17: A. Harth et al. Yars2: A federated repository for querying graph structured data from the web. In ISWC/ASWC, 2007.
• 18: Zachary G. Ives , Nicholas E. Taylor, Sideways Information Passing for Push-Style Query Processing, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.774-783, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497486]
• 19: Jena: a Semantic Web Framework for Java. http://jena.sourceforge.net/.
• 20: Donald Kossmann, The state of the art in distributed query processing, ACM Computing Surveys (CSUR), v.32 n.4, p.422-469, Dec. 2000 [doi>10.1145/371578.371598]
• 21: 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]
• 22: 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
• 23: MonetDB. http://monetdb.cwi.nl/.
• 24: Inderpal Singh Mumick , Hamid Pirahesh, Implementation of magic-sets in a relational database system, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.103-114, May 24-27, 1994, Minneapolis, Minnesota, United States
• 25: Thomas Neumann , Gerhard Weikum, RDF-3X: a RISC-style engine for RDF, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453927]
• 26: OpenRDF. http://www.openrdf.org/index.jsp.
• 27: PostgreSQL. http://www.postgresql.org/.
• 28: RDF-3X. http://www.mpi-inf.mpg.de/~neumann/rdf3x.
• 29: Semantic web challenge 2008. billion triples track. http://challenge.semanticweb.org/.
• 30: Praveen Seshadri , Joseph M. Hellerstein , Hamid Pirahesh , T. Y. Cliff Leung , Raghu Ramakrishnan , Divesh Srivastava , Peter J. Stuckey , S. Sudarshan, Cost-based optimization for magic: algebra and implementation, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.435-446, June 04-06, 1996, Montreal, Quebec, Canada
• 31: Lefteris Sidirourgos , Romulo Goncalves , Martin Kersten , Niels Nes , Stefan Manegold, Column-store support for RDF data management: not all swans are white, Proceedings of the VLDB Endowment, v.1 n.2, August 2008 [doi>10.1145/1454159.1454227]
• 32: 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
• 33: Konrad Stocker , Donald Kossmann , Reinhard Braumandl , Alfons Kemper, Integrating Semi-Join-Reducers into State of the Art Query Processors, Proceedings of the 17th International Conference on Data Engineering, p.575-584, April 02-06, 2001
• 34: 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]
• 35: 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]
• 36: O. Udrea, A. Pugliese, and V. S. Subrahmanian. Grin: A graph based rdf index. In AAAI, 2007.
• 37: Uniprot RDF. http://dev.isb-sib.ch/projects/uniprot-rdf/.
• 38: Cathrin Weiss , Panagiotis Karras , Abraham Bernstein, Hexastore: sextuple indexing for semantic web data management, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453965]
• 39: K. Wilkinson et al. Efficient rdf storage and retrieval in jena2. In SWDB, 2003.
• 40: Fei Wu , Daniel S. Weld, Automatically refining the wikipedia infobox ontology, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367583]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Performance

Keywords:
query processing, rdf