Query processing for graph-structured data
Jeffrey Xu Yu, Jiefeng Cheng · 2007
Graph-structured data is enjoying an increasing popularity among Web technology and new data management and archiving techniques. Numerous applications work with graphs and need to query reachability among nodes in graphs. A 2-hop cover can compactly represent the whole edge transitive closure of a graph in O (|V| · |E| 1/2) space, providing a time- and space-efficient solution to reachability query processing. We study fast computation and maintenance of 2-hop covers for any kind of graphs. Besides, we study efficient processing of graph pattern queries, which consists of multiple reachability conditions. Our work processes graph pattern queries efficiently by a join/semi-join approach. We can find an optimal join/semi-join order to process graph pattern queries with manageable overhead. We have conducted extensive experiments to confirm the efficiency our approach.