This is another problem from the same paper as last week’s. The paper this time though, doesn’t really give a reduction. Hopefully, I think it’s easy enough for us to build it ourselves.

**The problem: **Conjunctive Boolean Query. This is problem SR31 in the appendix.

**The description: **Given a conjunctive query in the format described last week, is the query true? (That is, can we find any tuples to satisfy the query?)

**Examples: **Here is the “List all departments that sell pens and pencils” query from last week:

(x). Sales(x, pen) and Sales(x, pencil).

This problem would return true if there was an actual tuple in the database that could bind to x, and false otherwise.

**Reduction: **The paper by Chandra and Merlin that we used last week has the definition of this problem, but just says the NP-Completeness “follows from, say, the completeness of the clique problem for graphs”

But I think the reduction is pretty easy to spell out. If we’re given an instance of Clique (a graph G and an integer K), we can just build the query:

“Does there exist k vertices x_{1} through x_{k} such that all edges between any two vertices in the set exist?”

We can implement this as a database by creating a relation for all edges, and then the conjunctive query will have at most O(V^{2}) clauses.

**Dififculty:** 3, but it’s a lot of work to understand the database definitions to get to the actual problem.