Estimating Result Size and Execution Times for Graph Queries.
Silke Trißl, Ulf Leser · 2010
Abstract. In recent years several languages have been proposed to pose queries on graphs. These languages allow to state graph queries that contain multiple node and path variables. Nodes and paths of the graph are incrementally bound to these variables when evaluating the query. For an efficient execution the order of the bindings is important. To optimize this order we must be able to estimate the sizes of intermediate result sets and the time required to produce these. Therefore, in this paper we present estimation functions for reachability and path queries. We show that it is possible to estimate the sizes and times using easy to pre-compute key features of a graph, such as number of nodes and edges, number of nodes without outgoing edges, and the outdegree of the node with highest degree. 1