ER Model Cardinality Constraints

• Chapter 6 focuses on Database Design Using the Entity-Relationship Model.
• The chapter uses "Database System Concepts, 7th Ed." by Silberschatz, Korth, and Sudarshan as a reference.

Outline of Topics:

• Overview of the Design Process
• The Entity-Relationship Model
• Complex Attributes
• Mapping Cardinalities
• Primary Key
• Removing Redundant Attributes in Entity Sets
• Reducing ER Diagrams to Relational Schemas
• Extended E-R Features
• Entity-Relationship Design Issues
• Alternative Notations for Modeling Data
• Other Aspects of Database Design

Design Phases:

• The initial phase involves characterizing the data needs of prospective database users.
• The second phase:
  • Choosing a data model
  • Applying the concepts of the chosen data model
  • Translating requirements into a conceptual schema of the database
  • Developing a conceptual schema indicating functional requirements of the enterprise
  • Describing the kinds of operations or transactions performed on the data

Design Phases (Cont.):

• Final Phase: Moving from an abstract data model to implementing the database.
  • Logical Design, which involves deciding on the database schema.
  • Business decisions determine what attributes to record in the database.
  • Computer Science decisions determine the relation schemas and attribute distribution.
  • Physical Design, which involves deciding on the physical layout of the database.

Design Alternatives:

• When designing a database schema, avoid two major pitfalls: redundancy and incompleteness.
  • Redundancy in a bad design may result in repeated information and data inconsistency.
  • Incompleteness in a bad design may make certain aspects of the enterprise difficult or impossible to model.
• Avoiding bad designs is insufficient and there are many good designs to choose from.

Design Approaches:

• Entity Relationship Model is covered in this chapter.
  • It models an enterprise as a collection of entities and relationships.
  • An entity is a "thing" or "object" in the enterprise distinguishable from other objects and is described by a set of attributes.
  • A relationship is an association among several entities.
  • Entity Relationship diagrams represent the model diagrammatically..
• Normalization Theory in Chapter 7 serves to formalize what designs are bad, and tests are run to determine if a design is bad.

ER Model

• The ER data model facilitates database design by specifying an enterprise schema that represents the overall logical structure of a database.
• Three basic concepts are used: entity sets, relationship sets, and attributes.
• The ER model has an associated diagrammatic representation, the ER diagram expressing the database's overall logical structure graphically.

Entity Sets:

• An entity is an object that exists and is distinguishable from other objects.
  • Examples: specific person, company, event, plant.
• An entity set is a set of entities of the same type that share the same properties.
  • Examples: set of all persons, companies, trees, holidays.
• An entity is represented by a set of attributes; descriptive properties possessed by all members of an entity set.
  • instructor = (ID, name, salary)
  • course= (course_id, title, credits)
• A subset of the attributes form a primary key of the entity set, uniquely identifying each member of the set.
• Using the primary key lens is helpful to decide what is an entity.

Representing Entity sets in ER Diagram:

• Rectangles graphically represent entity sets.
• Attributes are listed inside the entity rectangle.
• Underlining indicates primary key attributes.

Relationship Sets:

• A relationship is an association among several entities.
  • Example: 44553 (Peltier) advisor 22222 (Einstein)
• A relationship set is a mathematical relation among n ≥ 2 entities, each taken from entity sets.
  • {(e₁, e₂, ..., eₙ) | e₁ ∈ E₁, e₂ ∈ E₂, ..., eₙ ∈ Eₙ}
  • where (e₁, e₂, ..., eₙ) is a relationship.
  • Example: (44553,22222) ∈ advisor

Relationship Sets (Cont.):

• A relationship set is defined to denote the associations between students and instructors who act as their advisors.
• Related entities are connected by a line.
• An attribute can also be associated with a relationship set.
  • The advisor relationship set between entity sets instructor and student may have a date attribute.

Representing Relationship Sets via ER:

• Diamonds represent relationship sets.

Roles:

• Entity sets of a relationship need not be distinct.
  • Each occurrence of an entity set plays a "role” in the relationship
• Labels such as "course_id" and "prereq_id" are called roles.

Degree of a Relationship Set:

• Binary relationship involves two entity sets or degree two.
  • Most relationship sets in a database system are binary.
• Relationships between more than two entity sets are rare and the majority are binary.
  • students work on research projects under the guidance of an instructor.
  • The proj_guide relationship is a ternary relationship between instructor, student, and project

Non-binary Relationship Sets:

• Most relationship sets are binary.
• It's convenient to represent relationships as non-binary on some occasions.
• E-R Diagram shows an example that includes a Ternary Relationship.

Complex Attributes:

• Simple and composite.
• Single-valued and multivalued; e.g., phone_numbers.
• Derived: computed from other attributes; e.g., age, given date_of_birth.
• Domain is the set of permitted values for each attribute.

Composite Attributes:

• Composite attributes allow division into subparts (other attributes).
• The composite attributes example shows name composed of first_name, middle initial and last_name

Representing Complex Attributes in ER Diagram:

• An example represents complex attributes in the instructor entity.
• ID, name, address can be listed as first_name, middle_initial, last_name, street_number, and street_name

Mapping Cardinality Constraints:

• Mapping cardinality constraints express the number of entities to which another entity can be associated via a relationship set.
• This is most useful in describing binary relationship sets.
• The mapping cardinality for a binary relationship set must be one of the following types:
  • One to one
  • One to many
  • Many to one
  • Many to many

Representing Cardinality Constraints in ER Diagram:

• Express cardinality constraints by drawing either a directed line, signifying "one," or an undirected line, signifying “many,” between the relationship set and the entity set.

Total and Partial Participation

• Total participation, indicated by a double line, means every entity in the entity set participates in at least one relationship within the relationship set.
  • Student participation in advisor relation is total when every student must have an associated instructor.
• Partial participation means some entities may not participate in any relationship in the relationship set.
  • Instructor's participation in advisor is partial because not all instructors advise students.

Notation for Expressing More Complex Constraints:

• A line may have an associated minimum and maximum cardinality, shown in the form l..h, where l is the minimum and h the maximum cardinality.
  • A minimum value of 1 indicates total participation.
  • A maximum value of 1 indicates that the entity participates in at most one relationship.
  • A maximum value of * indicates no limit.

Cardinality Constraints on Ternary Relationship:

• At most one arrow out of a ternary (or greater degree) relationship, indicates a cardinality constraint.
• An arrow from proj_guide to instructor indicates each student has at most one guide for a project.
• If there is more than one arrow, there are two ways of defining the meaning.
• Each A entity is associated with a unique entity from B and C.
• Each pair of entities from (A, B) is associated with a unique C entity, and each pair (A, C) is associated with a unique B.
• To avoid confusion, more than one arrow is outlawed.

Primary Key:

• Primary keys specify how entities and relations are distinguished.
• Considering:
  • Entity sets
  • Relationship sets
  • Weak entity sets

Primary key for Entity Sets:

• Individual entities are distinct by definition.
• From a database perspective, the differences must be expressed regarding attributes.
• Attribute values of an entity must uniquely identify the entity
  • No two entities in an entity may have the same value for all attributes
• A key for an entity is a set of attributes to distinguish entities from each other

Primary Key for Relationship Sets:

• The individual primary keys of the entities in the relationship set distinguish the various relationships in a relationship set.
• Let R be a relationship set involving entity sets E1, E2, .. En.
• The primary key consists of the union of the primary keys of entity sets E1, E2, ..En.
• If the relationship set R has attributes a1, a2, ..., am associated with it, then the primary key also includes the attributes a1, a2, ..., am.
• For the relationship set "advisor”, the primary key consists of instructor.ID and student.ID.
• The choice of primary key depends on the mapping cardinality of the relationship set.

Choice of Primary key for Binary Relationship:

• For Many-to-Many relationships: the preceding union of the primary keys is a minimal superkey and is chosen as the primary key.
• For One-to-Many relationships: The primary key of the "Many” side is a minimal superkey and is used as the primary key.
• For Many-to-one relationships: The primary key of the "Many” side is a minimal superkey and is used as the primary key.
• For One-to-one relationships: the primary key of either one of the participating entity sets forms a minimal superkey; either one can be chosen as the primary key.

Weak Entity Sets:

• The section entity is uniquely identified by course_id, semester, year, and sec_id.
• Section entities are related to course entities, represented by the sec_course relationship set between entity sets section and course.
• The information in sec_course duplicates the course_id attribute already present in section.
• One option is to remove sec_course, making the relationship between section and course implicit.

Weak Entity Sets (Cont.):

• Another way stores the attributes: section_id, year, and semester.
  • The section then doesn't have enough attributes to be uniquely identified
• Treat the relationship sec_course as a special relationship that provides information, in this case, the course_id to uniquely identify section entities.
• A weak entity set is one whose existence depends on another entity, called its identifying entity.
• Instead of a primary key, use the identifying entity along with a discriminator to uniquely identify an entity.

