Structural Indexing of Relational Databases for the Evaluation of Free-Connex Acyclic Conjunctive Queries

Cristian Riveros, Benjamin Scheidt, Nicole Schweikardt · 2026

Read Structural Indexing of Relational Databases for the Evaluation of Free-Connex Acyclic Conjunctive Queries by Cristian Riveros, Benjamin Scheidt, Nicole Schweikardt (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-04757.txt.

Description

Cristian Riveros, Benjamin Scheidt, and Nicole Schweikardt index a database by its symmetries rather than its values, in a 2026 arXiv paper. Ordinary indexes sort entries or hash them. This one compresses a relational database into an auxiliary structure whose size reflects how many structurally distinct roles its tuples play, as measured by a relational color refinement procedure. For graphs, that count is the minimal equitable partition — tiny for trees and constant for regular graphs.

Against that index, an important query class becomes cheap. For any free-connex acyclic conjunctive query, the authors prove the answers can be counted, or enumerated with constant delay, after preprocessing linear in the small auxiliary database rather than the full one. Even a database with no symmetries at all keeps the index linear, so nothing is lost — and where structure exists, query evaluation can run in time strictly below the database size.

Catalog record

CREATORCristian Riveros, Benjamin Scheidt, Nicole Schweikardt
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE209 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-04757

Browse the full library · About the Tower of Babel