136 citations · 313 across the 25 of their papers we have counts for
5 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…
Possible and Certain Answers for Queries over Order-Incomplete Data
Antoine Amarilli, Mouhamadou Lamine Ba, Daniel Deutch +1
To combine and query ordered data from multiple sources, one needs to handle uncertainty about the possible orderings. Examples of such "order-incomplete" data include integrated e…
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…
Top-k Querying of Unknown Values under Order Constraints (Extended Version)
Antoine Amarilli, Yael Amsterdamer, Tova Milo +1
Many practical scenarios make it necessary to evaluate top-k queries over data items with partially unknown values. This paper considers a setting where the values are taken from a…