38 citations · 99 across the 20 of their papers we have counts for
3 papers · 1 filter
Connecting Width and Structure in Knowledge Compilation (Extended Version)
Antoine Amarilli, Mikaël Monet, Pierre Senellart
Several query evaluation tasks can be done via knowledge compilation: the query result is compiled as a lineage circuit from which the answer can be determined. For such tasks, it…
Conjunctive Queries on Probabilistic Graphs: Combined Complexity
Antoine Amarilli, Mikaël Monet, Pierre Senellart
Query evaluation over probabilistic databases is known to be intractable in many cases, even in data complexity, i.e., when the query is fixed. Although some restrictions of the qu…
Combined Tractability of Query Evaluation via Tree Automata and Cycluits (Extended Version)
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 introduce a new Datalog frag…