P. Loos: Capture More Data Semantic Through The Expanded Entity-Relationship Model,
Arbeitsbericht des Instituts für Wirtschaftsinformatik, Nr. 53, Münster, March 1997

Capture More Data Semantic Through The Expanded Entity-Relationship Model (PERM)

Contents

Abstract

The Expanded Entity-Relationship Model, an extension to the common ER approach, is presented. The extension makes it possible to express more static data semantic of applications. It focuses on precise qualification of relationship types and on a concept for a graphical representation of inter-relationship wide integrity constraints.

1. Introduction

Section 2 gives on overview over the basic concepts of ERM also used in PERM. Section 3 stresses the necessity for additional classification and qualification of n-ary relationships. Section 4 introduces the concept of relationships with alternative entity types. Section 5 deals with a classification of further semantic integrity constraints and their graphical representation using Relationship-Constraint diagrams (RC diagram). The concepts are illustrated with examples.

2. Basic Concepts

Figure 1: Basic Concepts of the Entity-Relationship Model

• Entities are real or abstract things which are relevant in the universe of discourse, e.g. customers, articles, and orders in the universe of discourse of an enterprise. Entities can be described by properties. If entities can be described by the same kind of properties, they are regarded as sets and referred to as entity types, their individual instances being the entities. Entity types are represented in the diagram of the ERM by using rectangles.

• Relationships are logical connections between two or more entities. Connected entities can belong to the same entity type. Although entities can exist in their own right, relationships can only be defined in combination with the relevant entities. Therefore relationships can be regarded as aggregations of entities. A set of relationships connecting entities of the same entity type is called relationship type. Between the same entity types several different relationship types can exist, e.g. between the entity type employee and department the relationship types works in and manage may exist. A relationship type is graphically represented by a diamond, which is connected to the relevant entity types with single lines. A relationship type must have at least two connection lines.

  Relationship types can be distinguished by the number of possible relationships a particular entity can have concerning the regarded relationship type. This range of numbers is called cardinality. The range is specified by the minimum and maximum number of relationships. Typically, a lower boundary of 0 or 1 and an upper boundary of 1 or n (many) are distinguished. This kind of indication is called (min,max)-notation. The (min,max)-notation is depicted at the connecting lines between the rectangles and the diamonds. Sometimes the cardinality is depicted by other graphical representations e.g. as 'crow feet', as double arrows or as shadowed diamonds. It must also be stressed that the side of the relationship on which the cardinality is denoted varies [Loos 93], but only the way used here is sensible with n-ary relationship types.
  

• Properties describing entities or relationships are called attributes. An attribute of an entity type machine may be hourly rate. Each attribute has a certain domain, e.g. a currency amount between 10 and 1000. For an entity machine A567 of the entity type machine the value of the attribute hourly rate may be $ 240. Attributes are usually listed in a circle or an oval which is connected to the relevant entity type or relationship type.

• With generalization, sets of different entity types can be grouped into a new super set. This is done if the entities of the generalized entity type have things in common, especially the same attributes or common relationship types. Since the subtypes have the same properties as the super type by definition, this kind of relationship is also called IS A relationship or specialization. The generalization is graphically denoted as a triangle, where the super type (generalized entity type) is connected with a corner of the triangle. Generalizations can be classified by the mutual relations of the instances of the entity types of the subsets [Hainaut et al. 96]. In a complete generalization each instance of the super type is at least an instance of one subtype. In a disjunctive generalization each instance of the super type can be the instance of at most one subtype. This classification is expressed according to the cardinality and denoted in the triangle as follows:
  (1) non-complete, disjunctive (0,1)
  (2) non-complete, non-disjunctive (0,n)
  (3) complete, disjunctive (1,1)
  (4) complete, non-disjunctive (1,n)
  

• Relationship types result from an aggregation of one or several entity types. In the subsequent process of modeling the relationship type can be used as a component for further relationship types. In order to provide the reuse of relationship types in relationships their reinterpretation as an entity type is applied. It is denoted in the ER diagram as a diamond surrounded by a rectangle. In order to reveal the modeling process which leads to the reinterpreted relationship type, the connecting lines coming from the aggregated entity types should touch the diamond, whereas the connecting lines coming from the reinterpreted relationship type should start from the edges of the rectangle.

3. Cardinality and Determinants

Assume the relationship works is connecting the entity types employee, department, and project. An employee can work in several departments in various projects. He can also work on a certain project in various departments. In a department several employees are working on different projects. A project can be processed in different departments by various employees. For each entity of all three types relationships are optional. This leads to cardinalities with (min)-values of 0 for all three lines to the relationship type works. On the other side each entity of all entity types can have several relations, which leads to (max)-values of n, i.e. all cardinalities are (0,n).

Now the example is modified. An employee may work in several departments, but in each department he is admitted to work in one project only. The rest of the scenario remains the same.

