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 $\Delta$ of subsets of facts of the database of size at most k, where k is the size of the query q. The algorithm runs in polynomial time and can be formally defined as: (1) Initialize $\Delta$ with all sets $S$ of at most $k$ facts such that $S\models q$. (2) Add any set $S$ of at most k facts to $\Delta$ if there exists a block $B$ (i.e., a maximal set of facts sharing the same key) such that for every fact $a \in B$ there is a set $S' \subseteq S \cup \{a\}$ such that $S'\in \Delta$. For an input database $D$, the algorithm answers "q is certain" iff $\Delta$ 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.

The problem of whether a recursive query can be rewritten as query without recursion is a fundamental reasoning task, known as the boundedness problem. Here we study the boundedness problem for Unions of Conjunctive Regular Path Queries (UCRPQs), a navigational query language extensively used in ontology and graph database querying. The boundedness problem for UCRPQs is known to be decidable, ExpSpace-complete. Here we focus our analysis on UCRPQs using simple regular expressions, which are of high practical relevance and enjoy a lower reasoning complexity. We show that the complexity for the boundedness problem for this UCRPQs fragment is Pi-p-2-complete, and that an equivalent bounded query can be produced in polynomial time whenever possible. When the query turns out to be unbounded, we also study the task of finding an equivalent maximally bounded query, which we show to be feasible in Pi-p-2 . As a side result of independent interest stemming from our developments, we study a notion of succinct finite automata and prove that its membership problem is NP-complete.

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 PTime or CoNP-complete. This conjecture has been verified for self-join-free and path queries. We show that it also holds for queries with two atoms.

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 facts of the database of size at most k, 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\models 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 \in B$ there is a set $S' \subseteq S \cup \{a\}$ such that $S'\in Δ$. For an input database $D$, 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.

First order modal logic (𝖥𝖮𝖬𝖫) is built by extending First Order Logic (𝖥𝖮) with modal operators. A typical formula is of the form \(\forall x \exists y \Box P(x,y)\) . Not only is 𝖥𝖮𝖬𝖫 undecidable, even simple fragments like that of restriction to unary predicate symbols, guarded fragment and two variable fragment, which are all decidable for 𝖥𝖮 become undecidable for 𝖥𝖮𝖬𝖫. In this paper we study Term Modal logic (𝖳𝖬𝖫) which allows modal operators to be indexed by terms. A typical formula is of the form \(\forall x \exists y~\Box _x P(x,y)\) . There is a close correspondence between 𝖳𝖬𝖫 and 𝖥𝖮𝖬𝖫 and we explore this relationship in detail in the paper. In contrast to 𝖥𝖮𝖬𝖫, we show that the two variable fragment (without constants, equality) of 𝖳𝖬𝖫 is decidable. Further, we prove that adding a single constant makes the two variable fragment of 𝖳𝖬𝖫 undecidable. On the other hand, when equality is added to the logic, it loses the finite model property.

Bundled products are often offered as good deals to customers. When we bundle quantifiers and modalities together (as in $\exists x \Box$, $\Diamond \forall x$ etc.) in first-order modal logic (FOML), we get new logical operators whose combinations produce interesting fragments of FOML without any restriction on the arity of predicates, the number of variables, or the modal scope. It is well-known that finding decidable fragments of FOML is hard, so we may ask: do bundled fragments that exploit the distinct expressivity of FOML constitute good deals in balancing the expressivity and complexity? There are a few positive earlier results on some particular fragments. In this paper, we try to fully map the terrain of bundled fragments of FOML in (un)decidability, and in the cases without a definite answer yet, we show that they lack the finite model property. Moreover, whether the logics are interpreted over constant domains (across states/worlds) or increasing domains presents another layer of complexity. We also present the \textit{loosely bundled fragment}, which generalizes the bundles and yet retain decidability (over increasing domain models).

Term modal logics (TML) are modal logics with unboundedly many modalities, with quantification over modal indices, so that we can have formulas of the form $\exists y. \forall x. (\Box_x P(x,y) \supset\Diamond_y P(y,x))$. Like First order modal logic, TML is also "notoriously" undecidable, in the sense that even very simple fragments are undecidable. In this paper, we show the decidability of one interesting fragment, that of two variable TML. This is in contrast to two-variable First order modal logic, which is undecidable.

Quantified modal logic is notorious for being undecidable, with very few known decidable fragments such as the monodic ones. For instance, even the two-variable fragment over unary predicates is undecidable. In this paper, we study a particular fragment, namely the bundled fragment, where a first-order quantifier is always followed by a modality when occurring in the formula, inspired by the proposal of [Yanjing Wang, 2017] in the context of non-standard epistemic logics of know-what, know-how, know-why, and so on. As always with quantified modal logics, it makes a significant difference whether the domain stays the same across possible worlds. In particular, we show that the predicate logic with the bundle "forall Box" alone is undecidable over constant domain interpretations, even with only monadic predicates, whereas having the "exists Box" bundle instead gives us a decidable logic. On the other hand, over increasing domain interpretations, we get decidability with both "forall Box" and "exists Box" bundles with unrestricted predicates, where we obtain tableau based procedures that run in PSPACE. We further show that the "exists Box" bundle cannot distinguish between constant domain and variable domain interpretations.