Using Color Refinement to Boost Enumeration and Counting for Acyclic CQs of Binary Schemas
<|reference_start|>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 $C_D$. The main ingredient of the color-index is a particular database $D_c$ whose active domain is $C_D$ 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| \cdot |D_c|)$ and constant delay enumeration. Furthermore, we can also count the number of results of $Q$ over $D$ in time $O(|Q| \cdot |D_c|)$. Given that $|D_c|$ 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.<|reference_end|>
@article{riveros2024using,
    title={Using Color Refinement to Boost Enumeration and Counting for Acyclic CQs
  of Binary Schemas},
    author={Cristian Riveros, Benjamin Scheidt, Nicole Schweikardt},
    journal={arXiv preprint arXiv:2405.12358},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.12358},
    primaryClass={cs.DB cs.LO}
}