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 x1 through xk 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(V2) clauses.
Dififculty: 3, but it’s a lot of work to understand the database definitions to get to the actual problem.