Complexity limits for queries with negation on semiring databases

Containment of Conjunctive Queries with Negative Information over Semirings

Logic in Computer ScienceDatabases

Summary

This paper looks at how hard it is to check if one database question (query) that includes negative information can fit inside another, when the data has special labels called semirings. The researchers study two ways negativity shows up in queries, and find that the difficulty depends on what kinds of labels the data uses. They also show that some queries are surprisingly no harder than normal queries, while others get more complex. Their findings help understand the limits of working with negative information in complex database settings.

What this means in practice

  • For database system designers: Avoid costly query processing by understanding when containment with negation remains tractable on semiring-annotated data.
  • For data provenance engineers: Optimize tracking of data origins by leveraging cases where negation in queries does not increase containment complexity.

A theory result. No direct application yet.

Authors

Guillermo Badia, Carles Noguera, Gaia Petreni, Alice Portone, Val Tannen

Abstract

We study the containment problem for (unions of) conjunctive queries ((U)CQs) with negative information on semiring-annotated databases. Our approach to negative information follows the treatment of negation proposed by Grädel and Tannen (2017, 2019, 2021 and 2024) for first-order logic and fixed point logic which applies productively to large classes of semirings, including bounded distributive lattices, as well as the important provenance semirings studied for positive CQ containment by Green (2009). Negation features in (U)CQs along two dimensions: negated equalities (disequations), and negated relational atoms. We study complexity for each of them separately, as well as jointly. For disequations, we extend a methodology that proves the same complexity bounds as the ones already known for the standard Boolean semiring (in the second level of the polynomial hierarchy) for most semirings of interest. Two prominent exceptions are $\mathbb{N}[X]$ and Trio(X) where the complexity bound for containment is in the second level of the counting hierarchy. For CQs with negated relational atoms we show that the complexity, surprisingly, is the same as that of the containment of CQs without negation when one considers model-defining and provenance-tracking interpretations (namely, nondeterministic polynomial time). Interestingly, among bounded distributive lattices, the Boolean two-element case is the only one where the complexity of the problem continues to be hard for the second level of the polynomial hierarchy for model-defining interpretations. Furthermore, we show that the complexity increases again for distributive lattices if we focus on other classes of interpretations. Finally, we consider queries that have both negated equalities and negated relational atoms and show that the complexity of containment continues to be that of the case with just negated equalities.