Entity Relationship Modeling and Normalization

What You'll Learn This Week

• Introduction to the course
• Background Materials
• Review of Entity-Relationship Model
  • Set of E-R modeling constructs
  • Entities
  • Attributes
  • Identifiers
  • Relationships
• E-R Diagrams
  • Variation One - What the Kronke book uses
  • Variation Two - Chen notation as used in the Elmasri/Navathe Textbook
  • Variation Three - Oracle Designer CASE
  • Variation Four - Visible Analyst
  • Variation Five - Sybase PowerDesigner
  • Variation Six - Popkin System Architect
  • Variation Seven - Popkin System Architect - UML Notation
  • Displaying Attributes
  • Weak Entities and ID Dependent Entities
  • Subtype Entities
• Entity to Relation Conversion

Introduction to the course

• Syllabus
• Computer Labs and Software
• Course Logistics

Background Material

Our goal is to provide information for the purposes of decision making in business. The database is one way to provide such information.

However, we must organize and develop a database in a structured fashion to meet the needs of an organization and reflect the way it operates.

Recall the database design process we follow:

1. Gather user/business requirements.
2. Develop the Entity Relationship (E-R) Model (shown as an E-R Diagram) based on the user/business requirements. The E-R model is the conceptual model of the database.
3. Convert the E-R Model to a set of relations in the relational model. We call this the Logical model
4. Normalize the relations to remove any anomalies.
5. Implement the database schema by creating a table for each normalized relation. We call this the Physical model
6. Develop applications (forms, reports, queries, scripts, procedures) that work with these tables.

Note that in the second step, we may also develop additional models such as data flow and functional models.

Review of Entity Relationship Model

Elmasri/Navathe 3rd ed.	Kroenke 7th Ed.	McFadden 5th ed.	Connolly/Begg 3rd ed.
Chapters 3 and 4	Chapter 3	Chapters 3 and 4	2, 10, 11, 12

• Entity Relationship Modeling: A Set of constructs used to interpret, specify and document data requirements for database processing systems.
• E-R Models are Conceptual Models of the system. They can not be directly implemented in a database.
• Many variations of E-R Modeling used in practice.
• Mainly differences in notation, symbols used to represent the constructs.

E-R Modeling Constructs

• E-R Modeling Constructs are: Entity, Relationship, Attributes, Identifiers

• It is important to get used to this terminology and to be able to use it at the appropriate time. For example, in the ER Model, we do not refer to tables. Here we call them entities.

• Entity: Some identifiable object relevant to the system being built. Examples of Entities are:
  EMPLOYEE
  CUSTOMER
  ORGANIZATION
  PART
  INGREDIENT
  PURCHASE ORDER
  CUSTOMER ORDER
  PRODUCT
  

  An instance of an entity is like a specific example:
  Bill Gates is an Employee of Microsoft
  SPAM is a Product
  Greenpeace is an Organization

• Attribute: A characteristic of an Entity. Properties used to distinguish one entity instance from another. Attributes of entity EMPLOYEE might include:
  EmployeeID
  Social Security Number
  First Name
  Last Name
  Street Address
  City
  State
  ZipCode
  Date Hired
  Health Benefits Plan
  

• Identifier: A special attribute used to identify a specific instance of an entity.
  
  • Typically we look for unique identifiers:
  • Social Security Number uniquely identifies an EMPLOYEE
  • CustomerID uniquely identifies a CUSTOMER
  • We can also use two attributes to indicate an identifier: ORDER_NUMBER and LINE_ITEM uniquely identify an item on an order.

• Relationship: An association between two entities.
  
  • A CUSTOMER places a CUSTOMER ORDER
    An EMPLOYEE takes a CUSTOMER ORDER
    A STUDENT enrolls in a COURSE
    A COURSE is taught by a FACULTY MEMBER
    

  • Relationships are typically given names.

  • A relationship can include one or more entities
  • The degree of a relationship is the number of Entities that participate in the relationship.
  • Relationships of degree 2 are called binary relationships. Most relationships in databases are binary.

  • Relationship Cardinality refers to the number of entity instances involved in the relationship. For example:
    one CUSTOMER may place many CUSTOMER ORDERS
    many STUDENTS may sign up for many CLASSES
    one EMPLOYEE receives one PAYCHECK

    1:N	"One to Many"
    N:M	"Many to Many"
    1:1	"One to One"

    Beware of 1:1 relationships. The two entities involved might be coalesced into one. Also called HAS-A relationship.

    Beware of N:M relationships. Typically split these into two 1:N relationships with an intersection entity.

  • Participation of instances in a relationship may be mandatory or optional.
  • For example,
    one CUSTOMER may place many CUSTOMER ORDERS
    one EMPLOYEE must fill out one or more PAY SHEETS
  • This is also called "minimal cardinality" or the "optionality" of a relationship.

