Estimating the Size of Path Relations

Abstract:

(Paper not available) We present a framework for estimating the size of path relations. We demonstrate the framework can be instantiated to provide a linear-time estimating algorithm for the size of the transitive closure of a sparse relation. We show that estimating the size of regular path relations over sparse graphs is at least as hard as estimating the size of transitive closures over arbitrary graphs. Our algorithm can be used to provide size estimates for generalizations of the transitive closure, including some recursive Datalog
queries. Such estimating algorithms are essential if database systems that support recursive relations or fixpoints are to be able to optimize queries and avoid infeasible computations.