Weak Entity Sets (Cont.):

• An entity set that is not a weak entity set is a strong entity set.
• Every weak entity is existence dependent on the identifying entity set and must be associated with an identifying entity.
• The identifying entity set owns the weak entity set that it identifies.
• The relationship associating the weak entity set with the identifying entity set is the identifying relationship.
• A relational schema created eventually has course_id for the set section.

Expressing Weak Entity Sets:

• In E-R diagrams, a weak entity set is depicted via a double rectangle.
• The discriminator of a weak entity set is underlined with a dashed line.
• The relationship set connecting the weak entity set to the identifying strong entity set is depicted by a double diamond.
• The primary key for section includes course_id, sec_id, semester, year.

Redundant Attributes:

• Suppose there are two entity sets.
  • student with attributes: ID, name, tot_cred, dept_name
  • department with attributes: dept_name, building, budget
• Each student has an associated department using the stud_dept relationship set.
• The dept_name attribute in the student replicates information in the relationship and is redundant.
• The attribute needs to be removed, however when converting back to tables, the attribute gets reintroduced.

Reduction to Relation Schemas:

• Entity sets and relationship sets can be expressed uniformly as relation schemas that represent the contents of the database.
• A database conforming to an E-R diagram can be represented by a collection of schemas.
• Each entity and relationship set corresponds to a unique schema, named after the set.
• Each schema has several uniquely named columns, corresponding to attributes.

Representing Entity Sets:

• A strong entity set reduces to a schema with the same attributes:
  • student(ID, name, tot_cred)
• A weak entity set becomes a table with a column for the primary key of the identifying strong entity set
  • section (course_id, sec_id, sem, year)

Representation of Entity Sets with Composite Attributes:

• Composite attributes are flattened out by creating a separate attribute for each component attribute.
  • Given entity instructor with composite attribute name and the component attributes first_name and last_name, the corresponding schema has two attributes name_first_name and name_last_name.
  • Prefixes are omitted if there is no ambiguity; name_first_name could be first_name.
• Ignoring multivalued attributes, the extended instructor is instructor(ID, first_name, middle_initial, last_name, street_number, street_name, apt_number, city, state, zip_code, date_of_birth).

Representation of Entity Sets with Multivalued Attributes:

• A multivalued attribute M of an entity E is represented by a separate schema EM.
• The schema EM has attributes corresponding to the primary key of E and an attribute corresponding to M.
• The multivalued attribute phone_number of instructor is represented by a schema:
  • inst_phone= (ID, phone_number)
• Each value of the multivalued attribute maps to a separate tuple of the relation on schema EM.
• The instructor entity with primary key 22222 and phone numbers 456-7890 and 123-4567 maps to two tuples:
  • (22222, 456-7890) and (22222, 123-4567).

Representing Relationship Sets:

• A many-to-many relationship set is represented as a schema with attributes for the primary keys of the two participating entity sets, and any descriptive attributes of the relationship set.
  • advisor = (s_id, i_id)

Redundancy of Schemas:

• Many-to-one and one-to-many relationship sets that are total on the many-side can be represented by adding an extra attribute to the “many” side, containing the primary key of the "one” side.
  • The inst_dept relationship can be represented without creating a schema and by adding a dept_name attribute to instructor.

Redundancy of Schemas (Cont.):

• For one-to-one relationship sets, either side can act as the "many” side by adding an extra attribute to either of the tables.
• If participation is partial on the "many” side, replacing a schema by an extra attribute in the schema corresponding to the "many" side could result in null values.
• The schema corresponding to a relationship set linking a weak entity set to its identifying strong entity set is redundant.

Extended E-R Features:

• Specialization
• Generalization
• Aggregation

Specialization:

• Specialization refers to designating sub-groupings within an entity set that are distinctive from other entities in the set.
• These sub-groupings become lower-level entity sets that have attributes or participate in relationships that do not apply to the higher-level entity set.
• It's depicted by a triangle component labeled ISA (e.g., instructor “is a” person).
• Attribute inheritance means a lower-level entity set inherits all the attributes and relationship participation of the higher-level entity set to which it is linked.

Specialization Example:

• Specialization can be:
  • Overlapping – employee and student
  • Disjoint – instructor and secretary
• Total and partial

Representing Specialization via Schemas

Method 1

• Form a schema for the higher-level entity. Form schemas for each lower-level entity set, include primary keys of higher-level entity sets and local attributes.
  • person: ID, name, street, city
  • student: ID, tot_cred
  • employee: ID, salary