E-R Diagrams

• The most common way to represent the E-R constructs is by using a diagram

• There are a wide variety of notations for E-R Diagrams. Most of the differences concern how relationships are specified and how attributes are shown.
• In almost all variations, entities are depicted as rectangles with either pointed or rounded corners. The entity name appears inside.
• Relationships can be displayed as diamonds (see below) or can be simply line segments between two entities.

• For Relationships, need to convey: Relationship name, degree, cardinality, optionality (minimal cardinality)

• Here we will give examples several variations. The point is not that you memorize all of these variations. Pick one you are most comfortable with and use it consistently.

Kronke textbook Notation (NOTE: We not longer use this notation so you can safely ignore this example) Relationship Name: Displayed just outside of the relationship diamond. Degree: Shown by line segments between the relationship diamond and 2 or more entities. Cardinality: Displayed inside the relationship diamond. Optionality: Mandatory participation indicated by an intersecting hash mark made perpendicular to the relationship line segment. Optional participation indicated by a 0 intersecting the relationship line segment. For this diagram: An ORDER must be placed by one and only one CUSTOMER. A CUSTOMER may place zero or more ORDERS. An ORDER may have zero or more ITEMS. An ITEM must have one and only one ORDER. Note: This notation is rarely used if at all since the notations are essentially backwards from all other notations. Also, when written vertically, the cardinalities become ambiguous.	Chen notation as used in the Elmasri/Navathe Textbook Relationship Name: Displayed just inside the relationship diamond. Degree: Shown by line segments between the relationship diamond and 2 or more entities. Cardinality: Displayed between the participating entity and the relationship diamond next to the relationship line. Split up the cardinality. Optionality: Mandatory participation indicated by double relationship line Optional participation indicated by a single relationship line. This is also called the "Chen notation" after the author who first proposed it.
Oracle Designer CASE Notation Also called the "Information Engineering" notataion. In Oracle Corporation's Designer, relationships are expressed in a rigid sentence format. For example: An ORDER must be placed by one and only one CUSTOMER. The "be" is mandatory making the verb difficult to get right. Relationship diamonds are not used. Relationship Names: Are expressed as a verb phrase starting with "be". There are two phrases, one for each direction of the relationship. This phrase is then written along the line segments for the relationship. Degree: Shown by line segments between any two entities. As such, ternary (3 way) relationships as described in the Kronke and Elmasri/Navathe textbooks (Chen notation) can not exist. Cardinality: Single participation ("1" in the previous example) is indicated by a single line segment. Multiple participation ("N") is indicated by crow's feet Optionality: Mandatory participation is indicated by a solid relationship line segment. Optional participation is indicated by a dotted line segment. One ORDER must be placed by one and only one CUSTOMER. One CUSTOMER may be placing zero or more ORDERS. One ORDER may be made up of zero or more ITEMS. One ITEM must be an item on one and only one ORDER. There are a set of tools within the Oracle CASE environment that can print these "relationship sentences".	Visible Analyst Notation Visible Analyst Workbench (VAW) uses the rounded box to show an Attributive Entity - one that depends on the existence of a fundamental entity (noted by just the rectangle). The relationships use the following symbols: For cardinality, the crow's feet are used to show a "Many" side of a relationship. A single line indicates a "One" side of the relationship. Optional participation is shown with an open circle. Thus in the above diagram, a Customer May place one or more Orders. Mandatory participation is shown with two hash marks. Thus in the above diagram, an Order Must be placed by one and only one Customer.
Sybase PowerDesigner Notation Single hash mark indicates mandatory participation Hollow circle indicates optional participation Crows-foot indicates Many while single line indicates One Cardinalities can also be shown next to the relationship anchors such as 0..n	Popkin System Architect - Crow's Feet Notation Two hash marks indicates mandatory participation Hollow circle indicates optional participation Crows-foot indicates Many while single line indicates One Dashed line indicates non-associative relationship Solid line indicates associative relationship (e.g., that the Identifier of OrderHeader should be part of the composite identifier of Order Items)
Popkin System Architect - UML Notation The Unified Modeling Language (UML) has gained in popularity UML draws upon several different Object Oriented modeling techniques developed in the 1980's and 1990's. Learn more at http://www.uml.org/ In UML notation, entites are refered to as classes or object types and are represented as rectangles. Note the naming convension used: Customer is a member of the class Customers Associations (relationships) can be binary, ternary or higher (n-ary Associations are shown by connecting lines with a single term as a label Cardinalities can be displayed (as above) e.g., 1 indicates one and only one 0..* indicates a minimum of 0 and a maximum of Many Note that only relationships of degree 1 and degree 2 are supported in UML (no ternary relationships) The Connolly/Begg textbook 3rd edition now uses UML throughout.

Displaying Attributes

