Can I read Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems on EtoBox?

Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems by Koutris, Paraschos (author);Ouyang, Xiating (author);Wijsen, Jef (author) is a nonfiction available to read on EtoBox.

What is Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems about?

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. ## CCS CONCEPTS • Information systems → Relational database query languages; • Theory of computation → Incomplete, inconsistent, and uncertain databases; Logic and databases.

Who reads Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems?

Author

Koutris, Paraschos (author);Ouyang, Xiating (author);Wijsen, Jef (author)

Publisher

ACM

Published

2021

Language

EN

Category

nonfiction