​

​

CS 220P

Conceptual Modeling of Data�(Lecture 3)

Prof. Sharad Mehrotra

Information and Computer Science Department, University of California at Irvine

1

Last Class….underneath the hood

File system

Buffer manager

record-oriented file system

indexing

query optimization

query processor

query optimization

transactions

..

…

2

Next few weeks…

Programming with databases

• conceptual modeling - this week
• relational model
• SQL

​

3

Database Design Process

4

high level specs

​

conceptual schema

logical schema

(in DBMS model)

miniworld

​

conceptual design

​

logical design

​

physical design

functional analysis

​

​

application design

​

​

transaction implementation

Data requirements

functional requirements

​

application programs

Physical schema

Requirement Analysis

Functional Design

Database Design

Database design often starts by specifying a schema in ER diagrams.

ER Diagrams

• A simple pictorial model to specify the structure and semantics of data.

​

• Contains a minimal number of powerful modeling concepts
• Entities, relationships

​

• ER diagrams are close to natural languages but are formal
• No ambiguity in specification

​

5

Entities and Entity Sets

• Entities
• Nouns, ‘things’, in the world.
• E.g., students, courses, employees, departments, flights, patients, …�
• Attributes
• Properties of entities.
• E.g., course name, deptname, departure time, age, room#, ... �
• Entity set
• a set of entities that have the same attributes.
• In OO terminology, an entity set is similar to a class, and an entity similar to an instance

6

Attributes

• Single-valued vs multi-valued:
• Hobbies of a person could be multi-valued.
• Salary of employee is single-valued.�
• Atomic vs composite:
• Age of a person is atomic.
• Address of a person could be composite. �
• Stored vs derived:
• Derived attributes are those that can be derived from other attributes or entities, e.g., age can be derived from date of birth.
• All other attributes are stored attributes.

7

Relationships

• Relationship:
• Association between multiple entities.
• Relationship Set:
• Set of relationships over the same entity sets.
• Binary, Ternary, 4-nary, … relationship sets

​

8

259 10000

245 2400

364 200000

305 20000

customer

account

Cust-Account Relationship set

62900 main austin

62901 north urbana

Sam

Pat

Visualizing ER Relationships as a Table

9

Relationship Set Corresponding to the Relationship Cust-Account

Row in the table represents the pair of entities participating in the relationship

ER Diagram -- graphical representation of ER schema

10

cust_acct

opening date

• Entity set -- rectangles;
• Attributes – listed under the entity;
• Parentheses -- derived attribute; e.g. age ()
• Square brackets -- multivalued attribute; e.g. [ phone number ]
• Relationship set -- diamonds;
• Lines connect the respective relationship set with entity sets;
• Relationship sets may have 1 or many attributes associated with them -- known as relationship attributes.

​

Roles in a Relationship

• The function that an entity plays in a relationship is called its role.
• Roles are normally not explicitly specified unless the meaning of the relationship needs clarification
• Roles needed when entity set is related to itself via a relationship.

11

employee

works for

Manager

Employee

Constraints on Entity Sets

• Key Constraint:
• With each entity set, a notion of a key can be associated.
• A key is an attribute (or set of attributes) that uniquely identify an entity in an entity set.
• Examples:
• Designer may specify that {ssno} is a key for the entity set customer with attributes {ssno, name, address}
• Likewise, {Name, Address} taken together might also be a key, if two people with the same name cannot live at the same address.
• Denoted in ER diagram by underlining the attributes that form a key
• Multiple keys may exist in which case one chosen as primary key and underlined. Other keys called secondary keys either not indicated or listed in a side comment attached to the diagram.

12

Constraints on Entity Sets (cont.)

• Domain constraint:
• with each simple attribute a domain is associated. The value of the attribute for each entity is constrained to be in the domain.

​

13

Cardinality Constraints on Relationship Sets

• Consider binary relationship set R between entity sets A and B:
• Many to Many (unconstrained) : An entity in A can be associated with many entities in B, and an entity in B can be associated with many entities in A.
• A customer may have many bank accounts. Accounts may be joint between multiple customers.
• Many to One: An entity in A is associated with at most one entity in B, an entity in B can be associated with many entities in A.
• an employee works in a single department but a department consists of many employees.

14

Cardinality Constraints on Relationship Sets (cont.)

• One to one: an entity in A is associated with at most one entity in B, and an entity in B is associated with at most one entity in A.
• an employee has only one spouse in a married-to relationship.

​

15

Multiplicity of Relationships

16

Many-to-one

One-to-one

Many-to-many

Multiplicity of relationship in ER diagram represented by an arrow pointing to “one”

Many to Many Relationship

• Multiple customers can share an account
• A customer may have many accounts.

17

customer

cust_acct

account

opening date

legal

legal

Many to One Relationship

• Multiple customers can share an account but one customer can have only one account.

18

Illegal

legal

customer

custacct

account

opening date

Relationship Attribute in a Many to One Relationship

• In a Many-to-One relationship, relationship attributes can be repositioned to the entity set on the many side.

19

customer

custacct

account

opening date

custacct

account

Customer

ssn

name

street

city

opening-date

One to One Relationship

• One customer can have One account.
• One account can be owned by One customer.
• Relationship attributes can be shifted to either of the entity sets.

20

Illegal

Illegal

Legal

customer

custacct

account

opening date

Other notations for Cardinality constraints

• Many-to-many denoted as N-M;
• If M = 1, then it is Many to one; If N= 1, then it is 1 to Many, if both are 1, then 1-1

21

customer

custacct

account

opening date

N

M

Participation Constraints

• Participation of an entity set A in the relationship set R1 can be total.
• Each entity in entity set A is constrained to be related to other entities via relationship R1.
• Examples:
• Participation of entity set employee in the relationship belongs-to with the entity set department may be total.
• Each employee must belong to at least one department.

22

Participation Constraints

• Total participation is also called existential dependency.

​

• If an entity does not have a total participation in a relationship, it is said to have a partial participation.

​

• In ER diagram, total participation represented using a double line between the relationship and entity set that totally participates in the relationship.

23

Example

• Keys: ss#, loanid, branchid
• Cardinality constraint: each loan belongs to a single branch
• Participation constraints:
• Each customer must be a customer of at least one branch
• Each loan must belong to some branch

24

borrower

Belongs-to

Customer-of

Weak Entity Sets

• Entity sets that do not have sufficient attributes to form a key are called weak entity sets.

​

• A weak entity set existentially depend upon (one or more) strong entity sets via a many-to-one relationship from whom they derive their key.

​

• A weak entity set may have a discriminator (or a partial key) that distinguish between weak entities related to the same strong entity.

​

• key of weak entity set = Key of owner entity set(s) + discriminator

25

Weak Entity Sets (cont.)

• Transaction is a weak entity set related to accounts via log relationship.
• Trans# distinguish different transactions on same account

26

cust_acct

opening date

log

A Chain of Weak Entity Sets

• Names of states are unique and form the key.
• Names of city are unique only within a state (e.g., 24 Springfield’s within the 50 states).
• Names of streets are unique within a city. Multiple cities could have streets with the same name.

​

27

city

state

street

Located in

Example illustrating that a weak entity set might itself participate as owner in an identifying relationship with another weak entity set.

Located in

A Weak Entity Set with Multiple Owner Entity Sets

• Reviewers review movies and assign a rating -- thumb up/thumbs down.
• Review is a weak entity set whose owner sets correspond to both the movie and the reviewer entity sets.
• Key for the review entity set = key of movie + key of reviewer

28

Multiway Relationships

• Usually binary relationships (connecting two E.S.) suffice.
• However, there are some cases where three or more E.S. must be connected by one relationship.
• Similar to binary relationship, cardinality and participation constraints defined over multiway relationships

29

CAB Relationship Set

CAB

Cardinality Constraint over Multiway Relationships

• Interpretation:
• Each pair of customer and account determine the branch (that is, have a single branch related to them).

30

Many to Many to 1 relationship

Illegal: Megan has account 1001 at 2 branches

Legal

CAB

Cardinality Constraint over Multiway Relationships

• Interpretation:
• Each (customer, branch) related to a single account
• Each (customer, account) pair related to a single branch

31

Many to 1 to 1 relationship

Illegal: Megan has 2 accounts in Tokyo Branch

Legal

CAB

Cardinality Constraint over Multiway Relationships

• Interpretation:
• Each (customer, branch) related to a single account
• Each (customer, account) pair related to a single branch
• Each (branch, account) pair can have single customer

32

1 to 1 to 1 relationship

Illegal: Both John and Megan have account 1002 in Tokyo Branch

Legal

CAB

Limitations of the Basic ER Model Studied So Far

• Lots of times an entity set has members that have special properties not associated with all the members of the entity set.

​

