Database interrogation using conjunctive queries

Abstract

We consider a scenario where a client communicates with a database server by posing boolean conjunctive queries, or more generally, counts of conjunctive queries. We investigate to what extent features such as quantification, negation, or non-equalities axe important in such a setting. We also investigate the difference between a setting where the client can pose an adaptive sequence of queries, and a setting where the client must pose a fixed combination of queries.