Data Based Elegant Models for Super Graph Query Processing
Mohamed Saber, Mostafa Aref, Tarek F. Gharib
Journal of Information Technology Review, Vol. 2, No. 1, 2011.
DOI: 
Link: http://www.dline.info/jitr/fulltext/v2n1/5.pdf
Abstract:
Graphs particularly the data models based ones, have proved to make significant impact on many applications. Efficient query processing over graph databases serves these applications. Having a graph query q, super-graph query processing finds all the graphs g in a database of graphs D where g is contained in q (g q). Because graph databases contain a lot of graphs and because sub-graph isomorphic tests are NP-complete, an indexingbased technique should be adopted. Now through this study we advocate a system for an optimal supergraph query making. The technique consists of an index called eIndex and a query processing algorithm. Given a query graph, the database is filtered to generate candidate graphs. The elegance of the proposed querying lies in consideration the full structure of the database graphs besides considering the frequent fragments. Through polynomial time algorithms, the proposed technique reduces the subgraph isomorphism tests required for query processing and hence the total processing time is reduced. We have shown evidences for building eIndex which consumes comparatively less time and space than other methods.