download

Likewise, the same argument holds for the imposition of a binary cardinality of M:1 between Y and Z. Attempting to impose this cardinality between Y and Z, requires a 1:1 relationship between X:Y that conflicts with the M:1 relationship established by the first imposition between X:Y. The secondary imposition of M:1 between Y and Z is also disallowed.

The remaining possibility of 1:M between Y:Z is allowed, but we have an additional implication. Consider that X:Y was explicitly imposed as M:1, and Y:Z has now been explicitly imposed as 1:M. Following the initial imposition between X and Y the relationship X:Z was implicitly derived due to the imposition of the X:Y constraint. With the additional imposition of the Y:Z constraint, the relationship X:Z is now implicitly required to adopt a binary cardinality derived from the dual imposition. This implicitly derived cardinality must be 1:1. The resultant structure caused by the dual imposition, is identical to that derived in Table 9(c), where all three relationships are mandated (or Table 13b, where the 1:1 imposition between X and Z is considered as the secondary imposition, fixing the binary relationship Y:X as 1:M).

	initial binary	result	additional binary	result
13(a)	X:Y is M:1	X:Y is M:1	Y:Z is 1:M	X:Y is M:1
		X:Z is M:1		X:Z is 1:1
		Y:Z is M:N		Y:Z is 1:M
13(b)	X:Y is M:1	X:Y is M:1	X:Z is 1:1	X:Y is M:1
		X:Z is M:1		X:Z is 1:1
		Y:Z is M:N		Y:Z is 1:M

Table 13. 1:1:1 with multiple binary impositions2

5.2.Ternary Cardinality M:1:1

Due to the equal symmetry of the structure in a 1:1:1, the resultant structure derived in

Section 5.1 was the same, regardless of which imposition was made first, or in which order. In the case of M:1:1, the situation is more complex. We can consider this case in two distinct sections. The first is if the initial binary imposition is between X:Y (or by symmetry, X:Z), and the second if the initial binary imposition is between Y:Z.

(a) According to the EBP rule, the only imposition allowed between X:Y (or X:Z) is M:1 (see Table 6). Either of these sets up a cardinality structure as previously described in Table 10(a & b), with X:Z and X:Y both being M:1. Y:Z is unchanged as M:N and therefore subject to

21:1 between Y:Z, M:1 between Y:Z and 1:M between X:Z are invalid as additional impositions due to conflict with cardinality requirements of initial binary imposition.

21

	initial binary	result	secondary binary	result
14(a)	X:Y is M:1	X:Y is M:1	Y:Z is 1:1	X:Y is M:1
	(also X:Z is M:1)	X:Z is M:1		X:Z is M:1
		Y:Z is M:N		Y:Z is 1:1
14(b)	X:Y is M:1	X:Y is M:1	Y:Z is M:1	X:Y is M:1
	(also X:Z is M:1)	X:Z is M:1		X:Z is M:1
		Y:Z is M:N		Y:Z is M:1
14(c)	X:Y is M:1	X:Y is M:1	Y:Z is 1:M	X:Y is M:1
	(also X:Z is M:1)	X:Z is M:1		X:Z is M:1
		Y:Z is M:N		Y:Z is 1:M

Table 14. M:1:1 with multiple binary imposition

further imposition. Unlike the considerations in the 1:1:1 cardinality, according to the EBP rule, this cardinality allows the imposition of any binary cardinality between Y:Z. The potential combinations are as shown in Table 14.

(b). The second alternative, where the initial imposition of the binary is between Y:Z, is closely related to the initial alternative. In this situation, we can consider various options in the initial imposition, but the secondary choices for imposition are limited due to the first. From the analysis in Table 10 (c),(d) & (e) (also left side of Table 15, below),we can see that regardless of the cardinality imposed between Y:Z that the remaining binary cardinalities remain as M:N. That is, there is no implicit constraint on either, caused by the initial imposition. In considering further impositions, we must also remember the implicit requirements of the ternary itself. Since both remaining relationships (X:Y and X:Z) are both M:1 within the ternary, the potential binary impositions are restricted according to the EBP rule. Due to the EBP rule, 1:1 impositions are disallowed, but M:1 constraints are allowed. The potential combinations are detailed in Table 15.

	initial binary	result	secondary binary	result
15(a)	Y:Z is 1:1	X:Y is M:N	X:Y is M:1	X:Y is M:1
		X:Z is M:N	(also X:Z is M:1)	X:Z is M:1
		Y:Z is 1:1		Y:Z is 1:1
15(d)	Y:Z is M:1	X:Y is M:N	X:Y is M:1	X:Y is M:1
		X:Z is M:N	(also X:Z is M:1)	X:Z is M:1
		Y:Z is M:1		Y:Z is M:1
15(c)	Y:Z is 1:M	X:Y is M:N	X:Y is M:1	X:Y is M:1
		X:Z is M:N	(also X:Z is M:1)	X:Z is M:1
		Y:Z is 1:M		Y:Z is 1:M

Table 15. M:1:1 with multiple binary imposition3

31:1 and 1:M between X:Y (or X:Z) are invalid as additional impositions due to EBP rule.

22

5.3.Ternary Cardinality M:N:1

In this final ternary cardinality that allows explicit imposition of a binary relationship, the

initial explicit imposition must be M:1 applied to X:Z or Y:Z (according to the EBP rule, Table 4(a)). We note that the imposition of the M:1 constraint does not affect the M:N cardinalities of the remaining two binary relationships. However, no further imposition can be made between X:Y due to the EBP rule (the ternary relationship requires M:N between X and Y). The single remaining combination between Y and Z, is likewise governed by the EBP rule but does allow the imposition of a M:1 without any conflict or impact on the previously established structure. The Table of possibilities for the ternary relationship of M:N:1 is as follows:

	initial binary	result	secondary binary	result
16(a)	X:Z is M:1	X:Y is M:N	Y:Z is M:1	X:Y is M:N
	(or Y:Z is M:1)	X:Z is M:1	(or X:Z is M:1)	X:Z is M:1
		Y:Z is M:N		Y:Z is M:1

Table 16. M:N:1 with multiple binary imposition4

5.4.Ternary Cardinality M:N:P

Since all binary pairs within the ternary are required to be M:N (unconstrained), the EBP rule

does not allow for the imposition of any explicit binary cardinalities. There is, therefore, no

consideration as to initial or secondary impositions for this cardinality.

5.5.Proof of Multiple SCB Relationship Imposition

As with the imposition of the single binary relationship on any specific ternary relationship,

the resulting cardinality combination of imposing a second binary relationship can be proven with functional dependency analysis.

Consider a ternary relationship with cardinality M:1:1, with the binary imposition of Y:Z having cardinality of 1:1. The dependencies identified from these criteria are as follows:

XZ → Y

XY → Z

Y → Z

Z → Y

41:1 and 1:M between Y:Z are invalid as additional impositions due to EBP rule.

23

Since the only binary relationships that can be identified from these dependencies are those between Y and Z, we can conclude that the binary cardinalities within this structure are:

X:Y = M:N X:Z = M:N Y:Z = 1:1

(Table 10(e))

The imposition of a secondary binary relationship between X:Y of cardinality M:1, creates an additional dependency of X → Y. If we add this to the original dependency set we can derive the following complete dependency set:

XZ → Y

XY → Z

Y → Z

Z → Y

X → Y

X → Z

Due to the identification of the dependencies between X:Y, X:Z and Y:Z , we can conclude the following embedded cardinalities:

X:Y = M:1 X:Z = M:1 Y:Z = 1:1 (Table 15(a))

All structures derived from the imposition of secondary binary relationships (Table 13 through 16) can be likewise validated using functional dependency analysis.

6. DECOMPOSITION STRATEGIES

In this section we briefly discuss the application of the binary imposition rules to the decomposition of ternary relationships. This is not intended to be a complete analysis of this topic, but an introduction, demonstrating the potential relevance of the rule set.

It is known that a ternary relationship can be decomposed into two binary relationships provided that a 1:1 relationship exists between any two entities involved in the ternary relationship (Elmasri & Navathe, 1989). We note, however, that this rule does not specify the implicitness or explicitness of the 1:1 binary cardinality with respect to the ternary relationship. Neither does the observation identify the ternary cardinalities on which the 1:1 binary cardinality can be imposed. According to our EBP rule, 1:1 is only allowed in 1:1:1 and 1:1:M ternary cardinalities (Table 5 & Table 6). Ternary cardinalities of M:N:P and M:N:1 can never have 1:1 relationships between any of two entities involved (Table 7 and Table 8). This implies that the rule stated by Elmasri & Navathe is not generalizable to all ternary relationships.

