Search Results

Documents authored by Segoufin, Luc

Document
DOI: 10.4230/LIPIcs.ICDT.2023.24
A Simple Algorithm for Consistent Query Answering Under Primary Keys

Authors: Diego Figueira, Anantha Padmanabha, Luc Segoufin, and Cristina Sirangelo

Published in: LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023)

Abstract
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 certain (i.e. whether it evaluates to true over all repairs of a given inconsistent database) is either polynomial time or coNP-complete. This conjecture has been verified for self-join-free and path queries. We propose a simple inflationary fixpoint algorithm for consistent query answering which, for a given database, naively computes a set Δ of subsets of database repairs with at most k facts, where k is the size of the query q. The algorithm runs in polynomial time and can be formally defined as: 1) Initialize Δ with all sets S of at most k facts such that S⊧ q. 2) Add any set S of at most k facts to Δ if there exists a block B (i.e., a maximal set of facts sharing the same key) such that for every fact a ∈ B there is a set S' ∈ Δ contained in S ∪ {a}. The algorithm answers "q is certain" iff Δ eventually contains the empty set. The algorithm correctly computes certainty when the query q falls in the polynomial time cases of the known dichotomies for self-join-free queries and path queries. For arbitrary Boolean conjunctive queries, the algorithm is an under-approximation: the query is guaranteed to be certain if the algorithm claims so. However, there are polynomial time certain queries (with self-joins) which are not identified as such by the algorithm.
Cite as

Diego Figueira, Anantha Padmanabha, Luc Segoufin, and Cristina Sirangelo. A Simple Algorithm for Consistent Query Answering Under Primary Keys. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{figueira_et_al:LIPIcs.ICDT.2023.24,
  author =	{Figueira, Diego and Padmanabha, Anantha and Segoufin, Luc and Sirangelo, Cristina},
  title =	{{A Simple Algorithm for Consistent Query Answering Under Primary Keys}},
  booktitle =	{26th International Conference on Database Theory (ICDT 2023)},
  pages =	{24:1--24:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-270-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{255},
  editor =	{Geerts, Floris and Vandevoort, Brecht},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.24},
  URN =		{urn:nbn:de:0030-drops-177663},
  doi =		{10.4230/LIPIcs.ICDT.2023.24},
  annote =	{Keywords: consistent query answering, primary keys, conjunctive queries}
}
Document
DOI: 10.4230/LIPIcs.CSL.2020.23
Order-Invariant First-Order Logic over Hollow Trees

Authors: Julien Grange and Luc Segoufin

Published in: LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)

Abstract
We show that the expressive power of order-invariant first-order logic collapses to first-order logic over hollow trees. A hollow tree is an unranked ordered tree where every non leaf node has at most four adjacent nodes: two siblings (left and right) and its first and last children. In particular there is no predicate for the linear order among siblings nor for the descendant relation. Moreover only the first and last nodes of a siblinghood are linked to their parent node, and the parent-child relation cannot be completely reconstructed in first-order.
Cite as

