Graphs-at-a-time: query language and access methods for graph databases

ABSTRACT

With the prevalence of graph data in a variety of domains, there is an increasing need for a language to query and manipulate graphs with heterogeneous attributes and structures. We propose a query language for graph databases that supports arbitrary attributes on nodes, edges, and graphs. In this language, graphs are the basic unit of information and each query manipulates one or more collections of graphs. To allow for flexible compositions of graph structures, we extend the notion of formal languages from strings to the graph domain. We present a graph algebra extended from the relational algebra in which the selection operator is generalized to graph pattern matching and a composition operator is introduced for rewriting matched graphs. Then, we investigate access methods of the selection operator. Pattern matching over large graphs is challenging due to the NP-completeness of subgraph isomorphism. We address this by a combination of techniques: use of neighborhood subgraphs and profiles, joint reduction of the search space, and optimization of the search order. Experimental results on real and synthetic large graphs demonstrate that our graph specific optimizations outperform an SQL-based implementation by orders of magnitude.

REFERENCES

• 1: S. Asthana et al. Predicting protein complex membership using probabilistic network reliability. Genome Research, May 2004.
• 2: Stefano Berretti , Alberto Del Bimbo , Enrico Vicario, Efficient Matching and Indexing of Graph Models in Content-Based Retrieval, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.10, p.1089-1105, October 2001 [doi>10.1109/34.954600]
• 3: S. Boag, D. Chamberlin, M. F. Fernández, D. Florescu, J. Robie, and J. Siméon. XQuery 1.0: An XML query language. W3C, http://www.w3.org/TR/xquery/, 2007.
• 4: C. Branden and J. Tooze. Introduction to protein structure. Garland, 2 edition, 1998.
• 5: Surajit Chaudhuri, An overview of query optimization in relational systems, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.34-43, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275492]
• 6: Li Chen , Amarnath Gupta , M. Erdem Kurul, Stack-based algorithms for pattern matching on DAGs, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 7: James Cheng , Yiping Ke , Wilfred Ng , An Lu, Fg-index: towards verification-free query processing on graph databases, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247574]
• 8: J. Cheng, J. X. Yu, X. Lin, H. Wang, and P. S. Yu. Fast computation of reachability labeling for large graphs. In EDBT, pages 961--979, 2006.
• 9: Edith Cohen , Eran Halperin , Haim Kaplan , Uri Zwick, Reachability and Distance Queries via 2-Hop Labels, SIAM Journal on Computing, v.32 n.5, p.1338-1355, 2003 [doi>10.1137/S0097539702403098]
• 10: Mariano P. Consens , Alberto O. Mendelzon, GraphLog: a visual formalism for real life recursion, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.404-416, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298591]
• 11: P. Erdõs and A. Rényi. On random graphs I. Publ. Math. Debrecen, (6):290--297.
• 12: Gene Ontology. http://www.geneontology.org/.
• 13: Ralf Hartmut Güting, GraphDB: Modeling and Querying Graphs in Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.297-308, September 12-15, 1994
• 14: Marc Gyssens , Jan Paredaens , Dirk van Gucht, A graph-oriented object database model, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.417-424, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298593]
• 15: Huahai He , Ambuj K. Singh, Closure-Tree: An Index Structure for Graph Queries, Proceedings of the 22nd International Conference on Data Engineering, p.38, April 03-07, 2006 [doi>10.1109/ICDE.2006.37]
• 16: J. Hopcroft and R. Karp. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Computing, 1973.
• 17: John E. Hopcroft , Rajeev Motwani , Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation (3rd Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2006
• 18: H. V. Jagadish , Laks V. S. Lakshmanan , Divesh Srivastava , Keith Thompson, TAX: A Tree Algebra for XML, Revised Papers from the 8th International Workshop on Database Programming Languages, p.149-164, September 08-10, 2001
• 19: H. Jiang, H. Wang, P. S. Yu, and S. Zhou. GString: A novel approach for efficient search in graph databases. In ICDE, 2007.
• 20: JeongKyu Lee , JungHwan Oh , Sae Hwang, STRG-Index: spatio-temporal region graph indexing for large video databases, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066239]
• 21: Ulf Leser, A query language for biological networks, Bioinformatics, v.21 n.2, p.33-39, January 2005 [doi>10.1093/bioinformatics/bti1105]
• 22: F. Manola and E. Miller. RDF Primer. W3C, http://www.w3.org/TR/rdf-primer/, 2004.
• 23: E. Prud'hommeaux and A. Seaborne. SPARQL query language for RDF. W3C, http://www.w3.org/TR/rdf-sparql-query/, 2007.
• 24: Raghu Ramakrishnan , Johannes Gehrke, Database Management Systems, McGraw-Hill, Inc., New York, NY, 1999
• 25: J. Rekers , A. Schurr, A graph grammar approach to graphical parsing, Proceedings of the 11th International IEEE Symposium on Visual Languages, p.195, September 05-09, 1995
• 26: Grzegorz Rozenberg, Handbook of graph grammars and computing by graph transformation: volume I. foundations, World Scientific Publishing Co., Inc., River Edge, NJ, 1997
• 27: Ralf Schenkel , Anja Theobald , Gerhard Weikum, Efficient Creation and Incremental Maintenance of the HOPI Index for Complex XML Document Collections, Proceedings of the 21st International Conference on Data Engineering, p.360-371, April 05-08, 2005 [doi>10.1109/ICDE.2005.57]
• 28: Nigel Shadbolt , Tim Berners-Lee , Wendy Hall, The Semantic Web Revisited, IEEE Intelligent Systems, v.21 n.3, p.96-101, May 2006 [doi>10.1109/MIS.2006.62]
• 29: Dennis Shasha , Jason T. L. Wang , Rosalba Giugno, Algorithmics and applications of tree and graph searching, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543620]
• 30: L. Sheng, Z. M. Ozsoyoglu, and G. Ozsoyoglu. A graph query language and its query processing. In ICDE, 1999.
• 31: Yuanyuan Tian , Richard C. Mceachin , Carlos Santos , David J. States , Jignesh M. Patel, SAGA: a subgraph matching tool for biological graphs, Bioinformatics, v.23 n.2, p.232-239, January 2007 [doi>10.1093/bioinformatics/btl571]
• 32: Silke Trißl , Ulf Leser, Fast and practical indexing and querying of very large graphs, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247573]
• 33: Haixun Wang , Hao He2 , Jun Yang , Philip S. Yu , Jeffrey Xu Yu, Dual Labeling: Answering Graph Reachability Queries in Constant Time, Proceedings of the 22nd International Conference on Data Engineering, p.75, April 03-07, 2006 [doi>10.1109/ICDE.2006.53]
• 34: D. W. Williams, J. Huan, and W. Wang. Graph database indexing using structured graph decomposition. In ICDE, 2007.
• 35: Xifeng Yan , Philip S. Yu , Jiawei Han, Graph indexing: a frequent structure-based approach, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007607]
• 36: S. Zhang, M. Hu, and J. Yang. TreePi: A novel graph indexing method. In ICDE, 2007.
• 37: Peixiang Zhao , Jeffrey Xu Yu , Philip S. Yu, Graph indexing: tree + delta <= graph, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

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

General Terms:
Algorithms, Languages, Performance

Keywords:
graph algebra, graph query language, query optimization