Autocomplete Subgraph Query Framework for Graph Databases (Abstract)

Composing queries have been evidently a tedious task. This is particular true to graph queries, as they are typically verbose and prone to typos. It is compounded with the fact that graph schemas can be missing or too loose for helping query formulation. Despite the great success of query formulation aids, in particular, automatic query completion, to the best of our knowledge, auto subgraph query completion has not been investigated. In this prospectus, we propose a novel framework for auto subgraph query completion (called AUTOC). Given a user query q as input, AUTOC returns a ranked list of query increments △q as output, as opposed to answers of q. Further, users may iteratively apply the increments to compose their queries. The main techniques in AUTOC can be described as follows. First, we design the logical unit for query increments. We propose novel c-prime features of a graph database, which are frequent subgraphs that (i) form larger frequent subgraphs and (ii) is composed by smaller c-prime features in no more than c ways. Second, we represent a query by c-prime features and propose query composition to enlarge the query with a query increment. Third, we propose a novel index called feature DAG (denoted as FDAG) to efficiently locate candidate query increments and rank them according to a given users’ intent. We have conducted an extensive experimental evaluation and a shorter usability test. The results show that our proposed techniques reduce query formulation times and the optimizations are effective.

This study forms the foundation of a stream of research of subgraph query feedback for graph databases. For example, AUTOC can be readily extended to subgraph similarity search. AUTOC can be extended to make correction on subgraph queries. Finally, the prospectus focuses on data graphs of modest sizes, e.g. molecules and compounds. AUTOC may be extended to support large graphs such as social networks (Facebook) and co-authorship networks (DBLP).