• Drawbacks include getting information about, which may require accessing two relations.

Method 2

• Form a schema for each entity set with all local and inherited attributes
  • person: ID, name, street, city
  • student: ID, name, street, city, tot_cred
  • employee: ID, name, street, city, salary
• Drawbacks include name, street, and city stored redundantly for people who are both students and employees

Generalization:

• Generalization refers to a bottom-up design process that combines a number of entity sets that share the same features into a higher-level entity set.
• Specialization and generalization are simple inversions of each other, represented similarly in an E-R diagram, and used interchangeably.

Completeness constraint:

• Specifies whether an entity in the higher-level set belongs to at least one lower level set within the generalization.
  • Total completeness means an entity must belong to one of the lower-level entity sets.
  • Partial completeness means need not belong to one of the lower-level entity sets.

Completeness Constraint (Cont.):

• Partial generalization is the default.
• Total generalization in an ER diagram by adding "total" and drawing a dashed line from the keyword to the corresponding hollow arrow-head.
• all student entities must be either graduate or undergraduate student.

Aggregation:

• Aggregation considers the ternary proj_guide relationship.
• Supposing evaluations are desired for students by a guide on a project.
• Evaluates the eval_for and proj_guide overlapping relationship that is typically redundant.
• Eliminating redundancy can be done via aggregation
  • Treat relationships as an abstract entity.
  • It enables relationships between relationships.
  • Abstraction is used with a relationship to make a new entity.

Aggregation (Cont.):

• Eliminating redundancy via aggregation (without introducing redundancy)
  • A student is guided by a particular instructor on a particular project.
  • A student, instructor, project combination may have an associated evaluation.

Reduction to Relational Schemas:

• To represent aggregation, create a schema containing
  • Primary key of the aggregated relationship
  • The primary key of the associated entity set
  • Any descriptive attributes
• The example schema eval_for includes s_ID, project_id, i_ID, evaluation_id. The schema proj_guide is redundant.

Design Issues:

• Common Mistakes in E-R Diagrams
• Entities vs. Attributes
• Entities vs. Relationship sets
• Binary Vs. Non-Binary Relationships

Common Mistakes in E-R Diagrams:

• Incorrect Use Of Attributes.
• Erroneous Use Of Relationship Attributes.

Entities vs. Attributes:

• Using entity sets vs. attributes and considering the use of phone as an entity allows extra information about phone numbers and multiple numbers.

Entities vs Relationship Sets:

• Possible to designate a relationship action that describes what occurs between two entities.
• For relationship attributes for example, attribute date as attribute of advisor or as attribute of student

Binary vs. Non-Binary Relationships:

• It is possible to replace any non-binary (n-ary, for n > 2) relationship set by several distinct binary relationship sets.
• Some relationships seem non-binary but can be represented using binary (relationship between child to mother/father)
• Some other cases are naturally non-binary

Converting Non-Binary Relationships to Binary Form:

• Any non-binary relationship can be represented using binary relationships by creating an artificial entity set.
  • Replace R between entity sets A, B and C by an entity set E, and three relationship sets.
  • RA, relating E and A.
  • RB, relating E and B.
  • RC, relating E and C.
  • Create an identifying attribute for E and add any attributes of R to E.

Converting Non-Binary Relationships (Cont.):

• Also need to translate constraints
• Translating all constraints may not be possible
• There may be instances in the translated schema that cannot correspond to any instance of R
• The use of an attribute or entity set to represent an object. The use of a ternary relationship versus a pair of binary relationships.

E-R Design Decisions:

• The use of an attribute or entity set to represent an object. Whether a real-world concept is best expressed by an entity set or a relationship set.
• The use of a ternary relationship versus a pair of binary relationships.
• The use of a strong or weak entity sei.
• The use of specialization/generalization – contributes to modularity in the design.
• The use of aggregation (can treat the aggregate entity set as a single unit without concern for detail)

Alternative ER Notations:

Chen, IDEF1X Chen: weak entity set, generalization

UML:

• UML is a Unified Modeling Language.
• It visually models different aspects of a software system.
• UML Class Diagrams correspond to E-R Diagrams, with some differences.

Other Aspects of Database Design:

• Functional Requirements
• Data Flow, Workflow
• Schema Evolution

Understanding derived attributes is crucial in ER modeling. A one-to-one cardinality constraint ensures each entity in one set relates to exactly one in another. Distinguish single-valued from multi-valued and composite attributes.