Showing cs.DBShow all
3 papers · 1 filter
cs.DB2025
Approximating Queries on Probabilistic Graphs
Antoine Amarilli, Timothy van Bremen, Octave Gaspard +1
Query evaluation over probabilistic databases is notoriously intractable -- not only in combined complexity, but often in data complexity as well. This motivates the study of appro…
cs.DB2025
Resilience for Regular Path Queries: Towards a Complexity Classification
Antoine Amarilli, Wolfgang Gatterbauer, Neha Makhija +2
The resilience problem for a query and an input set or bag database is to compute the minimum number of facts to remove from the database to make the query false. In this paper, we…
cs.DB2024
Tractable Circuits in Database Theory
Antoine Amarilli, Florent Capelli
This work reviews how database theory uses tractable circuit classes from knowledge compilation. We present relevant query evaluation tasks, and notions of tractable circuits. We t…