You’re working with a large database of employee records. For the purposes of this question, we’ll picture the database as a two-dimensional table T with a set R of m rows and a set C of n columns; the rows correspond to individual employees, and the columns correspond to different attributes.

To take a simple example, we may have four columns labeled

name, phone number, start date, manager s name

and a table with five employees as shown here.

 

Given a subset S of the columns, we can obtain a new, smaller table by keeping only the entries that involve columns from S. We will call this new table the projection of T onto S, and denote it by T[S]. For example, if S = {name, start date}, then the projection T[S] would be the table consisting of just the first and third columns.

There’s a different operation on tables that is also useful, which is to permute the columns. Given a permutation p of the columns, we can obtain a new table of the same size as T by simply reordering the columns according to p. We will call this new table the permutation of T by p, and denote it by T_p.

All of this comes into play for your particular application, as follows. You have k different subsets of the columns S₁, S₂,..., S_k that you’re  going to be working with a lot, so you’d like to have them available in a readily accessible format. One choice would be to store the k projections T[S₁], T[S₂], . . . , T[S_k], but this would take up a lot of space. In considering alternatives to this, you learn that you may not need to explicitly project onto each subset, because the underlying database system can deal with a subset of the columns particularly efficiently if (in some order) the members of the subset constitute a prefix of the columns in left-to-right order. So, in our example, the subsets {name, phone number} and {name, start date, phone number,} constitute prefixes (they’re the first two and first three columns from the left, respectively); and as such, they can be processed much more efficiently in this table than a subset such as {name, start date}, which does not constitute a prefix. (Again, note that a given subset S_i does not come with a specified order, and so we are interested in whether there is some order under which it forms a prefix of the columns.)

So here’s the question: Given a parameter â„“ â„“  permutations of the columns p₁, p₂,..., p _â„“ so that for every one of the given subsets S_i (for i = 1, 2, . . . , k), it’s the case that the columns in S_i constitute a prefix of at least one of the permuted tables T_p1 , T_p2 ,..., T_pâ„“  ? We’ll say that such a set of permutations constitutes a valid solution to the problem; if a valid solution exists, it means you only need to store the â„“ permuted tables rather than all k projections. Give a polynomial-time algorithm to solve this problem; for instances on which there is a valid solution, your algorithm should return an appropriate set of â„“  permutations.

Example. Suppose the table is as above, the given subsets are

S1 = {name, phone number},

S2 = {name, start date},

S3 = {name, manager s name, start date},

and â„“ = 2. Then there is a valid solution to the instance, and it could be achieved by the two permutations

p1 = {name, phone number, start date, manager s name},

p2 = {name, start date, manager s name, phone number}.

This way, S₁ constitutes a prefix of the permuted table T_p1 , and both S₂ and S₃ constitute prefixes of the permuted table T_p2 .