An Efficient Features-Based Processing Technique for Supergraph Queries

Graphs are widely used for modeling complicated data such as social networks, chemical compounds, protein interac-tions, XML documents and multimedia databases. To be able to effectively understand and utilize any collection of graphs, a graph database that efficiently supports elemen-tary querying mechanisms is crucially required. Supergraph query is an important type of graph queries which has many practical applications. Given a graph database D, the an-swer set of a supergraph query q is computed by retrieving all graphs in D which are fully contained in q. A primary challenge in computing the answers of graph queries is that pair-wise comparisons of graphs are usually hard problems. For example, subgraph isomorphism is known to be NP-complete. Clearly, the success of any graph database appli-cation is directly dependent on the efficiency of the graph indexing and query processing mechanisms. In this paper, we study the problem of using the relational infrastructure to achieve an efficient evaluation of supergraph queries. We rely on an effective and efficient layer of features-based sum-mary structures, called graph features knowledge, to reduce the required number of pair-wise graph comparisons and boost the efficiency of query processing. Finally, we con-duct an extensive set of experiments on real and synthetic data sets to demonstrate the efficiency and the scalability of our approach