Tag Archives: Graph K-Coloring

Conjunctive Query Foldability

Back on track with more database problems.  This is another one of those “really hard to explain in NP-Complete language” problems.

The problem: Conjunctive Query Foldability.  This is problem SR30 in the appendix.

The description: I find G&J’s definition very confusing, I think because they don’t have room to define what the various variables mean in terms of databases (they actually send you to the paper, as if they know it was confusing).  The definitions in the paper by Chandra and Merlin that has the reduction do a good job of giving names to things and building up slowly.  So:

They define a Relational Data Base as a finite domain D, and a set of relations R1 through Rs.  Each relation is an ordered tuple of elements of D.

A first-order query is of the form (x1, x2, …xk). Φ(x1, x2, ..xk) where Φ is a first-order formula whose only free variables are x1 through xk

The result of a query on a database B with domain D is a set of k-tuples {(y1..yk) ∈ Dk such that Φ(y1..yk) is true in B}.

A conjunctive query is a first-order query of the form (x1, ..xk).∃ xk+1,xk+2, …xm. A1∧A2..Ar, where each Ai is an atomic formula asking about a relation in a database, and each element in the relation is a variable form x1 to xm or a constant.

Examples of conjunctive queries: Here are some examples from the paper, so we can see how this relates to databases:

“List all departments that sell pens and pencils”.  If we have a relation Sales(Department, Item)  (“Department” and “Item” are placeholders for variables), the conjunctive query is:

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

In this case, there are no new variables (or ∃) added in the query, and “pen” and “pencil” are constants.

“List all second-level or higher managers in department K10” (People who are in X10 who manage someone who manages someone else).  If we have a relation Emp(Name, Salary, Manager, Dept), the conjunctive query is:

(x1).∃(x2, …, x9) .Emp(x2, x3, x4, x5) ∧Emp(x4, x6, x1, x7) ∧ Emp(x1, x8, x9, K10)

In this query, x1 is the “answer”, but depends on the existence of the other x variables.  In particular, x4, who is the employee x1 manages, and x2, who is the employee x4 manages.

Ok, now the actual foldability definition (this is written less formally than either the paper or G&J):

Given two conjunctive queries Q1 and Q2, can we create a function σ mapping all constants and variables x1 through xk to themselves (and possibly mapping other variables to constants or variables from x1 to xk as well), where if we replace each variable x  in Q1 with σ(Q1), we get Q2?

Example: Here is a “worse” version of the first example above:

(x).Sales(x, xpen) ∧ Sales(x,xpencil) ∧ xpen=pen ∧ xpencil = pencil

This can be “folded” into:

(x).Sales(x, pen) ∧ Sales(x,pencil) ∧ pen=pen ∧ pencil = pencil

..it still has those redundant equalities at the end, though, but I don’t see a way to use the definitions of foldability to get rid of them.  I think that the definition given in Chandra and Merlin’s paper might let you do it because their function maps the “natural model” of a query, which I think includes relations.

Reduction: From Graph Coloring.  We start with a graph and an integer K.  We build one variable for each vertex, and K additional (separate) vertices, in a set called C. The relational model R relates vertices connected by an edge.

Q1 is: (). \exists V.\exists C. (\bigwedge\limits_{(u,v) \in E} R(u,v) \wedge \bigwedge\limits_{(u,v)\in C, u\ne v} R(u,v))

Q2 is (). \exists C. \bigwedge\limits_{(u,v)\in C, u \ne v} R(u,v))

So what I think we’re trying to do is “fold” the variables in V into the variables in C, so that there is still a relation between each edge.  That only works if the vertices on each side of the edge are different colors because otherwise.the relation won’t show up (because of the u \ne v constraint).  But I’m not sure, and the proof in the paper stops after building this construction.

Difficulty: 9.  I’m pretty sure a lot of this is going over my head.

Protected: Nesetril-Rödl Dimension

This content is password protected. To view it please enter your password below:

Protected: Partition Into Cliques

This content is password protected. To view it please enter your password below:

Protected: K-Colorability

This content is password protected. To view it please enter your password below: