2 citations · 2 across the 2 of their papers we have counts for
8 papers
A Simple Algorithm for Consistent Query Answering under Primary Keys
Diego Figueira, Anantha Padmanabha, Luc Segoufin +1
We consider the dichotomy conjecture for consistent query answering under primary key constraints. It states that, for every fixed Boolean conjunctive query q, testing whether q is…
Conjunctive Queries With Self-Joins, Towards a Fine-Grained Complexity Analysis
Nofar Carmeli, Luc Segoufin
Even though query evaluation is a fundamental task in databases, known classifications of conjunctive queries by their fine-grained complexity only apply to queries without self-jo…
Tameness and the power of programs over monoids in DA
Nathan Grosshans, Pierre Mckenzie, Luc Segoufin
The program-over-monoid model of computation originates with Barrington's proof that the model captures the complexity class . Here we make progress in understanding…
Enumerating Answers to First-Order Queries over Databases of Low Degree
Arnaud Durand, Nicole Schweikardt, Luc Segoufin
A class of relational databases has low degree if for all , all but finitely many databases in the class have degree at most , where is the size of the database. Typi…
First-order queries on classes of structures with bounded expansion
Wojtek Kazana, Luc Segoufin
We consider the evaluation of first-order queries over classes of databases with bounded expansion. The notion of bounded expansion is fairly broad and generalizes bounded degree,…
Bottom-up automata on data trees and vertical XPath
Diego Figueira, Luc Segoufin
A data tree is a finite tree whose every node carries a label from a finite alphabet and a datum from some infinite domain. We introduce a new model of automata over unranked data…