9 Search Results for "Brault-Baron, Johann"

Document
DOI: 10.4230/LIPIcs.ICDT.2026.16
Gamma Acyclicity, Annotated Relations, and Consistency Witness Functions

Authors: Albert Atserias and Phokion G. Kolaitis

Published in: LIPIcs, Volume 365, 29th International Conference on Database Theory (ICDT 2026)

Abstract
During the early days of relational database theory it was realized that "acyclic" database schemas possess a number of desirable properties. In fact, three different notions of "acyclicity" were identified and investigated during the 1980s, namely, α-acyclicity, β-acyclicity, and γ-acyclicity. Much more recently, the study of α-acyclicity was extended to annotated relations, where the annotations are values from some positive commutative monoid. The recent results about α-acyclic schemas and annotated relations give rise to results about β-acyclic schemas and annotated relations, since a schema is β-acyclic if and only if every sub-schema of it is α-acyclic. Here, we study γ-acyclic schemas and annotated relations. Our main finding is that the characterization of γ-acyclic schemas in terms of monotone sequential join expression extends to annotated relations, provided the annotations come from a positive commutative monoid that has the inner consistency property. Furthermore, the results reported here shed light on the role of the join of two standard relations. Specifically, our results reveal that the only relevant property of the join of two standard relations is that it is a witness to the consistency of the two relations, provided that these two relations are consistent. For the more abstract setting of annotated relations, this property of the standard join is captured by the notion of a consistency witness function, a notion which we systematically utilize in this work.
Cite as