Julien Grange and Luc Segoufin. Order-Invariant First-Order Logic over Hollow Trees. In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 152, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{grange_et_al:LIPIcs.CSL.2020.23,
  author =	{Grange, Julien and Segoufin, Luc},
  title =	{{Order-Invariant First-Order Logic over Hollow Trees}},
  booktitle =	{28th EACSL Annual Conference on Computer Science Logic (CSL 2020)},
  pages =	{23:1--23:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-132-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{152},
  editor =	{Fern\'{a}ndez, Maribel and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2020.23},
  URN =		{urn:nbn:de:0030-drops-116661},
  doi =		{10.4230/LIPIcs.CSL.2020.23},
  annote =	{Keywords: order-invariance, first-order logic}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.2
The Power of Programs over Monoids in DA

Authors: Nathan Grosshans, Pierre McKenzie, and Luc Segoufin

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
The program-over-monoid model of computation originates with Barrington's proof that it captures the complexity class NC^1. Here we make progress in understanding the subtleties of the model. First, we identify a new tameness condition on a class of monoids that entails a natural characterization of the regular languages recognizable by programs over monoids from the class. Second, we prove that the class known as DA satisfies tameness and hence that the regular languages recognized by programs over monoids in DA are precisely those recognizable in the classical sense by morphisms from QDA. Third, we show by contrast that the well studied class of monoids called J is not tame and we exhibit a regular language, recognized by a program over a monoid from J, yet not recognizable classically by morphisms from the class QJ. Finally, we exhibit a program-length-based hierarchy within the class of languages recognized by programs over monoids from DA.
Cite as

Nathan Grosshans, Pierre McKenzie, and Luc Segoufin. The Power of Programs over Monoids in DA. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 2:1-2:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{grosshans_et_al:LIPIcs.MFCS.2017.2,
  author =	{Grosshans, Nathan and McKenzie, Pierre and Segoufin, Luc},
  title =	{{The Power of Programs over Monoids in DA}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{2:1--2:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.2},
  URN =		{urn:nbn:de:0030-drops-80909},
  doi =		{10.4230/LIPIcs.MFCS.2017.2},
  annote =	{Keywords: Programs over monoids, DA, lower-bounds}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2017.20
Constant Delay Enumeration for FO Queries over Databases with Local Bounded Expansion

Authors: Luc Segoufin and Alexandre Vigny

Published in: LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)

Abstract
We consider the evaluation of first-order queries over classes of databases with local bounded expansion. This class was introduced by Nesetril and Ossona de Mendez and generalizes many well known classes of databases, such as bounded degree, bounded tree width or bounded expansion. It is known that over classes of databases with local bounded expansion, first-order sentences can be evaluated in pseudo-linear time (pseudo-linear time means that for all \epsilon there exists an algorithm working in time O(n^{1+\epsilon})). Here, we investigate other scenarios, where queries are not sentences. We show that first-order queries can be enumerated with constant delay after a pseudo-linear preprocessing over any class of databases having locally bounded expansion. We also show that, in this context, counting the number of solutions can be done in pseudo-linear time.
Cite as

Luc Segoufin and Alexandre Vigny. Constant Delay Enumeration for FO Queries over Databases with Local Bounded Expansion. In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, pp. 20:1-20:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{segoufin_et_al:LIPIcs.ICDT.2017.20,
  author =	{Segoufin, Luc and Vigny, Alexandre},
  title =	{{Constant Delay Enumeration for FO Queries over Databases with Local Bounded Expansion}},
  booktitle =	{20th International Conference on Database Theory (ICDT 2017)},
  pages =	{20:1--20:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-024-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{68},
  editor =	{Benedikt, Michael and Orsi, Giorgio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.20},
  URN =		{urn:nbn:de:0030-drops-70602},
  doi =		{10.4230/LIPIcs.ICDT.2017.20},
  annote =	{Keywords: enumeration, first-order queries, local bounded expansion.}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.STACS.2014.13
A glimpse on constant delay enumeration (Invited Talk)

Authors: Luc Segoufin

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
We survey some of the recent results about enumerating the answers to queries over a database. We focus on the case where the enumeration is performed with a constant delay between any two consecutive solutions, after a linear time preprocessing. This cannot be always achieved. It requires restricting either the class of queries or the class of databases. We describe here several scenarios when this is possible.
Cite as

Luc Segoufin. A glimpse on constant delay enumeration (Invited Talk). In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 13-27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{segoufin:LIPIcs.STACS.2014.13,
  author =	{Segoufin, Luc},
  title =	{{A glimpse on constant delay enumeration}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{13--27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.13},
  URN =		{urn:nbn:de:0030-drops-45001},
  doi =		{10.4230/LIPIcs.STACS.2014.13},
  annote =	{Keywords: Enumeration, constant delay, logic}
}
Document
DOI: 10.4230/DagRep.1.10.37
Foundations of distributed data management (Dagstuhl Seminar 11421)

Authors: Serge Abiteboul, Alin Deutsch, Thomas Schwentick, and Luc Segoufin

Published in: Dagstuhl Reports, Volume 1, Issue 10 (2012)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 11421 ``Foundations of distributed data management''.
Cite as

Serge Abiteboul, Alin Deutsch, Thomas Schwentick, and Luc Segoufin. Foundations of distributed data management (Dagstuhl Seminar 11421). In Dagstuhl Reports, Volume 1, Issue 10, pp. 37-57, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Article{abiteboul_et_al:DagRep.1.10.37,
  author =	{Abiteboul, Serge and Deutsch, Alin and Schwentick, Thomas and Segoufin, Luc},
  title =	{{Foundations of distributed data management (Dagstuhl Seminar 11421)}},
  pages =	{37--57},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2012},
  volume =	{1},
  number =	{10},
  editor =	{Abiteboul, Serge and Deutsch, Alin and Schwentick, Thomas and Segoufin, Luc},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.1.10.37},
  URN =		{urn:nbn:de:0030-drops-33737},
  doi =		{10.4230/DagRep.1.10.37},
  annote =	{Keywords: XML Query language, Distribution, Incompleteness}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.81
Automata based verification over linearly ordered data domains

Authors: Luc Segoufin and Szymon Torunczyk

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
In this paper we work over linearly ordered data domains equipped with finitely many unary predicates and constants. We consider nondeterministic automata processing words and storing finitely many variables ranging over the domain. During a transition, these automata can compare the data values of the current configuration with those of the previous configuration using the linear order, the unary predicates and the constants. We show that emptiness for such automata is decidable, both over finite and infinite words, under reasonable computability assumptions on the linear order. Finally, we show how our automata model can be used for verifying properties of workflow specifications in the presence of an underlying database.
Cite as

Luc Segoufin and Szymon Torunczyk. Automata based verification over linearly ordered data domains. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 81-92, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{segoufin_et_al:LIPIcs.STACS.2011.81,
  author =	{Segoufin, Luc and Torunczyk, Szymon},
  title =	{{Automata based verification over linearly ordered data domains}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{81--92},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.81},
  URN =		{urn:nbn:de:0030-drops-30017},
  doi =		{10.4230/LIPIcs.STACS.2011.81},
  annote =	{Keywords: register automata, data values, linear order}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.93
Bottom-up automata on data trees and vertical XPath

Authors: Diego Figueira and Luc Segoufin

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
A data tree is a 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 trees with a decidable emptiness problem. It is essentially a bottom-up alternating automaton with one register, enriched with epsilon-transitions that perform tests on the data values of the subtree. We show that it captures the expressive power of the vertical fragment of XPath -- containing the child, descendant, parent and ancestor axes -- obtaining thus a decision procedure for its satisfiability problem.
Cite as

Diego Figueira and Luc Segoufin. Bottom-up automata on data trees and vertical XPath. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 93-104, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{figueira_et_al:LIPIcs.STACS.2011.93,
  author =	{Figueira, Diego and Segoufin, Luc},
  title =	{{Bottom-up automata on data trees and vertical XPath}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{93--104},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.93},
  URN =		{urn:nbn:de:0030-drops-30029},
  doi =		{10.4230/LIPIcs.STACS.2011.93},
  annote =	{Keywords: Decidability, XPath, Data trees, Bottom-up tree automata}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.344
Unary negation

Authors: Balder ten Cate and Luc Segoufin

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
We study fragments of first-order logic and of least fixed point logic that allow only unary negation: negation of formulas with at most one free variable. These logics generalize many interesting known formalisms, including modal logic and the mu-calculus, as well as conjunctive queries and monadic Datalog. We show that satisfiability and finite satisfiability are decidable for both fragments, and we pinpoint the complexity of satisfiability, finite satisfiability, and model checking. We also show that the unary negation fragment of first-order logic is model-theoretically very well behaved. In particular, it enjoys Craig interpolation and the Beth property.
Cite as

Balder ten Cate and Luc Segoufin. Unary negation. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 344-355, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{tencate_et_al:LIPIcs.STACS.2011.344,
  author =	{ten Cate, Balder and Segoufin, Luc},
  title =	{{Unary negation}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{344--355},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.344},
  URN =		{urn:nbn:de:0030-drops-30256},
  doi =		{10.4230/LIPIcs.STACS.2011.344},
  annote =	{Keywords: Decidability, Logic, Unary negation}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact