11.8 ENTITY-RELATIONSHIP MODEL

This figure is an example from a paper by Campbell, Czejdo, and Embley. Rectangles represent entities, diamonds, relations between them, and ovals attributes. Both entities and relations can have attributes.

Purpose:

The four basic organizations (see below) cover all situations that can occur when building a database within the ER model. You declare entities and relations as C++ classes; ER attributes simply become attributes of these structures. All organizations are internally doubly linked, so that the "delete" operation and traversing through the network is fast in all directions.

The Four ER models:

ZZ_HYPER_1_TO_1 (id, sourceEntity, relation, targetEntity);

ZZ_HYPER_1_TO_N (id, sourceEntity, relation, targetEntity);

ZZ_HYPER_M_TO_1 (id, sourceEntity, relation, targetEntity);

ZZ_HYPER_M_TO_N (id, sourceEntity, relation, targetEntity);

The Four ER models:

ZZ_HYPER_1_TO_1 (id, sourceEntity, relation, targetEntity); declares 1-to-1 relation which is similar to DOUBLE_LINK, except that it has the relation object sitting in the middle of the link.

Using DOUBLE_LINK for this purpose is less fancy, but more efficient. The same thing applies to 1-to-N and M-to-1 relations below. Only the M-to-N relation is a special organization in its own right, which has no other simple representation.

ZZ_HYPER_1_TO_N (id, sourceEntity, relation, targetEntity); connects several target entities with one source entity, and is similar to SINGLE_AGGREGATE (formerly SINGLE_TRIANGLE), except for the relation sitting in the middle. If you don't keep any data on the relation itself, use SINGLE_AGGREGATE instead.

ZZ_HYPER_M_TO_1 (id, sourceEntity, relation, targetEntity); connects several source entities with one target entity, and is similar to SINGLE_AGGREGATE (formerly SINGLE_TRIANGLE), except for the relation sitting in the middle. If you don't keep any data on the relation itself, use SINGLE_AGGREGATE instead.

ZZ_HYPER_M_TO_N (id, sourceEntity, relation, targetEntity); connects several source entities with several target entities; the relation objects form the connections.

The access to all organizations is generic, as shown in the Syntax section.

Error protection:

As a result of strong typing, many coding errors get caught by the compiler. At run time, the organization is automatically protected against dangling pointers. An object must be completely disconnected before it can be freed. You cannot replace a relation using add(); first the old relation must be disconnected by del().

Required memory:

1_TO_1 1 pointer on each entity, 2 on the relation;
1_TO_N 1 pointer on each entity, 4 on each relation;
M_TO_1 1 pointer on each entity, 4 on each relation;
M_TO_N 1 pointer on each entity, 6 on each relation;

Fast name pickup:

In databases based on the ER model, fast pickup of an object's name is usually required. Use the HASH organization in conjunction with the ER model - see the example in orgC/test/test18a.c.

Alternate Implementation:

The four basic models permit uniform handling of all ER situations. However, relations that have no attributes can also be implemented as a DOUBLE_LINK (1_TO_1 relation) or as a DOUBLE_TRIANGLE (1_TO_N and M_TO_1 relations). Such representations use fewer objects and 2 less pointers per relation. The penalty is that some of the uniformity is lost.

Syntax:

ZZ_HYPER_1_TO_1(id,SOURCE,REL,TARGET);
ZZ_HYPER_1_TO_N(id,SOURCE,REL,TARGET);
ZZ_HYPER_M_TO_1(id,SOURCE,REL,TARGET);
ZZ_HYPER_M_TO_N(id,SOURCE,REL,TARGET);		 These statements declare the 4 basic relations. SOURCE stands for the type of the source entity, REL stands for the relation, and TARGET for the type or the target entity.
void id.add(SOURCE *s,REL *r,TARGET*t); Adds relation r between entities s and t.
void id.del(REL *r); Disconnects the given relation.
REL* id.fwd(SOURCE *s); For a given source node, this returns the first relation starting from it (fwd=FORWARD).
REL* id.bwd(TARGET *t); For a given target entity, this returns the first relation leading to it (bwd=BACKWARD).
SOURCE* id.source(REL *r); For a given relation, it returns the source entity.
TARGET* id.target(REL *r); For a given relation, it returns the target entity.
SOURCE *s; REL *r;
id_sIterator is(s);
while(r=is++){ ... }		 For a given s, this loop traverses all relations starting at s.
TARGET *t; REL *r;
id_tIterator it(s);
while(r=it++){ ... }		 For a given t, this loop traverses all relations that lead to t.
is.start(s);
it.start(t);		 Restart the iterators.

Examples:

  1. See files macro/hyp1to1, macro/hyp1ton, macro/hypmto1, and macro/hypmton.
  2. test18a.c contains a comprehensive test of all ER features on the database shown in the figure above.

 

Previous Section 11.7 STACK Next Section 11.9 Property (Run-Time Extensibility)