• E.g., the set of checking accounts and savings accounts are a subset of the set of accounts. Checking has a overdraft amount, and savings has a interest-rate.

33

How do we represent the above in ER model?

Possible Solutions

• Associate an attribute -- account-type with the accounts entity set
• different attributes may be associated with the account depending on its type (e.g., checking: overdraft amount, savings: interest rate)
• depending upon its type, savings and checking accounts may participate in different relationships.
• Create multiple entity sets: checking, savings, and accounts with : 1-1 relationships between checking and accounts & 1-1 between savings and accounts
• Not intuitive: checking and savings are represented as entities different from accounts, even though they are accounts
• Redundancy of information: info about accounts represented both in checking / savings as well as account entity set
• Potential Errors: Same account could be erroneously associated with both checking as well as savings.

34

Subclass/Superclass Relationships

• Savings and checking are subclasses of the account entity set.
• account is a superclass of savings and checking entity sets.
• An entity in a subclass has to belong to superclass as well -- that is, every savings account is also an account. Similarly every checking account is also an account
• Attribute Inheritance: subclasses inherit all the attributes of the superclass. Similarly, subclasses inherit all relationships in which the superclass participates

​

35

IS A

Types of Class/Subclass Relationships

• Disjoint vs Overlapping:
• If the subclasses of the entity set do not overlap then it is disjoint (denoted by a ‘d’ next to ISA triangle).
• Else, overlapping (denoted by a ‘o’ next to ISA triangle)
• Total vs Partial:
• If an entity in a superclass belongs to at least one of the subclasses, then total. (denoted by a double line from superclass to ISA triangle)
• Else, partial
• Key of entity set corresponding to the subclass is the same as the key for the superclass.

36

Superclass/Subclass Lattice

• Class/Subclass relationships might form a hierarchy (tree) or a lattice

​

37

person

employee

alumnus

student

staff

faculty

student

assistant

grad

undergrad

RA

TA

d

o

ISA

ISA

ISA

IS A

d

o

Overlapping means that a person can be both a employee and an alumnus for example

ISA

Superclass/Subclass Lattice

• Class/Subclass relationships might form a hierarchy (tree) or a lattice

​

38

person

employee

alumnus

student

staff

faculty

student

assistant

grad

undergrad

RA

TA

d

o

ISA

ISA

ISA

IS A

d

o

ISA

Disjoint means that employees either are staff, or faculty, or student assistants but cannot more than 1. Also, total participation means that every employee is either one of these three

Superclass/Subclass Lattice

• Class/Subclass relationships might form a hierarchy (tree) or a lattice

​

39

person

employee

alumnus

student

staff

faculty

student

assistant

grad

undergrad

RA

TA

d

o

ISA

ISA

ISA

IS A

d

o

ISA

If we have only a single subclass we can draw or not draw a is-a relationship. It is implied.

Superclass/Subclass Lattice

40

person

employee

alumnus

student

staff

faculty

student

assistant

grad

undergrad

RA

TA

d

o

ISA

ISA

ISA

IS A

d

o

ISA

Student class is classified based on two different is-a relationships.

They are classified as grad and undergrad. And the second classification is that some of the students are also assistants. Note that student assistants can be either grad or undergrad.

Superclass/Subclass Lattice

41

person

employee

alumnus

student

staff

faculty

student

assistant

grad

undergrad

RA

TA

d

o

ISA

ISA

ISA

IS A

d

o

ISA

Student assistant class inherits its attributes and relationships from both the employee and also from the student classes. This is multiple inheritance.

Multiple Inheritance

• In a class/subclass relationship, the subclass inherits all its attributes from the superclass.
• If a subclass has 2 or more superclasses, then subclass inherits from all the superclasses (multiple inheritance).
• How should conflicts be resolved?
• Example:
• Employee Entity Set: with an attribute country denoting the country of citizenship
• Asians Entity Set: with an attribute country denoting the country from which a particular person originated.
• Asian_Employee Entity set is a subclass of both Employee and Asians. However, what does country attribute of the Asian_Employee correspond to.
• ER model mute on multiple inheritance.

42

Superclass/Subclass Lattice

43

person

employee

alumnus

student

staff

faculty

student

assistant

grad

undergrad

RA

TA

d

o

ISA

ISA

ISA

IS A

d

o

ISA

Question: Could person classification into employee, alumnus, and students have been a disjoint ?

Limitations of ER Model

• We wish to represent that an employee works on a specific project possibly using multiple tools

44

employee

project

