From: Giorgio Valoti

To: Editor

Date: 3 May 2005

 

In Tree-structured Data: A Relational Perspective it is stated (p. 15) that the tree depicted in Fig. 5 is not a tree at all, because part P4 is repeated, and it's replaced with the graph showed in Fig. 6. Then relational solution to the bill-of-materials problem, using transitive closure, is showed. However, I fail to see how to extend this solution to the tree structures in chapter 7 of PRACTICAL ISSUES IN DATABASE MANAGEMENT.

 

More specifically, given a tree structure like that in Fig.1 and its relational equivalent representation:

 

---------+----------

MAJOR_P# | MINOR_P#

=========+==========

P1       | P2

P1       | P3

P1       | P4

P2       | P5

P2 | P6

P4       | P9

P5       | P7

P6       | P8

--------------------

 

 

Figure 1

 

We can use the transitive closure to solve the bill-of-material explosion problem. However, in general, the same part might appear more than once, and at different levels in the structure, like P4 in fig.2.

 

 

Figure 2

 

P4 now has two direct parents, P1 and P2, thus violating the definition of a true hierarchy (where each child has exactly one direct parent).

 

Date considers the tree-like structure in Fig. 3 a better representation, which can be easily represented in a relational form.

 

Figure 3

 

But we can transform Fig. 2 in Fig. 3 only if we agree that the two representations mean the same structure, namely that P4 always has two parents, P1 and P2 (and one child, P9). However, we could give to Fig. 2 a different meaning than that of Fig. 3: the two P4’s are two distinct instances of the same part. If so, we cannot use the relational representation we gave before, because it does not distinguish between the two P4 instances.

 

 

Fabian Pascal Responds: Fig. 3 is not, in my opinion, a "better" representation of fig. 2, but a network (graph), not a true tree structure. In Fig. 2 there are two distinct instances of P4 at different levels in the structure. In Fig. 3 there is only one instance of P4. In other words, the representation in Figure 3 does not distinguish between parts and instances thereof (in fact, P9 has also two instances, and two direct parents, which happen to be two instances of the same part P4).

 

If a distinction between parts and instances is necessary and kept, then the structure in Figure 2 may be considered a tree, with each child instance having exactly one instance as a direct parent, in which case, the two structures are not equivalent.

 

Chris Date apparently eschews this issue in his paper, and has not offered a reply to your question.

 

 

Posted 7/15/05