3 citations · 5 across the 4 of their papers we have counts for
8 papers · 1 filter
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…
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…
Worst-case Analysis for Interactive Evaluation of Boolean Provenance
Antoine Amarilli, Yael Amsterdamer
In recent work, we have introduced a framework for fine-grained consent management in databases, which combines Boolean data provenance with the field of interactive Boolean evalua…
Equivalent Rewritings on Path Views with Binding Patterns
Julien Romero, Nicoleta Preda, Antoine Amarilli +1
A view with a binding pattern is a parameterized query on a database. Such views are used, e.g., to model Web services. To answer a query on such views, the views have to be orches…
Enumeration on Trees with Tractable Combined Complexity and Efficient Updates
Antoine Amarilli, Pierre Bourhis, Stefan Mengel +1
We give an algorithm to enumerate the results on trees of monadic second-order (MSO) queries represented by nondeterministic tree automata. After linear time preprocessing (in the…
Evaluating Datalog via Tree Automata and Cycluits
Antoine Amarilli, Pierre Bourhis, Mikaël Monet +1
We investigate parameterizations of both database instances and queries that make query evaluation fixed-parameter tractable in combined complexity. We show that clique-frontier-gu…