[20150611] Question #3
Assigned to: Juan Felipe Hernández AlbarracĂn
Stem
Find the PQR tree for the collection C = {he, dc, fb, dcifbg, ae, gb, ic, jc} under U = abcdefghij.
Answer
The strictly overlapping graph for the collection is:
Starting from U0 = U and C0 = C, we can consider H0 = aeh, since ae and he are from the same component in the graph. Performing the division, the next two U and C are obtained as follows:
| U1 = aeh |
| C1 = {he, ae} |
| U2 = bcdfgijU1 |
| C2 = {dc, fb, dcifbg, gb, ic, jc} |
For U1 and C1 (which is prime) there is a linear order that demands e between a and h, so there should be a Q node with e in the center.
A set H2 for U2 can be bfg, so the next two U and C are:| U3 = bfg |
| C3 = {fb, gb} |
| U4 = cdijU1U3 |
| C4 = {dc, dciU3, ic, jc} |
For U3 and C3 (which is prime) there is a linear order that demands b between f and g, so there should be a Q node with b in the center.
The set H4 for U4 is cdijU3, so the next two U and C are:| U5 = cdijU3 |
| C5 = {dc, dciU3, ic, jc} |
| U6 = U1U5 |
| C6 = ∅ |
C5 is prime and non trivial, but it demands c to be between d and i, and consecutive to j as well, which is impossible. So there should be an R node including the elements of U5.
C6 is prime and trivial, so there should be a P node including U5 and U1, which are the elements of U6.
The resulting tree is:
