Outline

Today's Topics:

• Good and Bad Database Design
• Database Keys
• Functional Dependencies

Introduction to Database Design Theory

Purpose

• Developed to evaluate relational schemas for design quality
• Focuses on two levels:
  • Logical/Conceptual Level (Logical Transformation)
    • Users understand clearly the meaning of data in relations
    • Enables correct query formulation
  • Implementation/Physical Storage Level (Physical Transformation)
    • How tuples in base relations are stored and updated

Design Methodology

Bottom-up Design (Design by Synthesis)

• Consider basic relationships among individual attributes as starting point
• Use those relationships to construct relation schemas

Top-down Design (Design by Analysis)

• Start with groupings of attributes into relations that exist together naturally
• Analyze relations individually and collectively
• Continue decomposition until all desirable properties are met

Note: The theory can be applied to both design approaches

Implicit Goals (Ideal Solutions for DB Design)

1. Information Preservation

• Maintain all concepts including:
  • Attribute types
  • Entity types
  • Relationship types
  • Generalization/specialization relationships

2. Minimum Redundancy

• Minimize redundant storage of the same data instance
• Reduce the need for multiple updates to maintain consistency across multiple copies of the same data instance

Problems of Poor Database Design

Four Main Problems:

1. Unclear semantics
   • Conceptually: attributes, entity types and relationship types
   • Logically: view and base relations
2. Data redundancy and update anomalies
3. NULL values in tuples (record)
4. Generation of spurious tuples (or data records)

Problem 1: Clear Semantics

Example Schemas:

$\text{EMPLOYEE (Ename, }{\underline{\text{Ssn}}}\text{, Bdate, Address, Dnumber)}$
DEPARTMENT (Dname, Dnumber, Dmgr_ssn)
DEPT_LOCATIONS (Dnumber, Dlocation)
EMP_PROJ (Ssn, Pnumber, Hours, Ename, Pname, Plocation)

• ส่วนที่ Highlight คือเป็น Primary Key นะ (มันขีดเส้นใต้ไม่ได้)

Issue with EMP_PROJ:

• Although it has clear semantics (relates employee to projects)
• It may be better used as a VIEW instead of a base relation
• Combines attributes of two entity types
• Fares poorly against the measure of design quality

Glossary: VIEW = virtual table (or in-memory table)

Informal Design Guideline #1

• Make sure that the semantics of the attributes is clear in the schema
• Do not combine attributes from multiple entity types and relationship types into a single relation

Problem 2: Redundancies and Update Anomalies

Example Schema:

EMP_DEPT (==Ssn==, Ename, Bdate, Address, Dnumber, Dname, Dmgr_ssn)

What happens when we:

1. Insert a new employee tuple → Potential issues
2. Insert a new department that has no employees → Cannot insert without employee
3. Delete an employee tuple that represents the last employee working for a particular department → Loss of department information
4. Change the value of one of the attributes of a particular department (e.g., manager for department 5) → Must update multiple rows

Informal Design Guideline #2

• Design base relation schemas so that no insertion, deletion, or modification anomalies occur
• If any anomalies are present, note them clearly
• Ensure that programs that update the database will operate correctly

Problem 3: NULL Values in Tuples

Issues with Combined Attributes:

• Combined attributes grouped together into a "fat" relation
• Can end up with many NULLs

Problems with NULLs:

• Physical level: Wasted storage space
• Logical level: Interpretation of meaning when JOIN, SELECT, and aggregation (e.g., SUM, COUNT)
• Conceptual level: Understanding meaning
  • Not applicable
  • Unknown
  • Known but absent

Informal Design Guideline #3

• Avoid placing attributes in a base relation whose values may frequently be NULL
• If NULL is unavoidable:
  • Make sure they apply in exceptional cases only
  • Do not apply to a majority of tuples in the relation

Problem 4: Generation of Spurious Tuples

Example Tables:

EMP_LOCS:

EMP_PROJ1:

Result of NATURAL JOIN:

[Image showing spurious tuples - marked with asterisks indicating incorrect/spurious combinations]

Informal Design Guideline #4

• Design relation schemas so they can join with equality conditions on attributes that are appropriately related (PK, FK) pairs
• This guarantees no spurious tuples are generated
• Avoid relations that contain matching attributes that are not (FK, PK) combinations
• Joining on such attributes may produce spurious tuples

Good Database Design Through Normalization

Key Concepts:

• Good design can be achieved by applying normalization
• Normalization is the process for:
  • Evaluating relational schemas
  • Correcting schemas to minimize data redundancies and data anomalies
• Based on concepts of:
  • Normal Forms (NFs)
  • Functional Dependencies (FDs)

This lecture focuses on how to design Keys and FDs

KEYS AND INTEGRITY CONSTRAINTS

Database Keys Overview

Definition:

• Consist of one or more attributes that determine other attributes

Used to:

• Ensure that each row in a table is uniquely identifiable
• Establish relationships among tables
• Ensure the integrity of the data

Key Types:

• Primary Key (PK): Attribute or combination of attributes that uniquely identifies any given row
• Foreign Key (FK): Attribute that identifies another attribute stored in another table

Characteristics of Keys

Composite Key:

• Key composed of more than one attribute

Entity Integrity:

• Condition in which each row in the table has its own unique identity using the primary key (PK)
• Requirements:
  • All values in the PK must be unique
  • No key attribute in the PK can contain null value

Referential Integrity:

• Every reference (using Foreign Key: FK) to an entity instance by another entity instance is valid

Relational Database Keys - Detailed

Keys Definition:

• Consist of one or more attributes that determine other attributes
• Determination: knowing the value of one attribute makes it possible to determine the value of another

Used to:

• Ensure that each row in a table is uniquely identifiable
• Establish relationships among tables and ensure the integrity of the data

Key Types Table:

#FinalExam - ต้องรู้ Superkey, Candidate key

Superkey

Definition:

• An attribute or combination of attributes that uniquely identifies each row in a table
• Superkey is a superset of Candidate key

Example Table:

Only SSN can be Superkey because it contains no duplication - แต่มองได้ว่าเราสามารถเอามา Combine กันได้แล้วมัน Unique แบบนี้ก็เป็น Superkey ได้อยู่ (รวม 2, 3, … ได้เรื่อย ๆ)

คล้าย ๆ Powerset แล้วเราก็มองว่าอันไหนไม่ซ้ำ อันนี้เป็นได้

Examples of Superkeys:

• SSN
  • SSN is unique for every row of data
• (SSN, FNAME)
  • FNAME of employee can be the same, but their SSN is unique
  • So the combination of these two attributes can also be a key
• (FNAME, LNAME)
  • Either FNAME and LNAME of employee can be the same
  • But the combination of these two attributes is unique
  • So this can also be a key
• Many more combinations possible

Candidate Key

ก็ดูจาก Set ทั้งหมดของ Superkey – ให้เริ่มมองจากตัวที่เล็กที่สุดก่อน ถ้าตัวที่ใหญ่กว่ามี SSN อะไรงี้ให้ Cancel ออกเพราะมันซ้ำอะ คือจะเอาไปให้มัน unique อีกทำไม แค่ตัวเดียวก็ Unique อยู่แล้ว

Definition:

• A minimal (irreducible) superkey
• A superkey that does not contain a subset of attributes that is itself a superkey
• Can act as a primary key for a table
• There can be more than one candidate key
• Candidate key is a subset of superkey

Example from Previous Table:

• SSN → superkey AND candidate key
• (FNAME, LNAME) → superkey AND candidate key
• (SSN, FNAME) → superkey but NOT a candidate key (contains redundant attribute)

Primary Key (PK)

Smallest Key!!!!!!!!!! From your candidate ไงงงง - แต่มันเท่ากัน ก็เลือกอะไรที่มันเหมาะสม อะไรก็ได้ up to your design

Definition:

• A candidate key selected to uniquely identify all other attribute values in any given row
• Cannot contain null entries
• One table has only one primary key

Example:

• If candidate keys are: SSN and (FNAME, LNAME)
• We can select SSN as the primary key

Surrogate Key:

• Special type of PK containing unique values automatically generated by the database system
• Usually has no meaning except uniquely identifying a record

NULL Definition:

• Absence of any data value that could represent:
  • An unknown attribute value
  • A known, but missing, attribute value
  • An inapplicable condition

Secondary or Alternative Keys

อันไหนที่ไม่ถูกเลือกเป็น PK ด้านบน ก็จะมองว่ามันเป็น Secondary Key นะ

Definition:

• The candidate key(s) which are not selected as primary key
• An attribute or combination of attributes used strictly for data retrieval purposes

Example:

• If candidate keys are: SSN and (FNAME, LNAME)
• If we select SSN as primary key
• Then (FNAME, LNAME) is the secondary key

Example Keys - Complete Overview

Given Table:

Key Classifications:

Superkeys:

• SSN
• (SSN, FNAME)
• (FNAME, LNAME)
• (FNAME, LNAME, GENDER)
• (FNAME, DEPT_NO)
• (SSN, LNAME)
• (SSN, DEPT_NO)
• (FNAME, LNAME, DEPT_NO)

Candidate Keys:

• SSN
• (FNAME, LNAME)

Primary Key:

• SSN (selected)

Secondary Keys:

• (FNAME, LNAME)

Foreign Key

Definition:

• An attribute or combination of attributes in one table whose values must either:
  • Match the primary key in another table, OR
  • Be null

Example Design:

Original Combined Data:

Better Design Using Relational Model:

Employee Table:

Department Table:

Integrity Rules

1. Entity Integrity

Definition:

• Condition in which each row in the table has its own unique identity

Requirements:

• All of the values in the primary key must be unique
• No key attribute in the primary key can contain a null value

Description Table:

Example - Testing Entity Integrity:

Employee Table:

Can we insert these new records?

2. Referential Integrity

Definition:

• Every reference to an entity instance by another entity instance is valid

Requirements:

• Every non-null foreign key value must reference an existing primary key value
• A key attribute in the foreign key can contain a null value

Description Table:

Example - Testing Referential Integrity:

Employee Table:

Department Table:

Can we insert these new records?

FUNCTIONAL DEPENDENCIES

Functional Dependencies (FDs)

Definition:

• Suppose relational database schema R has n attributes: $A_1, A_2, \dotso, A_n$
• That is, $R=\{A_1, A_2, \dotso, A_n\}$
• Functional dependency is a constraint between two sets of attributes from the database
• Denoted by $X\to Y$, where X ⊆ R and Y ⊆ R
  • อ่านว่า X determine Y (Y depends on X)

Interpretation:

• For any two tuples t₁ and t₂ in relation state r(R):
  • If t₁[X] = t₂[X], they must also have t₁[Y] = t₂[Y]
• Meaning:
  • Values of the Y component of a tuple in r depend on or are determined by values of the X component
  • (i.e., Y is functionally dependent on X)
  • Values of the X component of a tuple in r determine values of the Y component
  • (i.e., X functionally determines Y)

Functional Dependencies (FDs) Definition

Notation: X → Y

Components:

• X (functionally) determines Y
• X: left-hand-side (LHS) or determinant set
• Y: right-hand-side (RHS) or dependent set

Meaning:

• For each X value, there is at most one Y value
• Similar to identifying potential candidate key

Reading:

• "Y is dependent on X", OR
• "X determines the value of Y uniquely"

Example:

• StudentID → StudentName
• StudentID is the determinant attribute
• StudentName is the dependent attribute

FD Examples (Multiple Attributes)

Single Determinant, Single Dependent:

• X₁ → Y₁
• Example: StudentID → StudentName

Single Determinant, Multiple Dependents:

• X → (Y₁, Y₂, Y₃)
• Example: StudentID → (StudentName, email, CGPA)

Multiple Determinants, Single Dependent:

• (X₁, X₂) → Y₁
• Example: (email, phoneNumber) → StudentID

Multiple Determinants, Multiple Dependents:

• (X₁, X₂) → (Y₁, Y₂, Y₃)
• Example: (StudentID, StudentName) → (email, phoneNumber, CGPA)