• Technically, an Entity-Relationship diagram should show only entities and their relationships.
• Consider: Entity-Relationship-Attribute (ERA) model.
• Two main ways to display attributes associated with an entity.
  1. Attributes appear in ovals attached to the entity. Gets messy.

     

  2. List attributes inside of the entity box.

     

• Note that some CASE and drawing tools include additional information in the entity box such as the primary keys. Example from Popkin System Architect CASE tool:

  

• Two additional important Notes:
  1. The "Relationships" screen in MS Access is not an ER modeling tool. This screen represents a physical model of the database, not a conceptual one.
  2. Be aware that many CASE tools automaticlaly display the foreign keys in the entities on the many side of one to many relationships.
     This is not correct ER modeling technique as such propegation of foreign keys should be a result of the conversion to relational model and not present at the conceptual modeling stage.

Weak Entities and ID Dependent Entities

• Vague definition: Weak Entity: An entity that depends on another for its existence.
  
• Elmasri/Navathe defiinition: An Entity with no identifying attributes

• ID Dependent Entity: A weak entity that includes the identifier of the related strong entity.
  The weak entity depends upon the identifier from the strong entity for its existence.

• Examples of strong entities:
  People, Employees, Customers, Clients, Vendors, Students
  Products, Services, Parts, Resources, Materials

• Weak entities are typically shown with a double-box.

Subtype Entities

• Attributes of two or more Entities may overlap significantly but not completely.