For the identification of the cardinalities it is decisive that each employee can work in many different combinations of departments and projects. The same is true for the entity types department and project for their respective relationships. This example illustrates that different scenarios of tenary relationship types lead to the same cardinality denotations, i.e. the cardinality qualification with (min,max)-notation is not sufficient and not unique to the application semantic.

For a unique identification of different semantic scenarios, functional dependencies can be applied [Date 81]. The functional dependencies show, which entities from the combined entity types are necessary for the uniqueness of the relationship. With that, functional dependencies are indicators for the max-values of the (min,max)-notation. Suppose there are three entity types A, B, and C forming the relationship type D, eight different classes of relationship types can be differentiated with the functional dependency and cardinality notations as shown in Table 1 (a -> b means that b is functionally dependent on a).

Class	Functional dependencies	Cardinality of A to D	Cardinality of B to D	Cardinality of C to D
(1)	a,b,c -> Ø	(0,n)	(0,n)	(0,n)
(2)	a,b -> c	(0,n)	(0,n)	(0,n)
(3)	a,b -> c and a,c -> b	(0,n)	(0,n)	(0,n)
(4)	a,b -> c and a,c -> b and b,c -> a	(0,n)	(0,n)	(0,n)
(5)	a -> b,c	(0,1)	(0,n)	(0,n)
(6)	a -> b,c and b -> a,c	(0,1)	(0,1)	(0,n)
(7)	a -> b,c and b -> a,c and c -> a,b	(0,1)	(0,1)	(0,1)
(8)	a -> b,c and b,c -> a	(0,1)	(0,n)	(0,n)

Table 1: Classes of Tenary Relationship Types

When applying cardinality notations without functional dependencies only 4 classes can be distinguished (combination without order with repetition of 2 elements of the degree of 3, Cr₂⁽³⁾ = 4). With quadrary relationship types even 24 different classes of functional dependencies can be distinguished. The first scenario of the example is equivalent to class (1). The modified scenario is equivalent to class (2), where A is the type employee, B is the type department, and C is the type project. In Figure 2 the eight classes are shown as tenary relationship types and their respective representation with binary relationship types. The tenary relationship types and the respective binary relationship types depict the same semantic concerning the relation possibilities of the entity types A, B, and C.

Figure 2-1: Different Kinds of Tenary Relationships (Class 1, 2, 3, 4)

Figure 2-2: Different Kinds of Tenary Relationships (Class 5, 6, 7, 8)

The resolution illustrates the necessity of unique classification of n-ary relationship types. The unique notation using functional dependencies is called determinant within the PERM. Determinants are added to the n-ary relationship types with an open hexagon as shown in Figure 3. Cardinalities only need to be depicted if the min-values is not 0 or the max-value is not 1 or n. For binary relationship types the max-values of the cardinality and determinants are equivalent.

Figure 3: Tenary Relationship Type with Determinants

4. Relationships with Alternative Entity Types

An example is that an employee can either be assigned to production areas or to projects. This semantic can easily be expressed by relationship types with alternative entity types without applying generalization as a more inconvenient possibility.

Figure 4 shows the graphical notation. A particular relationship B1 of relationship type B of a certain instance A1 of type A (e.g. employee) is a connection to either an instance C1 of type C (e.g. production area) or an instance D1 of type D (e.g. project).

Figure 4: Relationship Type with Alternative Entity Types

5. Integrity Constraints

Semantic which has not been covered through the concepts mentioned up to now is introduced through explicit integrity constraints. The integrity constraints are limited to static conditions since transitional and dynamic conditions are beyond the scope of data models [Lipeck 89].

Object type internal integrity constraints can effect single entities as well as object subset. Integrity constraints effecting a single entity are either domains, derived attributes (e.g. the age can be derived from the birth date and the current date), conditional attributes (e.g. the values 'unmarried' of the attribute marital status exclude some values of the attribute tax class of a certain instance of the entity type person), or mutually dependent attributes (the value of the attribute starting date must always be smaller than the value of the attribute ending date).

Integrity constraints on sets of entities can either effect the minimal or maximal number of instances of a type (which is also called absolute cardinality constraint [Lenzerini/Santucci 1983]) or conditions on sum or average values.

Relationship related integrity constraints are describing conditions between different types of entities. These conditions refer to either single relationship types or multiple relationship types.

Single relationship typs constraints are relationship type specifications through cardinalities and determinants, relationship derived attributes (e.g. the values of the attribute number of employees of the entity type department can be derived from the number of relationships of a certain instance to the entity type employee), object instance dependent relationships (the ability of relationships of an instance depend on the values of certain attributes, e.g. an entity material can only be related as superior part to the type bill of material if the material is classified with the values assembly part or end product, and vice versa only be related as subordinated if the material is classified with the values assembly part or component part), and object combination dependent relationships (the ability of relationship between certain entities depends on the combination of values of their attributes, e.g. within the relationship instructs it should be guaranteed that the boss is always more senior than the subordinate).