Albert Atserias and Phokion G. Kolaitis. Gamma Acyclicity, Annotated Relations, and Consistency Witness Functions. In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{atserias_et_al:LIPIcs.ICDT.2026.16,
  author =	{Atserias, Albert and Kolaitis, Phokion G.},
  title =	{{Gamma Acyclicity, Annotated Relations, and Consistency Witness Functions}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-413-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{365},
  editor =	{ten Cate, Balder and Funk, Maurice},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2026.16},
  URN =		{urn:nbn:de:0030-drops-256304},
  doi =		{10.4230/LIPIcs.ICDT.2026.16},
  annote =	{Keywords: annotated relations, gamma-acyclicity, consistency witness functions}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2026.18
Output-Sensitive Evaluation of Acyclic Conjunctive Regular Path Queries

Authors: Mahmoud Abo Khamis, Alexandru-Mihai Hurjui, Ahmet Kara, Dan Olteanu, Dan Suciu, and Zilu Tian

Published in: LIPIcs, Volume 365, 29th International Conference on Database Theory (ICDT 2026)

Abstract
Conjunctive Regular Path Queries, or CRPQs for short, are an essential construct in graph query languages. In this paper, we propose the first output-sensitive algorithm for evaluating acyclic CRPQs. It is output-sensitive in the sense that its complexity is a function of the sizes of the input graph and of the query output and not of the output sizes of the regular expressions that appear in the query, as these latter sizes can be larger than the query output size. Our algorithm proceeds in two stages. In the first stage, it contracts the given query into a free-connex acyclic one such that the output of the original query can be obtained from the output of the contracted one. This contraction removes bound variables by composing regular expressions or by promoting bound variables to free ones. The minimum necessary number of promoted bound variables gives the contraction width, which is a novel parameter specific to CRPQs. In the second stage, our algorithm evaluates the free-connex acyclic CRPQ and projects away the columns of the promoted bound variables. It ensures output-sensitivity by computing the calibrated outputs of the regular expressions appearing in the free-connex acyclic CRPQ in time proportional to their sizes. Our algorithm has lower complexity than the state-of-the-art approaches for problem instances where the query output is asymptotically smaller than the output sizes of the regular expressions that appear in the query.
Cite as

Mahmoud Abo Khamis, Alexandru-Mihai Hurjui, Ahmet Kara, Dan Olteanu, Dan Suciu, and Zilu Tian. Output-Sensitive Evaluation of Acyclic Conjunctive Regular Path Queries. In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 18:1-18:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{abokhamis_et_al:LIPIcs.ICDT.2026.18,
  author =	{Abo Khamis, Mahmoud and Hurjui, Alexandru-Mihai and Kara, Ahmet and Olteanu, Dan and Suciu, Dan and Tian, Zilu},
  title =	{{Output-Sensitive Evaluation of Acyclic Conjunctive Regular Path Queries}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{18:1--18:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-413-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{365},
  editor =	{ten Cate, Balder and Funk, Maurice},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2026.18},
  URN =		{urn:nbn:de:0030-drops-256321},
  doi =		{10.4230/LIPIcs.ICDT.2026.18},
  annote =	{Keywords: graph databases, regular path queries, output-sensitive algorithms}
}
Document
Database Theory in Action
DOI: 10.4230/LIPIcs.ICDT.2026.27
Database Theory in Action: Direct Access to Query Answers

Authors: Jiayin Hu and Nikolaos Tziavelis

Published in: LIPIcs, Volume 365, 29th International Conference on Database Theory (ICDT 2026)

Abstract
Direct access asks for the retrieval of query answers by their ranked position, given a query and a desired order. While the time complexity of data structures supporting such accesses has been studied in depth, and efficient algorithms for many queries and common orders are known, their practical performance has received little attention. We provide an implementation covering a wide range of queries and orders; it allows us to investigate intriguing practical aspects, including the comparative performance of database systems and the relationship between direct access and its single-access counterpart.
Cite as

Jiayin Hu and Nikolaos Tziavelis. Database Theory in Action: Direct Access to Query Answers. In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 27:1-27:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hu_et_al:LIPIcs.ICDT.2026.27,
  author =	{Hu, Jiayin and Tziavelis, Nikolaos},
  title =	{{Database Theory in Action: Direct Access to Query Answers}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{27:1--27:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-413-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{365},
  editor =	{ten Cate, Balder and Funk, Maurice},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2026.27},
  URN =		{urn:nbn:de:0030-drops-256411},
  doi =		{10.4230/LIPIcs.ICDT.2026.27},
  annote =	{Keywords: direct access, conjunctive queries, joins, ranking}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.73
Colouring Probe H-Free Graphs

Authors: Daniël Paulusma, Johannes Rauch, and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
The NP-complete problems Colouring and k-Colouring (k ≥ 3) are well studied on H-free graphs, i.e., graphs that do not contain some fixed graph H as an induced subgraph. We research to what extent the known polynomial-time algorithms for H-free graphs can be generalized if we only know some of the edges of the input graph. We do this by considering the classical probe graph model introduced in the early nineties. For a graph H, a partitioned probe H-free graph (G,P,N) consists of a graph G = (V,E), together with a set P ⊆ V of probes and an independent set N = V ⧵ P of non-probes, such that G+F is H-free for some edge set F ⊆ binom(N,2). We show the following: - We fully classify Colouring on partitioned probe H-free graphs and show that the obtained complexity dichotomy differs from the known dichotomy of Colouring for H-free graphs. - We fully classify 3-Colouring on partitioned probe P_t-free graphs: we prove polynomial-time solvability for t ≤ 5 and NP-completeness for t ≥ 6. In contrast, 3-Colouring on P_t-free graphs is known to be polynomial-time solvable for t ≤ 7 and quasi-polynomial-time solvable for t ≥ 8. Our main result is our polynomial-time algorithm for 3-Colouring on partitioned P₅-free graphs. For this result, and also for all our other polynomial-time results, we do not need to know the edge set F; we only need to know its existence. Moreover, the class of probe P₅-free graphs includes not only paths of arbitrary length but even all bipartite graphs and is much richer than the class of P₅-free graphs. The latter is also evidenced by the fact that there exist graph problems, such as Matching Cut, that are known to be polynomial-time solvable for P₅-free graphs but NP-complete for partitioned probe P₅-free graphs. In particular, unlike the class of 3-colourable P₅-free graphs, the class of 3-colourable probe P₅-free graphs has unbounded mim-width. Hence, our polynomial-time result for 3-Colouring for probe P₅-free graphs suggests that there may be another, deeper overarching reason why 3-Colouring is polynomial-time solvable for P₅-free graphs.
Cite as

Daniël Paulusma, Johannes Rauch, and Erik Jan van Leeuwen. Colouring Probe H-Free Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 73:1-73:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{paulusma_et_al:LIPIcs.STACS.2026.73,
  author =	{Paulusma, Dani\"{e}l and Rauch, Johannes and van Leeuwen, Erik Jan},
  title =	{{Colouring Probe H-Free Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{73:1--73:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.73},
  URN =		{urn:nbn:de:0030-drops-255621},
  doi =		{10.4230/LIPIcs.STACS.2026.73},
  annote =	{Keywords: colouring, probe graph, forbidden induced subgraph, complexity dichotomy}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.88
Color Refinement for Relational Structures

Authors: Benjamin Scheidt and Nicole Schweikardt

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
Color Refinement, also known as Naive Vertex Classification, is a classical method to distinguish graphs by iteratively computing a coloring of their vertices. While it is traditionally used as an imperfect way to test for isomorphism, the algorithm has permeated many other, seemingly unrelated, areas of computer science. The method is algorithmically simple, and it has a well-understood distinguishing power: it has been logically characterized by Immerman and Lander (1990) and Cai, Fürer, Immerman (1992), who showed that it distinguishes precisely those graphs that can be distinguished by a sentence of first-order logic with counting quantifiers and only two variables. A combinatorial characterization was given by Dvořák (2010), who showed that it distinguishes precisely those graphs that differ in the number of homomorphisms from some tree. In this paper, we introduce Relational Color Refinement (RCR, for short), a generalization of the Color Refinement method from graphs to arbitrary relational structures, whose distinguishing power admits the equivalent combinatorial and logical characterizations as Color Refinement has on graphs: we show that RCR distinguishes precisely those structures that differ in the number of homomorphisms from an acyclic connected relational structure. Further, we show that RCR distinguishes precisely those structures that are distinguished by a sentence of the guarded fragment of first-order logic with counting quantifiers. Additionally, we show that for every fixed finite relational signature, RCR can be implemented to run on structures of that signature in time O(N⋅log N), where N denotes the number of tuples present in the structure.
Cite as

Benjamin Scheidt and Nicole Schweikardt. Color Refinement for Relational Structures. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 88:1-88:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{scheidt_et_al:LIPIcs.MFCS.2025.88,
  author =	{Scheidt, Benjamin and Schweikardt, Nicole},
  title =	{{Color Refinement for Relational Structures}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{88:1--88:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.88},
  URN =		{urn:nbn:de:0030-drops-241958},
  doi =		{10.4230/LIPIcs.MFCS.2025.88},
  annote =	{Keywords: color refinement, counting logics, homomorphism counts, homomorphism indistinguishability, guarded logics, pebble games, relational structures, alpha-acyclicity, join-trees}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2025.12
Tractable Conjunctive Queries over Static and Dynamic Relations

Authors: Ahmet Kara, Zheng Luo, Milos Nikolic, Dan Olteanu, and Haozhe Zhang

Published in: LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025)

Abstract
We investigate the evaluation of conjunctive queries over static and dynamic relations. While static relations are given as input and do not change, dynamic relations are subject to inserts and deletes. We characterise syntactically three classes of queries that admit constant update time and constant enumeration delay. We call such queries tractable. Depending on the class, the preprocessing time is linear, polynomial, or exponential (under data complexity, so the query size is constant). To decide whether a query is tractable, it does not suffice to analyse separately the sub-queries over the static relations and over the dynamic relations, respectively. Instead, we need to take the interaction between the static and the dynamic relations into account. Even when the sub-query over the dynamic relations is not tractable, the overall query can become tractable if the dynamic relations are sufficiently constrained by the static ones.
Cite as

Ahmet Kara, Zheng Luo, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. Tractable Conjunctive Queries over Static and Dynamic Relations. In 28th International Conference on Database Theory (ICDT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 328, pp. 12:1-12:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kara_et_al:LIPIcs.ICDT.2025.12,
  author =	{Kara, Ahmet and Luo, Zheng and Nikolic, Milos and Olteanu, Dan and Zhang, Haozhe},
  title =	{{Tractable Conjunctive Queries over Static and Dynamic Relations}},
  booktitle =	{28th International Conference on Database Theory (ICDT 2025)},
  pages =	{12:1--12:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-364-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{328},
  editor =	{Roy, Sudeepa and Kara, Ahmet},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.12},
  URN =		{urn:nbn:de:0030-drops-229534},
  doi =		{10.4230/LIPIcs.ICDT.2025.12},
  annote =	{Keywords: fully dynamic algorithm, constant enumeration delay, constant update time}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2025.26
Dynamic Direct Access of MSO Query Evaluation over Strings

Authors: Pierre Bourhis, Florent Capelli, Stefan Mengel, and Cristian Riveros

Published in: LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025)

Abstract
We study the problem of evaluating a Monadic Second Order (MSO) query over strings under updates in the setting of direct access. We present an algorithm that, given an MSO query with first-order free variables represented by an unambiguous variable-set automaton 𝒜 with state set Q and variables X and a string s, computes a data structure in time 𝒪(|Q|^ω⋅ |X|² ⋅ |s|) and, then, given an index i retrieves, using the data structure, the i-th output of the evaluation of 𝒜 over s in time 𝒪(|Q|^ω ⋅ |X|³ ⋅ log(|s|)²) where ω is the exponent for matrix multiplication. Ours is the first efficient direct access algorithm for MSO query evaluation over strings; such algorithms so far had only been studied for first-order queries and conjunctive queries over relational data. Our algorithm gives the answers in lexicographic order where, in contrast to the setting of conjunctive queries, the order between variables can be freely chosen by the user without degrading the runtime. Moreover, our data structure can be updated efficiently after changes to the input string, allowing more powerful updates than in the enumeration literature, e.g. efficient deletion of substrings, concatenation and splitting of strings, and cut-and-paste operations. Our approach combines a matrix representation of MSO queries and a novel data structure for dynamic word problems over semi-groups which yields an overall algorithm that is elegant and easy to formulate.
Cite as

Pierre Bourhis, Florent Capelli, Stefan Mengel, and Cristian Riveros. Dynamic Direct Access of MSO Query Evaluation over Strings. In 28th International Conference on Database Theory (ICDT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 328, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bourhis_et_al:LIPIcs.ICDT.2025.26,
  author =	{Bourhis, Pierre and Capelli, Florent and Mengel, Stefan and Riveros, Cristian},
  title =	{{Dynamic Direct Access of MSO Query Evaluation over Strings}},
  booktitle =	{28th International Conference on Database Theory (ICDT 2025)},
  pages =	{26:1--26:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-364-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{328},
  editor =	{Roy, Sudeepa and Kara, Ahmet},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.26},
  URN =		{urn:nbn:de:0030-drops-229675},
  doi =		{10.4230/LIPIcs.ICDT.2025.26},
  annote =	{Keywords: Query evaluation, direct access, MSO queries}
}
Document
DOI: 10.4230/LIPIcs.STACS.2015.143
Understanding Model Counting for beta-acyclic CNF-formulas

Authors: Johann Brault-Baron, Florent Capelli, and Stefan Mengel

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
We show that SAT on beta-acyclic CNF-formulas can be solved in polynomial time. In contrast to previous algorithms for other structurally restricted classes of formulas, our algorithm does not proceed by dynamic programming. Instead, it works along an elimination order, solving a weighted version of constraint satisfaction. We give evidence that this deviation from more standard algorithms is no coincidence by showing that it is outside of the framework recently proposed by Saether et al. (SAT 2014) which subsumes all other structural tractability results for #SAT known so far.
Cite as

Johann Brault-Baron, Florent Capelli, and Stefan Mengel. Understanding Model Counting for beta-acyclic CNF-formulas. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 143-156, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{braultbaron_et_al:LIPIcs.STACS.2015.143,
  author =	{Brault-Baron, Johann and Capelli, Florent and Mengel, Stefan},
  title =	{{Understanding Model Counting for beta-acyclic CNF-formulas}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{143--156},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.143},
  URN =		{urn:nbn:de:0030-drops-49106},
  doi =		{10.4230/LIPIcs.STACS.2015.143},
  annote =	{Keywords: model counting, hypergraph acyclicity, structural tractability}
}
Document
DOI: 10.4230/LIPIcs.CSL.2012.137
A Negative Conjunctive Query is Easy if and only if it is Beta-Acyclic

Authors: Johann Brault-Baron

Published in: LIPIcs, Volume 16, Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL (2012)

Abstract
It is known that the data complexity of a Conjunctive Query (CQ) is determined *only* by the way its variables are shared between atoms, reflected by its hypergraph. In particular, Yannakakis [Yannakakis VLDB'81,Beeri/Fagin/Maier/Yannakakis JACM'83] proved that a CQ is decidable in linear time when it is alpha-acyclic, i.e. its hypergraph is alpha-acyclic; Bagan et al. [Bagan/Durand/Grandjean CSL'07] even state: * Any CQ is decidable in linear time iff it is alpha-acyclic. (under certain hypotheses) (By linear time, we mean a query on a structure S can be decided in time O(|S|)) A natural question is: since the complexity of a *Negative* Conjunctive Query (NCQ), a conjunctive query where *all* atoms are negated, also only depends on its hypergraph, can we find a similar dichotomy in this case? To answer this question, we revisit a result of Ordyniak et al. --- that states that satisfiability of a beta-acyclic CNF formula is decidable in polynomial time --- by proving that some part of their procedure can be done in linear time. This implies, under an algorithmic hypothesis that is likely true: (precisely: one cannot decide whether a graph is triangle-free in time O(n²log n) where n is the number of vertices.) * Any NCQ is decidable in quasi-linear time iff it is beta-acyclic. (By quasi-linear time, we mean a query on a structure S can be decided in time O(|S|log|S|)) We extend the easiness result to 'Signed' Conjunctive Query (SCQ) where 'some' atoms are negated. This has great interest since using some negated atoms is natural in the frameworks of databases and CSP. Furthermore, it implies straightforwardly the following: * Any beta-acyclic existential first-order query is decidable in quasi-linear time.
Cite as

Johann Brault-Baron. A Negative Conjunctive Query is Easy if and only if it is Beta-Acyclic. In Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 16, pp. 137-151, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{braultbaron:LIPIcs.CSL.2012.137,
  author =	{Brault-Baron, Johann},
  title =	{{A Negative Conjunctive Query is Easy if and only if it is Beta-Acyclic}},
  booktitle =	{Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL},
  pages =	{137--151},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-42-2},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{16},
  editor =	{C\'{e}gielski, Patrick and Durand, Arnaud},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2012.137},
  URN =		{urn:nbn:de:0030-drops-36697},
  doi =		{10.4230/LIPIcs.CSL.2012.137},
  annote =	{Keywords: conjunctive query, hypergraph, beta-acyclicity, data complexity, Davis-Putnam procedure}
}
  • Refine by Type
  • 9 Document/PDF
  • 7 Document/HTML

  • Refine by Publication Year
  • 4 2026
  • 3 2025
  • 1 2015
  • 1 2012

  • Refine by Author
  • 2 Brault-Baron, Johann
  • 2 Capelli, Florent
  • 2 Kara, Ahmet
  • 2 Mengel, Stefan
  • 2 Olteanu, Dan
  • Show More...

  • Refine by Series/Journal
  • 9 LIPIcs

  • Refine by Classification
  • 3 Theory of computation → Database query processing and optimization (theory)
  • 3 Theory of computation → Graph algorithms analysis
  • 2 Mathematics of computing → Graph theory
  • 2 Theory of computation → Database theory
  • 1 Information systems → Data streams
  • Show More...

  • Refine by Keyword
  • 2 direct access
  • 1 Davis-Putnam procedure
  • 1 MSO queries
  • 1 Query evaluation
  • 1 alpha-acyclicity
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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