Sen Zheng, Renate A. Schmidt · arXiv (Cornell University) · 2022
Query answering is an important problem in AI, database and knowledge representation. In this paper, we develop saturation-based Boolean conjunctive query answering and rewriting procedures for the guarded, the loosely guarded and the clique-guarded fragments. Our query answering procedure improves existing resolution-based decision procedures for the guarded and the loosely guarded fragments and this procedure solves Boolean conjunctive query answering problems for the guarded, the loosely guarded and the clique-guarded fragments. Based on this query answering procedure, we also introduce a novel saturation-based query rewriting procedure for these guarded fragments. Unlike mainstream query answering and rewriting methods, our procedures derive a compact and reusable saturation, namely a closure of formulas, to handle the challenge of querying for distributed datasets. This paper lays the theoretical foundations for the first automated deduction decision procedures for Boolean conjunctive query answering and the first saturation-based Boolean conjunctive query rewriting in the guarded, the loosely guarded and the clique-guarded fragments.
Cited by 0Open access
Sen Zheng, Renate A. Schmidt · Journal of Automated Reasoning · 2023
Abstract Query answering is an important problem in AI, database and knowledge representation. In this paper, we develop saturation-based Boolean conjunctive query answering and rewriting procedures for the guarded, the loosely guarded and the clique-guarded fragments. Our query answering procedure improves existing resolution-based decision procedures for the guarded and the loosely guarded fragments and this procedure solves Boolean conjunctive query answering problems for the guarded, the loosely guarded and the clique-guarded fragments. Based on this query answering procedure, we also introduce a novel saturation-based query rewriting procedure for these guarded fragments. Unlike mainstream query answering and rewriting methods, our procedures derive a compact and reusable saturation, namely a closure of formulas, to handle the challenge of querying for distributed datasets. This paper lays the theoretical foundations for the first automated deduction decision procedures for Boolean conjunctive query answering and the first saturation-based Boolean conjunctive query rewriting in the guarded, the loosely guarded and the clique-guarded fragments.
Cited by 0Open access
Georg Gottlob, Nicola Leone, Francesco Scarcello · Journal of the ACM · 2001
This paper deals with the evaluation of acyclic Boolean conjunctive queries in relational databases. By well-known results of Yannakakis[1981], this problem is solvable in polynomial time; its precise complexity, however, has not been pinpointed so far. We show that the problem of evaluating acyclic Boolean conjunctive queries is complete for LOGCFL, the class of decision problems that are logspace-reducible to a context-free language. Since LOGCFL is contained in AC1 and NC2, the evaluation problem of acyclic Boolean conjunctive queries is highly parallelizable. We present a parallel database algorithm solving this problem with alogarithmic number of parallel join operations. The algorithm is generalized to computing the output of relevant classes of non-Boolean queries. We also show that the acyclic versions of the following well-known database and AI problems are all LOGCFL-complete: The Query Output Tuple problem for conjunctive queries, Conjunctive Query Containment, Clause Subsumption, and Constraint Satisfaction. The LOGCFL-completeness result is extended to the class of queries of bounded tree width and to other relevant query classes which are more general than the acyclic queries.
Cited by 194
Dimitri Surinx, Jan Van den Bussche · arXiv (Cornell University) · 2018
When a relational database is queried, the result is normally a relation.\nSome queries, however, only require a yes/no answer; such queries are often\ncalled boolean queries. It is customary in database theory to express boolean\nqueries by testing nonemptiness of query expressions. Another interesting way\nfor expressing boolean queries are containment statements of the form $Q_1\n\\subseteq Q_2$ where $Q_1$ and $Q_2$ are query expressions. Here, for any input\ninstance $I$, the boolean query result is $\\mathit{true}$ if $Q_1(I)$ is a\nsubset of $Q_2(I)$ and $\\mathit{false}$ otherwise.\n In the present paper we will focus on nonemptiness and containment statements\nabout conjunctive queries. The main goal is to investigate the monotone\nfragment of the containments of conjunctive queries. In particular, we show a\npreservation like result for this monotone fragment. That is, we show that, in\nexpressive power, the monotone containments of conjunctive queries are exactly\nequal to conjunctive queries under nonemptiness.\n
Cited by 0Open access
Глазырин Павел Александрович, Glazyrin Pavel · Research Repository Saint Petersburg State University (Saint Petersburg State University) · 2018
"Конъюнктивный булевский запрос" - NP-полная задача, связанная с базами данных. Поскольку для баз данных время выполнения запроса - одна из важнейших характеристик, то эффективные методы решения задач являются довольно востребованными. Предлагаемый в данной работе алгоритм позволяет построить на основе содержимого базы данных структуру, уменьшающую требуемое число шагов для решения задачи.
Cited by 0Open access
Sen Zheng, Renate A. Schmidt · Research Explorer (The University of Manchester)
We consider the following query answering problem: Given a Boolean conjunctive query and a theory in the Horn loosely guarded fragment, the aim is to determine whether the query is entailed by the theory. In this paper, we present a resolution decision procedure for the loosely guarded fragment, and use such a procedure to answer Boolean conjunctive queries against the Horn loosely guarded fragment. The Horn loosely guarded fragment subsumes classes of rules that are prevalent in ontology-based query answering, such as Horn ALCHOI and guarded existential rules. Additionally, we identify star queries and cloud queries, which using our procedure, can be answered against the loosely guarded fragment.
Cited by 0
Paraschos Koutris, Jef Wijsen · 2015
A relational database is said to be uncertain if primary key constraints can possibly be violated. A repair (or possible world) of an uncertain database is obtained by selecting a maximal number of tuples without ever selecting two distinct tuples with the same primary key value. For any Boolean query q, CERTAINTY(q) is the problem that takes an uncertain database db as input, and asks whether q is true in every repair of db. The complexity of this problem has been particularly studied for q ranging over the class of self-join-free Boolean conjunctive queries. A research challenge is to determine, given q, whether CERTAINTY(q) belongs to complexity classes FO, P, or coNP-complete. In this paper, we combine existing techniques for studying the above complexity classification task. We show that for any self-join-free Boolean conjunctive query q, it can be decided whether or not CERTAINTY(q) is in FO. Further, for any self-join-free Boolean conjunctive query q, CERTAINTY(q) is either in P or coNP-complete, and the complexity dichotomy is effective. This settles a research question that has been open for ten years.
Cited by 40
Antoine Amarilli, Florent Capelli · ACM SIGMOD Record · 2024
This work reviews how database theory uses tractable circuit classes from knowledge compilation. We present relevant query evaluation tasks, and notions of tractable circuits. We then show how these tractable circuits can be used to address database tasks. We first focus on Boolean provenance and its applications for aggregation tasks, in particular probabilistic query evaluation. We study these for Monadic Second Order (MSO) queries on trees, and for safe Conjunctive Queries (CQs) and Union of Conjunctive Queries (UCQs). We also study circuit representations of query answers, and their applications to enumeration tasks: both in the Boolean setting (for MSO) and the multivalued setting (for CQs and UCQs).
Cited by 3
Paraschos Koutris, Xiating Ouyang, Jef Wijsen · Proceedings of the ACM on Management of Data · 2024
We study the data complexity of consistent query answering (CQA) on databases that may violate the primary key constraints. A repair is a maximal subset of the database satisfying the primary key constraints. For a Boolean query q, the problem fCERTAINTY(q) takes a database as input, and asks whether or not each repair satisfies q. The computational complexity of fCERTAINTY(q) has been established whenever q is a self-join-free Boolean conjunctive query, or a (not necessarily self-join-free) Boolean path query. In this paper, we take one more step towards a general classification for all Boolean conjunctive queries by considering the class of rooted tree queries. In particular, we show that for every rooted tree query q, fCERTAINTY(q) is in FO, NL-hard ∩ LPFL, or coNP-complete, and it is decidable (in polynomial time), given q, which of the three cases applies. We also extend our classification to larger classes of queries with simple primary keys. Our classification criteria rely on query homomorphisms and our polynomial-time fixpoint algorithm is based on a novel use of context-free grammar (CFG).
Cited by 3Open access
Paraschos Koutris, Xiating Ouyang, Jef Wijsen · arXiv (Cornell University) · 2023
We study the data complexity of consistent query answering (CQA) on databases that may violate the primary key constraints. A repair is a maximal subset of the database satisfying the primary key constraints. For a Boolean query q, the problem CERTAINTY(q) takes a database as input, and asks whether or not each repair satisfies q. The computational complexity of CERTAINTY(q) has been established whenever q is a self-join-free Boolean conjunctive query, or a (not necessarily self-join-free) Boolean path query. In this paper, we take one more step towards a general classification for all Boolean conjunctive queries by considering the class of rooted tree queries. In particular, we show that for every rooted tree query q, CERTAINTY(q) is in FO, NL-hard $\cap$ LFP, or coNP-complete, and it is decidable (in polynomial time), given q, which of the three cases applies. We also extend our classification to larger classes of queries with simple primary keys. Our classification criteria rely on query homomorphisms and our polynomial-time fixpoint algorithm is based on a novel use of context-free grammar (CFG).
Cited by 1Open access
Michaël Thomazo · HAL (Le Centre pour la Communication Scientifique Directe) · 2023
Answering queries while taking an ontology into account has been studied over the last fifteen years to ease data integration. The goal is to allow users to express their queries in a vocabulary they are familiar with, while facilitating data integration and providing more complete sets of answers thanks to the exploitation of the semantics of the query terms. Decidability, complexity and algorithms developed so far have focused on the casewhere Boolean conjunctive queries are used to query a so-called knowledge base.In this manuscript, we explore the limitations of this setting, and suggest a few extensions that are relevant from an applicative point of view. Expressivity is studied through the prism of descriptive complexity, while the proposed extensions escape from the Boolean conjunctive query framework, by either allowing path queries, or by going beyond the Boolean case, by supporting counting features or providing meta-data about theprovenance of an answer.
Cited by 0Open access
Georg Gottlob, Nicola Leone, Francesco Scarcello · 2002
We show that the problem of evaluating acylic Boolean database-queries is LOGCFL-complete and thus highly parallelizable. We present a parallel database algorithm solving this problem with a logarithmic number of parallel join operations. It follows from our main result that the acylic versions of the following important database and Al problems are LOGCFL-complete: The query output tuple problem for conjunctive queries, conjunctive query containment, clause subsumption, and constraint satisfaction.
Cited by 29
Dan Olteanu, Jiewen Huang · 2008
Abstract. We consider the problem of query evaluation for tuple independent probabilistic databases and Boolean conjunctive queries with inequalities but without self-joins. We approach this problem as a construction problem for ordered binary decision diagrams (OBDDs): Given a query q and a probabilistic database D, we construct in polynomial time an OBDD such that the probability of q(D) can be computed linearly in the size of that OBDD. This approach is applicable to a large class of queries, including the hierarchical queries, i.e., the Boolean conjunctive queries without self-joins that admit PTIME evaluation on any tuple-independent probabilistic database, hierarchical queries extended with inequalities, and non-hierarchical queries on restricted databases. 1
Cited by 0
Lanxiang Chen, Yi Mu, Jihoon Yang et al. · IEEE Transactions on Information Forensics and Security · 2025
Cash et al. [CRYPTO2013] proposed the oblivious cross-tags (OXT) protocol to enable highly scalable searchable symmetric encryption (SSE) with support for Boolean queries. More recently, Lai et al. [CCS2018] introduced the hidden cross-tags (HXT) protocol, an enhancement of OXT designed to eliminate “keyword-pair result pattern” (KPRP) leakage in conjunctive queries. However, while HXT prevents KPRP leakage in conjunctive queries, it suffers from low efficiency and remains vulnerable to KPRP leakage in disjunctive queries. In this paper, we propose the first efficient structured encryption scheme for Boolean queries (STE-BQ) that eliminates KPRP leakage for both disjunctive and conjunctive multi-keyword queries. Our approach introduces a novel index construction method based on prime number aggregation, which significantly reduces the number of comparisons required in multi-keyword searches, thereby improving efficiency. Security analysis confirms that STE-BQ satisfies CQA2-security. Experimental evaluations further demonstrate that STE-BQ achieves optimal performance in conjunctive query processing. While its disjunctive query time is slightly slower than that of OXT, STE-BQ is the only scheme that fully eliminates KPRP leakage for both conjunctive and disjunctive queries.
Cited by 0
Paraschos Koutris, Jef Wijsen · 2020
We study consistent query answering with respect to key dependencies. Given a (possibly inconsistent) database instance and a set of key dependencies, a repair is an inclusion-maximal subinstance that satisfies all key dependencies. Consistent query answering for a Boolean query is the following problem: given a database instance as input, is the query true in every repair? In [Koutris and Wijsen, ICDT 2019], it was shown that for every self-join-free Boolean conjunctive query and set of key dependencies containing exactly one key dependency per relation name (also called the primary key), this problem is in FO, L-complete, or coNP-complete, and it is decidable which of the three cases applies. In this paper, we consider the more general case where a relation name can be associated with more than one key dependency. It is shown that in this more general setting, it remains decidable whether or not the above problem is in FO, for self-join-free Boolean conjunctive queries. Moreover, it is possible to effectively construct a first-order query that solves the problem whenever such a query exists.
Cited by 9
Paraschos Koutris, Jef Wijsen · arXiv (Cornell University) · 2015
A relational database is said to be uncertain if primary key constraints can\npossibly be violated. A repair (or possible world) of an uncertain database is\nobtained by selecting a maximal number of tuples without ever selecting two\ndistinct tuples with the same primary key value. For any Boolean query q,\nCERTAINTY(q) is the problem that takes an uncertain database db on input, and\nasks whether q is true in every repair of db. The complexity of this problem\nhas been particularly studied for q ranging over the class of self-join-free\nBoolean conjunctive queries. A research challenge is to determine, given q,\nwhether CERTAINTY(q) belongs to complexity classes FO, P, or coNP-complete. In\nthis paper, we combine existing techniques for studying the above complexity\nclassification task. We show that for any self-join-free Boolean conjunctive\nquery q, it can be decided whether or not CERTAINTY(q) is in FO. Further, for\nany self-join-free Boolean conjunctive query q, CERTAINTY(q) is either in P or\ncoNP-complete, and the complexity dichotomy is effective. This settles a\nresearch question that has been open for ten years, since [9].\n
Cited by 0Open access
Abo Khamis, Mahmoud, Chichirim, George, Kormpa, Antonia et al. · Zurich Open Repository and Archive (University of Zurich) · 2022
Intersection joins over interval data are relevant in spatial and temporal data settings. A set of intervals join if their intersection is non-empty. In case of point intervals, the intersection join becomes the standard equality join. We establish the complexity of Boolean conjunctive queries with intersection joins by a many-one equivalence to disjunctions of Boolean conjunctive queries with equality joins. The complexity of any query with intersection joins is that of the hardest query with equality joins in the disjunction exhibited by our equivalence. This is captured by a new width measure called the IJ-width. We also introduce a new syntactic notion of acyclicity called iota-acyclicity to characterise the class of Boolean queries with intersection joins that admit linear time computation modulo a poly-logarithmic factor in the data size. Iota-acyclicity is for intersection joins what alpha-acyclicity is for equality joins. It strictly sits between gamma-acyclicity and Berge-acyclicity. The intersection join queries that are not iota-acyclic are at least as hard as the Boolean triangle query with equality joins, which is widely considered not computable in linear time.
Cited by 0Open access
Paraschos Koutris, Xiating Ouyang, Jef Wijsen · 2021
We study the data complexity of consistent query answering (CQA) on databases that may violate the primary key constraints. A repair is a maximal consistent subset of the database. For a Boolean query q, the problem CERTAINTY(q) takes a database as input, and asks whether or not each repair satisfies the query q. It is known that for any self-join-free Boolean conjunctive query q, CERTAINTY(q) is in FO, L-complete, or coNP-complete. In particular, CERTAINTY(q) is in FO for any self-join-free Boolean path query q. In this paper, we show that if self-joins are allowed, then the complexity of CERTAINTY(q) for Boolean path queries q exhibits a tetrachotomy between FO, NL-complete, PTIME-complete, and coNP-complete. Moreover, it is decidable, in polynomial time in the size of the query q, which of the four cases applies.
Cited by 8
Hubie Chen, Moritz Müller · 2013
We perform a fundamental investigation of the complexity of conjunctive query evaluation from the perspective of parameterized complexity. We classify sets of boolean conjunctive queries according to the complexity of this problem. Previous work showed that a set of conjunctive queries is fixed-parameter tractable precisely when the set is equivalent to a set of queries having bounded treewidth. We present a fine classification of query sets up to parameterized logarithmic space reduction. We show that, in the bounded treewidth regime, there are three complexity degrees and that the properties that determine the degree of a query set are bounded pathwidth and bounded tree depth. We also engage in a study of the two higher degrees via logarithmic space machine characterizations and complete problems. Our work yields a significantly richer perspective on the complexity of conjunctive queries and, at the same time, suggests new avenues of research in parameterized complexity.
Cited by 6
Paraschos Koutris, Jef Wijsen · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2018
We study the complexity of consistent query answering on databases that may violate primary key constraints. A repair of such a database is any consistent database that can be obtained by deleting a minimal set of tuples. For every Boolean query q, CERTAINTY(q) is the problem that takes a database as input and asks whether q evaluates to true on every repair. In [KW17], the authors show that for every self-join-free Boolean conjunctive query q, the problem CERTAINTY(q) is either in P or coNP-complete, and it is decidable which of the two cases applies. In this paper, we sharpen this result by showing that for every self-join-free Boolean conjunctive query q, the problem CERTAINTY(q) is either expressible in symmetric stratified Datalog or coNP-complete. Since symmetric stratified Datalog is in L, we thus obtain a complexity-theoretic dichotomy between L and coNP-complete. Another new finding of practical importance is that CERTAINTY(q) is on the logspace side of the dichotomy for queries q where all join conditions express foreign-to-primary key matches, which is undoubtedly the most common type of join condition.
Cited by 4Open access