24

X

M

1

Y

N

Z

Figure 7. Ternary Relationship

with M:1:N Cardinality

If we have an analysis that imposes a binary relationship of 1:M on a ternary, then a further set of considerations arises from the possibility of decomposing this ternary relationship.

Figure 7 shows a ternary relationship having cardinality of M:1:N. Without an explicitly imposed binary relationship the cardinality between X and Y is M:N (IBC rule, Sect. 3.5).

	M		1
X	M	1	Y
		N

Z

Figure 8. M:1:N with Imposed

M:1 Binary Relationship

Figure 8 shows the imposition of a binary relationship between X and Y with cardinality of M:1 (allowed by EBP rule, Sect. 4.1). We have now changed the actual relationship between X and Y to agree with the binary so the specific relationship between X and Y is now M:1 (Table 11(a),

		M	1
	X			Y
N						M

M Z N

Figure 9. Binary

Representation of Figure 8

25

M	1
X	Y

M

Z N

Figure 10. Lossy Decomposition

Of Figure 9

Sect. 4.2).

Since the implicit cardinalities between XZ and YZ are both M:N (IBC rule), we can view the ternary relationship as three binary relationships (Figure 9). This consideration does not negate the requirements of the ternary inclusion constraints.

The question is now posed; can the ternary relationship be losslessly decomposed to a simpler format? If we consider the decomposition as in Figure 10, a lossless decomposition cannot be guaranteed.

In Figure 10, we see that the relationship Z:Y is M:N, that is, for each instance of Z we have multiple instances of Y. Further, the directional relationship Y:X is likewise 1:N. If we then consider whether we can associate all correct instances of Z with the correct instances of X, it is possible to develop spurious tuples from making all possible associations through Y, which may not have been present in the original instance set. The following example demonstrates this:

X1 : Y1 : Z1

X1 : Y1 : Z2

X2 : Y1 : Z1

X3 : Y3 : Z1

This relation, demonstrates a ternary relationship adhering to the required cardinality of M:1:N, as well as demonstrating a specific binary cardinality of M:1 between X:Y. Thus the cardinality requirements are met, as well as the rules of ternary and binary combination established earlier. Following the strategy in Figure 10, this relation can be decomposed into the following two tables:

26

X1 : Y1	Y1 : Z1
X2 : Y1	Y1 : Z2
X3 : Y3	Y3 : Z1

The decomposition maintains the cardinalities of M:1 between X and Y, and M:N between Y and Z. If the tables are now recomposed using all possible combinations of X and Z through Y, we can develop a spurious tuple X2:Y1:Z2 that was not part of the original relation.

M	1
X	Y

N

M	Z

Figure 11. Lossless Decomposition

of Figure 9

Alternatively, if we decompose the table with entity X as the common entity

(diagrammatically shown in Figure 11), we arrive at the following set of tables:

X1 : Y1	X1 : Z1
X2 : Y1	X1 : Z2
X3 : Y3	X2 : Z1
	X3 : Z1

If we now recompose these tables we note that the original table is recreated, indicating a lossless decomposition. This decomposition strategy is also supported by the functional dependency analysis shown in Section 4.3 where we developed the dependency of both Y and Z on entity X.

This section has demonstrated that decomposition strategies are available in situations other than when a 1:1 cardinality exists in a ternary relationship. When considering the use of ternary relationship modeling in ER diagrams we must consider a number of factors to decide whether the ternary can be decomposed to two binary relationships. Elmasri (1989) established a criterion for decomposition when a 1:1 binary relationship exists. Here we have identified the circumstances

27

where this condition can exist, as well as going beyond these considerations to demonstrate other possibilities for decomposition of ternary relationships, specifically where a 1:M exists.

7. SUMMARY

