GBLENDER: towards blending visual query formulation and query processing in graph databases

ABSTRACT

Given a graph database D and a query graph g, an exact subgraph matching query asks for the set S of graphs in D that contain g as a subgraph. This type of queries find important applications in several domains such as bioinformatics and chemoinformatics, where users are generally not familiar with complex graph query languages. Consequently, user-friendly visual interfaces which support query graph construction can reduce the burden of data retrieval for these users. Existing techniques for subgraph matching queries built on top of such visual framework are designed to optimize the time required in retrieving the result set S from D, assuming that the whole query graph has been constructed. This leads to sub-optimal system response time as the query processing is initiated only after the user has finished drawing the query graph.

In this paper, we take the first step towards exploring a novel graph query processing paradigm, where instead of processing a query graph after its construction, it interleaves visual query construction and processing to improve system response time. To realize this, we present an algorithm called GBLENDER that prunes false results and prefetches partial query results by exploiting the latency offered by the visual query formulation. It employs a novel action-aware indexing scheme that exploits users' interaction characteristics with visual interfaces to support efficient retrieval. Extensive experiments on both real and synthetic datasets demonstrate the effectiveness and efficiency of our solution.

References

1. S. S. BHOWMICK, S. PRAKASH. Every Click You Make, I Will be Fetching It: Efficient XML Query Processing in RDBMS Using GUI-driven Prefetching. In ICDE, 2006.
2. J. CHENG, Y. KE, W. NG, A. LU. FG-Index: Towards Verification-Free Query Processing On Graph Databases. In SIGMOD, 2007.
3. M. P. CONSENS, A. O. MENDELZON. GraphLog: A Visual Formalism for Real Life Recursion. In PODS, 1990.
4. S. A. COOK. The Complexity of Theorem-Proving Procedures. In STOC, 1971.
5. H. HE, A. K. SINGH. Closure-Tree: An Index Structure for Graph Queries. In ICDE, 2006.
6. H. HE, A. K. SINGH. Graphs-at-a-time: Query Language and Access Methods for Graph Databases. In SIGMOD, 2008.
7. J. P. HUAN, W. WANG. Efficient Mining of Frequent Subgraph in the Presence of Isomorphism. In ICDM, 2003.
8. H. V. JAGADISH, A. CHAPMAN, A. ELKISS ET AL. Making Database Systems Usable. In ACM SIGMOD, 2007.
9. H. JIANG, H. WANG, P. S. YU, S. ZHOU. GString: A Novel Approach for Efficient Search in Graph Databases. In ICDE, 2007.
10. U. LESER. A Query Language for Biological Networks. In Bioinformatics, 21:ii33--ii39, 2005.
11. E. PIETRIGA. A Toolkit for Addressing HCI Issues in Visual Language Environments. In IEEE Symp. on Vis. Lang. and Human-Centric Comp., 2005.
12. H. SHANG, Y. ZHANG, X. LIN, J. X. YU. Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism. In VLDB, 2008.
13. S. TRIL, U. LESER. Fast and Practical Indexing and Querying of Very Large Graphs. In SIGMOD, 2007.
14. D. W. WILLIAMS, J. HUAN, W. WANG. Graph Database Indexing Using Structured Graph Decomposition. In ICDE, 2007.
15. J. R. ULLMAN. An Algorithm for Subgraph Isomorphism. J. ACM, 23(1):31--42, 1976.
16. X. YAN, J. HAN. gSpan: Graph-based Substructure Pattern Mining. In ICDM, 2002.
17. X. YAN, P. S. YU, J. HAN. Graph Indexing: A Frequent Structure-Based Approach. In SIGMOD, 2004.
18. X. YAN, P. S. YU, J. HAN. Substructure Similarity Search in Graph Databases. In SIGMOD, 2005.
19. S. ZHANG, M. HU, J. YANG. TreePi: A Novel Graph Indexing Method. In ICDE, 2007.
20. P. ZHAO, J. X. YU, P. S. YU. Graph Indexing: Tree + delta >= Graph. In VLDB, 2007.
21. J. L. ZOU, L. CHEN, Y. LU. A Novel Spectral Coding in a Large Graph Database. In EDBT, 2008.

Index Terms

• Information systems

  • Data management systems

    • Database management system engines

      • Database query processing

• Theory of computation

  • Theory and algorithms for application domains

    • Database theory

      • Database query processing and optimization (theory)