Conditions concerning multiple relationship types can be distinguished into conditions involving direct relationship types (single depth) and conditions involving indirect relationship types. In the case of conditions of single depth, relationships can either exclude each other mutually or can be mutually dependent (e.g. if a production order is assigned to a tool, it must also be assigned to a machine). An example for mutual exclusion is that an employee can either be assigned to a production area or to a project. The range of effect can be even more differentiated. Some kinds of exclusion can be expressed by generalization. An example for mutual dependency may be a production order that must be assigned to a machine before assigning it to a tool. Certain kinds of mutual dependencies can be expressed with n-ary relationship types.

Indirect relationship effecting constraints are the relationship path cardinality, the relationship path constraint and the recursion constraint. The relationship path cardinality defines a cardinality condition between entity types that are only connected indirectly. These conditions can also be expressed by realizing the direct connection with separate relationships and additional relationship path constraints. Relationship path constraints define conditions concerning dependency or exclusion between two entity types that are connected through two paths of relationships. Figure 5 gives an overview about the classification of semantic integrity constraints.

Figure 5: Classification of Semantic Integrity Constraints

Object type internal integrity constraints can be expressed by a formal notation oriented at the Backus-Naur-Form [Hopcroft/Ullman 1969]. The notation is depicted in an open hexagon with the object type according to the determinants. If the ER diagram becomes too complex, the formal notation can also be separated in a figure of its own with number references in the open hexagons.

Relationship related integrity constraints in Backus-Naur-Form can also be complex very easily. Therefore a graphical representation is preferred.

The graphical notation is analogous to the ER notation, but the integrity constraints are formulated on instance level, e.i. entity level and relation level, rather than the entity type level of common ER diagrams. For an easy distinction the instance level is depicted with dashed lines rather than full lines. The instance level diagram refer to the Occurrence Structure Concept [Tabourier/Nanci 1983] and is called Relationship-Constraint diagrams or RC diagram. In these diagrams integrity constraints are illustrated with object instances, i.e. with entities and their relationships.

Figure 6 gives a PERM example including a RC diagram. The tenary relationship is specified through a determinant. Constraint <1.1> is specifying that an employee can get instructions in a certain project only by one superior, i.e. the relationship type instructs is of relationship type class (2) as described in Table 1. A relationship path constraint ensures, that two employees involved in an instruction hierarchy (relationship type instructs) are working in the same project. This is expressed by condition <1.2>. The numbers in parenthesis can be regarded as an index in order to distinguish different instances of an entity type. Condition <1.2> can be read and interpreted as follows: if employee 1 can instruct employee 2 in project 1, then both employees must be assigned by the relationship type works to the same project 1.

Figure 6: Integrity Constraints with RC diagram

If the integrity constraints are active in only one direction, the connecting lines between diamonds and rectangles are shown as directed graphs. An object combination dependent relationship is shown in <1.3>. It is denoted that employee 1 giving instructions to employee 2 must have at least the same age as employee 2. The recursion constraint <1.4> excludes that an employee can give instructions to itself, regardless if it is direct or indirect through various steps of other employees.

6. References

Date, C. J.: An Introduction to Database Systems Reading, Vol. I, Massachusetts 1981.

Hainaut, J.-L.; Hick, J.-M.; Englebert, V.; Henrard, J.; Roland, D.: Understanding the Implementation of IS-A Relations, in: Thalheim, B. (ed.) Conceptual Modeling, Proceedings ER'96, Berlin-Heidelberg-New York 1996, pp 42-57.

Hopcroft, J. E.; Ullman, J. D.: Formal Languages and their Relation to Automata, Readings-Menlo Park-London-Don Mills 1969.

Lenzerini, M.; Santucci, G.: Cardinality Constraints in the Entity-Relationship Model, in: Davis C. G. et al. (eds.), Entity-Relationship Approach to Software Engineering, Amsterdam-New York-Oxford 1983, pp 529-549.

Lipeck, U. W.: Dynamische Integrität von Datenbanken - Grundlagen der Spezifikation und Überwachung, Berlin et al. 1989.

Loos, P.: Datenstrukturierung in der Fertigung, München-Wien 1992.

Loos, P.: Representation of Data Structures Using the Entity Relationship Model and the Transformation in Relational Databases, in: Veröffentlichungen des Instituts für Wirtschaftsinformatik, paper #100, Saarbrücken, January 1993.

Moody, D.: Graphical Entity Relationship Models: Towards a More User Understandable Representation of Data, in: Thalheim, B. (ed.) Conceptual Modeling, Proceedings ER'96, Berlin-Heidelberg-New York 1996, pp 227-244.

Scheer, A.-W.: Business Process Engineering: Reference Models for Industrial Enterprises, 2nd ed., Berlin et al. 1994.

Tabourier, Y.; Nanci, D.: The Occurrence Structure Concept: An Approach to Structural Integrity Constraints in the Entity-Relationship Model, in: Chen, P. P. (ed.), Entity-Relationship Approach to Information Modeling and Analysis, Amsterdam-New York-Oxford 1983, pp 73­108.

Teorey, T. J.: Database Modeling and Design - The Entity-Relationship Approach, San Mateo 1990.