Guaranteed polynomial time answering of database queries that include negation.

What is it about?

We identify new structural properties of conjunctive database queries with negation that allow for guaranteed polynomial time query answering. We give algorithms for the efficient evaluation, assuming the the property is satisfied, and for identifying whether a query has the property itself. In addition, our results are also extended to the propositional satisfiability problem where even stronger upper bound guarantees can be given.

Featured Image

Photo by Jan Antonin Kolar on Unsplash

Photo by Jan Antonin Kolar on Unsplash

Why is it important?

Database systems operate on heuristics that hope to perform well on common workloads. With the immense increase of data in all industries, and more and more complex data analysis, these heuristics are reaching their limits and users are exposed to the worst-case exponential time (the problem is NP-hard) required to solve queries. Theoretical advances in polynomial time query answering are therefore critical for the future of databases and data science. While the case of queries without negation is extensively studied and well understood, this work considers the problem with negation. While negation is a very natural and intuitive concept in database queries, it also vastly complicates the problem and requires completely new methods for efficient query solving. This work is the first to introduce methods and algorithms for solving large classes of complex queries with negation in guaranteed polynomial time.

Perspectives