Using Color Refinement to Boost Enumeration and Counting for Acyclic CQs of Binary Schemas

We present an index structure, called the color-index, to boost the evaluation of acyclic conjunctive queries (ACQs) over binary schemas. The color-index is based on the color refinement algorithm, a widely used subroutine for graph isomorphism testing algorithms. Given a database D, we use a suitable version of the color refinement algorithm to produce a stable coloring of D, an assignment from the active domain of D to a set of colors CD. The main ingredient of the color-index is a particular database Dc whose active domain is CD and whose size is at most $|D|$. Using the color-index, we can evaluate any free-connex ACQ Q over D with preprocessing time O(|Q| · |Dc|) and constant delay enumeration. Furthermore, we can also count the number of results of Q over D in time O(|Q| · |Dc|). Given that |Dc| could be much smaller than $|D|$ (even constant-size for some families of databases), the color-index is the first index structure for evaluating free-connex ACQs that allows efficient enumeration and counting with performance that may be strictly smaller than the database size.