tools

works_using

employee

project

tools

work

using

relationships among relationships not permitted in ER!

incorrect since it requires each project to use tools

Aggregation

• Treat the relationship set work and the entity sets employee and projects as a higher level entity set-- an aggregate entity set
• Permit relationships between aggregate entity sets and other entity sets

45

employee

project

tools

works

using

N

N

Representation without Aggregation in ER Model

46

employee

project

tools

works

using

employee

project

tools

EP

redundant relationship!

works

using

awkward schema!

Review of ER Model

• Basic Model:
• Entities : strong, weak.
• Attributes associated with entity sets and relationships.
• Relationships: binary, ternary, ...
• Role of entity sets in a relationship.
• Constraints on entity set: domain constraints, key constraint
• Constraint on relationships: cardinality -- 1-1, 1-N, M-N, participation (also called existential) --total vs partial.
• Extended Model:
• Notion of superclass and subclass.
• Superclass/subclass relationships: disjoint vs overlapping, total rs partial.
• Notion of aggregation.

47

Database Design

​

• Two key considerations:
• Redundancy: A good design should not represent the same information redundantly in several places.
• Redundant representation of information may lead to data inconsistency among the various copies of information
• Incompleteness: a good design should as completely model the domain semantics as possible
• Incomplete designs may make it impossible to certain applications/queries since information to implement them is not stored.
• Not modeling certain constraints may result in inconsistency in databases

​

​

48

Schema Design Issues

• Observation: there may be multiple ER schemas describing the same target database or miniworld.
• Decisions that need to be made:
• whether to use an attribute or entity set to represent an object.
• whether to model a concept as a relationship or an entity set.
• whether to use ternary relationship or a set of binary ones.
• whether to use a strong entity set or a weak entity set.
• whether using generalization/specializations is appropriate.
• whether using aggregates is appropriate.
• There are no straightforward answers to these questions.
• No two design teams will come up with the same design.
• However, there are some simple design principles that should be followed during ER design.

49

E/R Design Principles

• Schemas should not change often. So store frequently changing information as instances.
• currently each project consists of 10 members. Since later projects may have more or less employees, do not hardcode the 10 employees as 10 attributes of the project entity.
• Schemas should prevent representing the same facts multiple times (avoid redundancy).
• An attribute/relationship is redundant if deleting it does not result in a loss of any information.
• redundancy may cause:
• wastage of space in storing data.
• application programming to be more difficult -- applications need to update all instances of a fact else risk inconsistency of database.
• Consistent and clear naming policy for attributes, entities, and relationships

50

Redundant Attributes

• Manager’s start date stored twice -- redundancy.

​

51

manages

start date

Redundant Relationship

• The fact that a project is-customer-of a supplier can be derived from the relationships between supplier and item and between item and project.
• That is, a project is-customer-of a supplier if there is a item that the supplier supplies which is used by the project.
• Redundancy analysis can be tricky -- if supplies is a N:N relationship, then schema does not contain redundancy.

​

52

supplier

project

item

supplies

used-by

is-customer-of

A Design Problem

• We wish to design a database representing cities, counties, and states in the US.
• For states, we wish to record the name, population, and state capital (which is a city).
• For counties, we wish to record the name, the population, and the state in which it is located.
• For cities, we wish to record the name, the population, the state in which it is located and the county in which it is located.

53

Uniqueness assumptions

• Names of states are unique.
• Names of counties are only unique within a state (e.g., 26 states have Washington Counties).
• Cities are likewise unique only within a state (e.g., there are 24 Springfields among the 50 states).
• Some counties and cities have the same name, even within a state (example: San Francisco).
• All cities are located within a single county.

54

Design 1: Bad design

55

Located-in2

capital

County Population repeated for each city

Design 2: Good design

56

Located-in2

capital

County Population repeated for each city

Belongs-to

Another Design Problem

• We wish to design a database consistent with the following facts.
• Trains are either local trains or express trains, but never both.
• A train has a unique number and an engineer.
• Stations are either express stops or local stops, but never both.
• A station has a name (assumed unique) and an address.
• All local trains stop at all stations.
• Express trains stop only at express stations.
• For each train and each station the train stops at, there is a time.

57

Design 1: Bad design

58

Does not capture the constraints that express trains only stop only at express stations and local trains stop at all local stations

StopsAt

time

Design 1: Better design

59

StopsAt1

time

IsA

express train

local train

express stop

local stop

IsA

d

d

StopsAt2

time