• Consider:
  Phone Call (Source#, Destination#, Time of day, Duration)
  LongDistance Call (Source#, Destination#, Time of day, Duration, Long distance Carrier)
  Cell Phone Call (Source#, Destination#, Time of day, LandTime, AirTime)
  

• One approach would be to put all of the attributes into a single entity.
  

  
  

• Second approach, put common attributes into a parent or supertype entity and then have 3 subtype entities.

• Relationship is called an IS-A relationship.
  

Subtype Entity Notations

• As with ER models, there are a number of different notations for super/subtype relationships
• The following diagram uses the Oracle Designer symbols for Supertype/Subtype.

  

• Below is the same diagram drawn using E-R symbols from the Elmasri/Navathe book.

  
  

  The d in the circle indicates the subtype entity is distinct. Only one subtype entity can participate in an instance.

  As before, the double line between the Call entity and the d in the circle indicates the relationship is mandatory.

• In UML, we can use the superclass/subclass relationships (inheritence) as shown below:

  

Review of the Relational Model

Elmasri/Navathe 3ed ed.	Kroenke 7th ed.	McFadden 5th ed.	Connolly/Begg 3rd ed.
Chapter 7	Chapter 9	Chapter 6	3, 13

• Recall, the Relational Model consists of the elements: relations, which are made up of attributes.
• A relation is a set of attributes with values for each attribute such that:
  1. Each attribute value must be a single value only (atomic).
  2. All values for a given attribute must be of the same type (or domain).
  3. Each attribute name must be unique.
  4. The order of attributes is insignificant
  5. No two rows (tuples) in a relation can be identical.
  6. The order of the rows (tuples) is insignificant.
• Domain: The set of allowable values an attribute may take. Also includes the data type and size/length.
• A Key in a relation is a set of attributes that have unique values across all tuples. There may be several candidate keys in a relation.
• A Primary key is a key that uniquely identifies a tuple.
• A Foreign key is a set of attributes that act as a primary key in R1 (with their associated domains) but also appear in another relation, R2.
• Relational integrity:
  1. Entity Integrity: A primary key may not contain NULL values.
  2. Referential integrity: A relationship between two relations used to maintain consistency of values. The Foreign key is a mechanism to enforce referential integrity.

Entity to Relation Conversion

• For a majority of ER Models, entities and weak entities convert easily into relations.

• Entities - In general, each entity will be converted directly to a relation. The attributes of the entity become the attributes of the Relation.

  The Identifier of the Entity becomes a Key of the Relation.
  (not primary key - just "key")

  
  CUSTOMER (CustID (key), Name, Address, Phone)

• Weak Entities - If a weak entity is not ID Dependent, then treat it like any other entity - Application must enforce referential integrity.
  

  If entity is ID Dependent, then the parent relation's key (Identifier) is copied into the dependent relation and is combined with the dependent relation's identifier to form a composite key.
  

  Chen Notation	UML Notation

  ORDER (OrderNum (key), OrderDate, SalesPerson)
  ORDERITEMS (OrderNum (key)(fk) , ItemNum (key), PartNum, Quantity, Cost)
  

  In the above example, in the ORDERITEMS Relation: OrderNum is the Foreign Key and OrderNum plus ItemNum is the Composite Key.
  In the ORDER Relation: OrderNum is the Key.

Representing Relationships

• 1:1 Relationships. The key of one relation is stored in the second relation.
  Look at example queries to determine which key is queried most often.

• 1:N Relationships.
  Parent - Relation on the "1" side.
  Child - Relation on the "Many" side.
• Represent each Entity as a relation.
  Copy the key of the parent into the child relation.
  

  Chen Notation	UML Notation

  CUSTOMER (CustomerID (key), Name, Address, ...)
  ORDER (OrderNum (key), OrderDate, SalesPerson, CustomerID (fk))
  
  

• M:N Relationships. Many to Many relationships can not be directly implemented in relations.
• Solution: Introduce a third Intersection relation and copy keys from original two relations.
  

  Chen Notation	UML Notation

  SUPPLIER (SupplierID (key), FirmName, Address, ...)
  COMPONENT (CompID (key), Description, ...)
  SUPPLIER_COMPONENT (SupplierID (key), CompID (key))

• Note that this can also be shown in the ER diagram. Also, look for potential added attributes in the intersection relation.

Recursive Relationships

• Consider assembling an automobile - a collection of basic parts are combined together to make a complete car.

• In this case, a part or component might be made up of one or more other parts. This forms a recursive 1:N relationship.
  

  Chen Notation	UML Notation

• We can implement this directly by including another copy of the key in the relation.
  PART (Part_ID (key), Parent_Part_ID (fk), Description)

• Here are some example data:
  

  Part_ID	Parent_Part_ID	Description
  1000	null	Complete Car
  200	1000	Engine
  500	1000	Body
  510	500	Doors
  520	500	Hood
  530	500	Quarter Panels
  540	500	Trunk
  550	500	Roof
  512	510	Front Passenger Door
  514	510	Front Driver's Door
  516	510	Back Passenger Door
  518	510	Back Driver's Door etc.

• This forms a Tree structure:
  

      Complete Car                            1000
          Engine                               200
          Body                                 500
             Doors                             510
                 Front Passenger Door          512
                 Front Driver's Door           514
                 Back Passenger Door           516
                 Back Driver's Door            518
             Hood                              520
             Quarter Panels                    530
             Trunk                             540
             Roof                              550
  

• null = No Value present
• Other kinds of recursive relationships:
  1:1 CUSTOMER is referred by one and only one other CUSTOMER
  N:M STUDENT tutors one or more other STUDENTS - Also, that STUDENT can be tutored by one more other STUDENTS.
  

  Chen Notation	UML Notation	Crow's Foot Notation

  STUDENT (StudentID (key), Name, Address, ...)
  STUDENT_TUTOR (StudentID (key), Tutored_StudentID (key))
  

• Example Data:
  STUDENT
  

  StudentID (key)	Name	Address
  101	B. Smith	1234 Smith St.
  202	A. Green	12 Grant St.
  303	D. Jones	98 Short St.
  404	P. Ewing	999 Tall St.

  STUDENT_TUTOR
  

  StudentID (key)	StudentTutoredID (key)
  101	202
  404	202
  202	303
  404	303

Ternary Relationships

• Ternary relationships are likely ambiguous.
• It is best if we can represent a ternary relationship as two binary relationships between the three entities.

• If we can re-write the ternary relationship as several binary relationships, then the above steps can be used to convert the entities into relations.

  Chen Notation

• One Example: ORDER, CUSTOMER, SALESPERSON becomes:
  CUSTOMER (CustomerID (key), Name, Address...)
  SALESPERSON (SpId (key), SpName, SpDepartment, ...)
  ORDER (OrderNum (key), OrderDate, CustomerID (fk), SpId (fk))
  

  This represents the business model where a salesperson is assigned to specific customers.

• Another Example: ORDER, CUSTOMER, SALESPERSON becomes:
  CUSTOMER (CustomerID (key), Name, Address..., SpId (fk))
  SALESPERSON (SpId (key), SpName, SpDepartment, ...)
  ORDER (OrderNum (key), OrderDate, CustomerID (fk))
  

  This represents the business model where a salesperson is assigned to individual orders.

• Note that with other notations such as Crow's feet and UML, one must write these as two binary (1 to many) relationships. This removes the ambiguity of the ternary relationship.

IS-A Relationships

• Recall that some entities may have subtypes associated with them.

  
  

• Strategy is:
  1. Convert the supertype entity directly into a relation using only those attributes in the supertype - note the key.
  2. Convert each of the subtype entities into relations - also only with the attributes they contain.
  3. Copy the key for the supertype entity into each of the subtypes.

• So our example becomes:
  CUSTOMER (Customer_ID (key), Name, Address, ...)
  CALL (Call_Identifier (key), Customer_Id (fk), Source_Number, Destination_Number, TimeOfDay)
  REGULAR_CALL (Call_Identifier (key), Duration)
  LONG_DISTANCE (Call_Identifier (key), Duration, LongDistanceCarrier)
  CELL_CALL (Call_Identifier (key), Air_Time, Land_Time)