In this paper we have progressively considered ternary relationships and the potential for combining them with binary relationship constraints. Initially we identified the implicit cardinalities of the binary combinations embedded in ternary relationships and established the Implicit Binary Cardinality (IBC) rule. Next we identified which binary cardinalities could be imposed on which ternary relationships, establishing the Explicit Binary Permission (EBP) rule. The final part of the analysis consisted of demonstrating how the imposition of binary relationships on ternary structures, alters the implicit binary relationships between the entities. This established the Implicit Binary Override (IBO) rule. This rule set is particularly important since the theory behind the co-existence of binary relationships within ternary relationships has not been formalized. We have found instances where our findings presented here correct examples offered in previous works (e.g., Jajodia et al. (1983), p.622; Markowitz & Shoshani (1989), p.432; Markowitz Shoshani (1992), p.426). We believe this rule set provides parameters for ternary relationship specification during ER modeling. Previously, no theoretical basis has been offered to explain the dynamics implicit in ternary relationships. Our work now provides a basis for both practitioners, to incorporate into their modeling structures, as well as educators, to explain the formalities of ternary structures and combinations of such with binary relationships.

Section 6 has demonstrated how the findings and rules established in this paper, are important to any considerations of ternary relationship decomposition. We have demonstrated that given the presence of certain binary relationships imposed on ternary relationships, the ternary can be decomposed to two binary relationships.

We have provided a framework which will allow users of ER models to verify the accuracy of their use of ternary relationships. Our rules also provide a means for identifying the potential for decomposing the ternary relationship to a simpler format and additionally, the means of ensuring the correct decomposition. We believe these findings to be important to analysts and designers seeking assistance in accurately modeling ternary relationships when using ER models. One aspect of ternary relationship not addressed is the question of the initial identification of ternary relationships. This question must be answered from the point of view of the semantics or situational dynamics of a particular problem domain. Since this paper has addressed the analysis of the logic inherent to predetermined ternary relationships, we leave the question of specifically when to use a ternary relationship to future analysis.

28

REFERENCES

Batini, C., Ceri, S., Navathe, S. Conceptual Database Design. Benjamin/Cummings, Redwood City, CA. 1992.

Chen, P.P. (1976) The entity-relationship model: towards a unified view of data. ACM Transactions on Database Systems, 1(1), pp. 9 -- 36.

Chung, I., Nakamura, F., Chen, P. (1981) A decomposition of relations using the entity-relationship approach. In Proceedings of the Second International Conference on Entity-Relationship Approach (Washington, D.C.). ER Institute, Saugus, CA. 1981, 151 -- 173.

Elmasri, R., and Navathe, S. Fundamentals of Database Systems. Benjamin/Cummings, Redwood City, CA. 1989.

Hawryszkiewycz, I.T. Database Analysis and Design, 2nd Ed. Macmillan Publishing Co., 1991.

Jajodia, S., Ng, P., Springsteel, F. (1983) The problem of equivalence for entity-relationship diagrams. IEEE Transactions on Software Engineering, v. SE-9(5), September, 1983, 617 -- 630.

Ling, T-W. (1985a) A normal form for entity-relationship diagrams. In Proceedings of 4th International Conference on the Entity-Relationship Approach (Chicago). IEEE Computer Society Press, Silver Springs, MD., 1985, pp. 24 -- 35.

Ling, T-W. (1985b) An analysis of multivalued and join dependencies based on the EntityRelationship approach. Data and Knowledge Engineering, v.1, pp. 253 -- 271.

Markowitz, V.M. & Shoshani, A. (1989) On the correctness of representing extended entityrelationship structures in the relational model. In Proceedings of 1989 ACM SIGMOD, Portland, OR., May 31 -- June 2, 1989, pp. 430 -- 439.

Markowitz, V.M. & Shoshani, A. (1992) Representing Extended Entity-Relationship Structures in Relational Databases: a Modular Approach. ACM Transactions on Database Systems, v.17(3), September, 1992, pp. 423 -- 464.

Teorey, T.J. Database Modeling and Design: The E-R Approach. Morgan-Kauffman, 1990.

Teorey, T.J., Yang, D., Fry, J.P. (1986) A logical design methodology for relational databases using the extended entity-relationship model. Computing Surveys, 18:12, June, pp. 197 -- 222.

29