direct access 1functional dependencies 1information-theoretic bounds 1join queries 1preprocessing complexity 1
From the 1 of 3 linked papers with an AI index.
3 papers
cs.DB2026
Lexicographic Direct Access with Functional Dependencies
Florent Capelli, Nofar Carmeli, Stefan Mengel
The paper investigates how quickly one can retrieve join query results in lexicographic order from databases that satisfy functional dependencies, providing fine‑grained lower and…
cs.DB2026
Dynamic direct access of MSO query evaluation over strings
Pierre Bourhis, Florent Capelli, Stefan Mengel +1
We study the problem of evaluating a Monadic Second Order (MSO) query over strings under updates in the setting of direct access. We present an algorithm that, given an MSO query w…
cs.AI2026
A canonical generalization of OBDD
Florent Capelli, YooJung Choi, Stefan Mengel +2
We introduce Tree Decision Diagrams (TDD) as a model for Boolean functions that generalizes OBDD. They can be seen as a restriction of structured d-DNNF; that is, d-DNNF that respe…