FD More Examples from a Relation

Schema:

Student (StdID, sName, address, HScode, HSname, HScity, GPA, honor)

Functional Dependencies:

1. StdID → sName
2. StdID → address
3. HSCode → HSname, HSCity
4. HSname, HSCity → HScode
5. StdID → GPA
6. GPA → honor
7. StdID → honor

Note: The last FD can be derived from Transitive Rule

• If A → B and B → C, then A → C

And More...

Implementation of Functional Dependence

How to use functional dependency in SQL

Example Query:

SELECT Student_Name FROM Student WHERE Reg_No = 123;

We should always get only one student_name for a given reg_no.

Analysis:

FD1: REG_NO → STUDENT_NAME

• This functional dependency means that there is at most one student name related to one register number
• This is correct

FD2: STUDENT_NAME → REG_NO

• This functional dependency means that there is at most one register number related to a student name
• This may not be true because there may be more than one student with the same name

Checking Functional Dependencies - Exercise

Given Relation R (A, B, C, D):

Table Tb1:

Check the following FDs:

• (a) A → B
• (b) A → CD
• (c) AB → CD
• (d) C → D
• (e) B → A
• (f) BD → AC
• (g) AD → BC
• (h) D → B
• (i) D → C
• (j) C → A

Solution (a): A → B

Analysis:

A → B does NOT hold in relation R

Why?

• In table R, we have 3 B values (1, 2, and 3) for a given A value (1)
• This violates the FD requirement that each A value should determine at most one B value

Solution (b): A → CD

Analysis:

A → CD HOLDS in relation R

Why?

• In R, we have a single C and D combination of values for every A value

Verification:

Solution (c): AB → CD

Analysis:

AB → CD HOLDS in relation R

Why?

• In R there is one-to-one relationship between AB and CD
• For a given A and B combination of values, there is a unique C and D combination of values

Verification:

Solution (d): C → D

Analysis:

C → D HOLDS in relation R

Why?

• In R there is one-to-one relationship between C and D values

Verification:

Solution (e): B → A

Analysis:

B → A HOLDS in relation R

Why?

• In R there is one-to-one relationship between B and A values
• For a given B value, there is only one associated A value

Verification:

Try Yourself - Remaining FDs

Given Table Tb1:

Check These:

• (f) BD → AC: Your solution is hold
• (g) AD → BC: Your solution is not hold
• (h) D → B: Your solution is not hold
• (i) D → C: Your solution is hold
• (j) C → A: Your solution is hold

Visualizing FDs using Dependency Diagram

Definition:

Dependency diagram: Depicts all dependencies found within a given relational schema

Benefits:

• Helps to get an overview of all relationships among relation's attributes
• Makes it less likely that an important dependency will be overlooked

Dependency Diagram Example

Visual Representation:

[Image showing diagram with C1, C2, C3, C4, C5 with arrows indicating dependencies]

Functional Dependencies Shown:

• FD1: C1 → C2
• FD2: C4 → C5
• FD3: C1, C3 → C2, C4, C5

Dependency Diagram - Complete Example

Schema:

StdSSN | StdCity | StdClass | OfferNo | OffTerm | OffYear | CourseNo | CrsDesc | EnrGrade

All Functional Dependencies:

1. StdSSN → StdCity, StdClass
2. OfferNo → OffTerm, OffYear, CourseNo
3. OfferNo → CrsDesc
4. CourseNo → CrsDesc
5. StdSSN, OfferNo → EnrGrade

[Image showing complete dependency diagram with all attributes and arrows]

Summary

Key Takeaways:

Database Design Quality:

• Clear semantics required
• Minimize redundancy and update anomalies
• Avoid excessive NULL values
• Prevent spurious tuples

Database Keys:

• Superkey, Candidate Key, Primary Key, Foreign Key, Secondary Key
• Entity Integrity and Referential Integrity rules

Functional Dependencies:

• X → Y notation
• Determinant set and Dependent set
• Used to identify potential keys
• Can be visualized using dependency diagrams
• Critical for normalization process

End of Notes