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

arXiv: https://arxiv.org/abs/2405.12358 · HTML: https://mlsanity.com/paper/2405.12358/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 May 2024.

## Built on by (most cited first, 1 of 1)

- [On the Expressibility of the Reconstructional Color Refinement](https://mlsanity.com/paper/2406.09351/) (2024)

## Abstract (arXiv)

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.