Database Management SystemsRelational Model Notation

Relational Model Notation

LevelIntermediate

Duration90 mins

TopicRelational Model Notation

3 / 5

Constraint Notation: Formalizing Data Rules

The Language of Data Integrity

A database without constraints is merely a data container—it accepts anything, guarantees nothing, and trusts everything. Constraints transform a passive container into an active guardian of data quality, automatically enforcing the rules that distinguish valid data from invalid.

Constraint notation provides the formal language for expressing these rules precisely. Without it, constraints remain ambiguous English descriptions prone to misinterpretation. With proper notation, constraints become unambiguous specifications that can be:

Verified for completeness and consistency
Translated directly to database implementations
Reasoned about mathematically
Communicated precisely across teams and documentation

This page explores the notational conventions for all major constraint types, from fundamental key constraints to complex semantic rules.

Learning Objectives

After studying this page, you will be able to:

• Express key constraints using formal notation • Specify referential integrity constraints with actions • Write domain and check constraint specifications • Formalize functional and multivalued dependencies • Document complex business rules in constraint notation

Key Constraint Notation

Key constraints ensure tuple uniqueness—no two tuples can have identical values for key attributes. Formal notation precisely distinguishes between superkeys, candidate keys, and primary keys.

Superkey Notation

A superkey is any set of attributes that uniquely identifies tuples:

SK(R) = X means attribute set X is a superkey for relation R

Formal definition: X is a superkey of R if and only if: ∀t₁, t₂ ∈ r(R): t₁[X] = t₂[X] → t₁ = t₂

Candidate Key Notation

A candidate key is a minimal superkey (no proper subset is a superkey):

CK(R) = X means X is a candidate key for R

Formal definition: X is a candidate key of R iff:

X is a superkey of R, AND
∀Y ⊂ X: Y is NOT a superkey of R (minimality)

Primary Key Notation

The designated main identifier from among candidate keys:

PK(R) = X or R(..., X̲, ...) (underlined in schema)

key_notation.txt

Key Notation

// KEY CONSTRAINT NOTATION
// ========================
 
// Schema
EMPLOYEE(emp_id, ssn, email, name, dept_id, salary)
 
// Superkey Examples (not necessarily minimal)
SK₁(EMPLOYEE) = {emp_id}
SK₂(EMPLOYEE) = {ssn}
SK₃(EMPLOYEE) = {email}
SK₄(EMPLOYEE) = {emp_id, name}     // Superkey (contains emp_id)
SK₅(EMPLOYEE) = {ssn, email, name} // Superkey (contains ssn)
 
// Candidate Keys (minimal superkeys)
CK₁(EMPLOYEE) = {emp_id}  // emp_id alone is unique
CK₂(EMPLOYEE) = {ssn}     // ssn alone is unique
CK₃(EMPLOYEE) = {email}   // email alone is unique
 
// Primary Key Selection
PK(EMPLOYEE) = {emp_id}   // Chosen as primary identifier
 
// Alternate Keys (candidate keys not chosen as primary)
AK(EMPLOYEE) = {{ssn}, {email}}
 
// Composite Key Example
ENROLLMENT(student_id, course_id, semester, grade)
PK(ENROLLMENT) = {student_id, course_id, semester}  // Composite
 
// Key Constraint in Schema Notation
EMPLOYEE(emp_id*, ssn [UNIQUE], email [UNIQUE], name, dept_id, salary)
 
// Formal Constraint Statement
∀t₁, t₂ ∈ r(EMPLOYEE): 
    t₁[emp_id] = t₂[emp_id] → t₁ = t₂    // PK uniqueness
∀t₁, t₂ ∈ r(EMPLOYEE): 
    t₁[ssn] = t₂[ssn] → t₁ = t₂          // UNIQUE constraint
∀t₁, t₂ ∈ r(EMPLOYEE): 
    t₁[email] = t₂[email] → t₁ = t₂      // UNIQUE constraint

Key Types and Notation Summary
Key Type	Notation	Property	Example
Superkey	SK(R) = X	Uniquely identifies (may not be minimal)	{emp_id, name}
Candidate Key	CK(R) = X	Minimal superkey	{emp_id}
Primary Key	PK(R) = X	Designated main identifier	{emp_id}
Alternate Key	AK(R) = X	Candidate key not chosen as PK	{ssn}, {email}
Composite Key	PK(R) = {A,B,C}	Multi-attribute key	{student_id, course_id}

Referential Integrity Notation

Referential integrity constraints ensure that foreign key values correspond to existing primary key values in referenced tables.

Basic Foreign Key Notation

R.A → S.B or R[A] ⊆ S[B]

Meaning: Every value of attribute A in relation R must appear as a value of attribute B in relation S.

Formal Definition

For FK constraint R.FK → S.PK:

∀t ∈ r(R): t[FK] ≠ NULL → ∃u ∈ r(S): t[FK] = u[PK]

Extended Notation with Referential Actions

Complete constraint specification includes update/delete actions:

R.A → S.B [ON DELETE action] [ON UPDATE action]

Where action ∈ {RESTRICT, CASCADE, SET NULL, SET DEFAULT, NO ACTION}

referential_notation.txt

FK Notation

// REFERENTIAL INTEGRITY NOTATION
// ================================
 
// Basic Foreign Key Notation
ORDER.customer_id → CUSTOMER.customer_id
EMPLOYEE.dept_id → DEPARTMENT.dept_id
ORDER_ITEM.product_id → PRODUCT.product_id
 
// Set Inclusion Notation
π_customer_id(ORDER) ⊆ π_customer_id(CUSTOMER)
// All customer_ids in ORDER must exist in CUSTOMER
 
// Complete Constraint Specification
FK₁: ORDER.customer_id → CUSTOMER.customer_id
     ON DELETE RESTRICT
     ON UPDATE CASCADE
 
FK₂: ORDER_ITEM.order_id → ORDER.order_id
     ON DELETE CASCADE
     ON UPDATE CASCADE
 
FK₃: EMPLOYEE.manager_id → EMPLOYEE.emp_id  // Self-referencing
     ON DELETE SET NULL
     ON UPDATE CASCADE
 
// Nullable Foreign Key
// Optionally references (NULL allowed)
FK₄: EMPLOYEE.dept_id →? DEPARTMENT.dept_id
     -- dept_id can be NULL (employee may be unassigned)
 
// Composite Foreign Key
ORDER_ITEM(order_id, line_num, product_id, quantity)
FK: ORDER_ITEM[order_id] → ORDER[order_id]
 
ENROLLMENT(student_id, course_id, semester, grade)
FK₁: ENROLLMENT[student_id] → STUDENT[student_id]
FK₂: ENROLLMENT[course_id] → COURSE[course_id]
 
// Constraint Verification Expression
// "FK constraint ORDER.customer_id → CUSTOMER.customer_id is satisfied"
∀t ∈ r(ORDER): 
    t[customer_id] IS NULL ∨ t[customer_id] ∈ π_customer_id(CUSTOMER)

Referential Action Notation

•RESTRICT — Prevent delete/update if referenced rows exist
•CASCADE — Propagate delete/update to referencing rows
•SET NULL — Set foreign key to NULL when referenced row changes
•SET DEFAULT — Set foreign key to default value on change
•NO ACTION — Similar to RESTRICT (deferred check in some DBMS)

Domain and Check Constraint Notation

Domain constraints restrict attribute values to valid ranges, while check constraints express arbitrary conditions on individual tuples.

Domain Constraint Notation

dom(A) = D [WHERE condition]

Examples:

dom(age) = INTEGER WHERE 0 ≤ age ≤ 150
dom(status) = {'active', 'inactive', 'pending'}
dom(email) = VARCHAR(255) WHERE email MATCHES '^[a-z0-9.]+@[a-z0-9.]+$'

Check Constraint Notation

General format: CHECK(predicate) where predicate is a Boolean expression.

Relation-level: Constraint applies to all tuples in a relation.

Cross-relation: Constraint involves multiple relations (implemented via triggers).

check_notation.txt

Constraint Notation

// DOMAIN AND CHECK CONSTRAINT NOTATION
// =====================================
 
// Domain Constraints
dom(salary) = DECIMAL(10,2) WHERE salary ≥ 0
dom(age) = INTEGER WHERE age ∈ [0, 150]
dom(gender) = CHAR(1) WHERE gender ∈ {'M', 'F', 'X'}
dom(rating) = DECIMAL(2,1) WHERE rating ∈ [0.0, 5.0]
dom(percentage) = DECIMAL(5,2) WHERE 0 ≤ percentage ≤ 100
 
// Enumeration Domain
dom(order_status) = {'pending', 'confirmed', 'shipped', 'delivered', 'cancelled'}
dom(day_of_week) = {'Mon', 'Tue', 'Wed', 'Thu', 'Fri', 'Sat', 'Sun'}
 
// Tuple-Level Check Constraints
EMPLOYEE:
  CHECK(salary ≥ 0)
  CHECK(hire_date ≤ CURRENT_DATE)
  CHECK(birth_date < hire_date)  // Must be born before hired
  
ORDER:
  CHECK(total_amount ≥ 0)
  CHECK(ship_date IS NULL OR ship_date ≥ order_date)
  CHECK(status ∈ dom(order_status))
 
// Conditional Constraints
EMPLOYEE:
  CHECK(salary ≥ min_salary)
  CHECK(title = 'Manager' → salary ≥ 80000)  // Managers earn at least 80K
  CHECK(status = 'terminated' → termination_date IS NOT NULL)
 
// Multi-Attribute Constraints
EVENT:
  CHECK(end_date > start_date OR end_date IS NULL)
  CHECK(max_attendees IS NULL OR max_attendees > 0)
  CHECK(status = 'cancelled' → cancelled_by IS NOT NULL)
 
// Formal Predicate Notation
∀t ∈ r(EMPLOYEE): t[salary] ≥ 0
∀t ∈ r(ORDER): t[ship_date] = NULL ∨ t[ship_date] ≥ t[order_date]

Constraint Enforcement Levels

Constraints operate at different granularities:

• Column-level: Domain constraints on single attributes • Tuple-level: CHECK constraints on individual rows • Table-level: UNIQUE, PRIMARY KEY constraints • Database-level: Foreign keys, cross-table assertions

Notation should clarify which level the constraint operates at.

Functional Dependency Notation

Functional dependencies (FDs) express deterministic relationships between attribute sets. They are fundamental to normalization theory and database design.

Basic FD Notation

X → Y (X functionally determines Y)

Meaning: If two tuples agree on X, they must agree on Y.

Formal definition: ∀t₁, t₂ ∈ r(R): t₁[X] = t₂[X] → t₁[Y] = t₂[Y]

FD Set Notation

F = {X₁ → Y₁, X₂ → Y₂, ...} — Set of FDs holding in relation R

F⁺ — Closure of F (all FDs derivable from F using Armstrong's axioms)

fd_notation.txt

FD Notation

// FUNCTIONAL DEPENDENCY NOTATION
// ================================
 
// Schema: EMPLOYEE(emp_id, ssn, name, dept_id, dept_name, salary)
 
// Individual FDs
emp_id → ssn, name, dept_id, salary      // emp_id determines all
ssn → emp_id, name, dept_id, salary      // ssn also determines all
dept_id → dept_name                       // department determines its name
 
// FD Set Notation
F = {
    emp_id → ssn,
    emp_id → name,
    emp_id → dept_id,
    emp_id → salary,
    ssn → emp_id,
    dept_id → dept_name
}
 
// Compact notation (grouping RHS)
F = {
    emp_id → {ssn, name, dept_id, salary},
    ssn → {emp_id, name, dept_id, salary},
    dept_id → dept_name
}
 
// Closure of Attribute Set
// X⁺ = set of all attributes functionally determined by X
{emp_id}⁺ = {emp_id, ssn, name, dept_id, salary, dept_name}
{dept_id}⁺ = {dept_id, dept_name}
 
// Minimal Cover / Canonical Cover
// Irreducible set of FDs equivalent to F
F_min = {
    emp_id → ssn,
    emp_id → name,
    emp_id → dept_id,
    emp_id → salary,
    ssn → emp_id,
    dept_id → dept_name
}
 
// Trivial vs Non-Trivial FDs
emp_id → emp_id             // Trivial (Y ⊆ X)
{emp_id, name} → name       // Trivial
emp_id → name               // Non-trivial (useful)
 
// Transitive Dependency (for 3NF analysis)
emp_id → dept_id → dept_name
// emp_id transitively determines dept_name via dept_id

Armstrong's Axioms (Inference Rules)

•Reflexivity: If Y ⊆ X, then X → Y
•Augmentation: If X → Y, then XZ → YZ
•Transitivity: If X → Y and Y → Z, then X → Z
•Union: If X → Y and X → Z, then X → YZ
•Decomposition: If X → YZ, then X → Y and X → Z
•Pseudotransitivity: If X → Y and WY → Z, then WX → Z

Multivalued Dependency Notation

Multivalued dependencies (MVDs) express independence between sets of attributes—relevant for 4NF analysis.

MVD Notation

X ↠ Y (X multidetermines Y)

Meaning: For a fixed X value, the Y values are independent of R-X-Y values.

Formal definition: In R(X, Y, Z) where Z = R - X - Y: ∀t₁, t₂ ∈ r(R): t₁[X] = t₂[X] → ∃t₃ ∈ r(R): t₃[X] = t₁[X] ∧ t₃[Y] = t₁[Y] ∧ t₃[Z] = t₂[Z]

Relationship to FDs

Every FD implies an MVD: X → Y implies X ↠ Y

But not vice versa: X ↠ Y does not imply X → Y

mvd_notation.txt

MVD Notation

// MULTIVALUED DEPENDENCY NOTATION
// =================================
 
// Schema: COURSE_INFO(course_id, instructor, textbook)
// One course can have multiple instructors AND multiple textbooks
// But instructors and textbooks are INDEPENDENT
 
// MVD Notation
course_id ↠ instructor
course_id ↠ textbook
 
// Equivalently (complementation rule)
course_id ↠ instructor | textbook
// The | indicates the MVDs partition the non-key attributes
 
// Example Instance showing MVD
r(COURSE_INFO) = {
    (CS101, 'Dr. Smith', 'Database Systems'),
    (CS101, 'Dr. Smith', 'SQL Fundamentals'),
    (CS101, 'Dr. Jones', 'Database Systems'),
    (CS101, 'Dr. Jones', 'SQL Fundamentals')
}
// Note: For CS101, EVERY instructor is paired with EVERY textbook
// This is the hallmark of a multivalued dependency
 
// MVD violations occur when pairs are incomplete
// Violation example:
r_bad = {
    (CS101, 'Dr. Smith', 'Database Systems'),
    (CS101, 'Dr. Jones', 'SQL Fundamentals')
}
// This violates course_id ↠ instructor because not all combinations exist
 
// Join Dependency (generalization of MVD)
// *(R₁, R₂, ..., Rₙ) means R decomposes losslessly into R₁, R₂, ..., Rₙ
*(COURSE_INSTRUCTOR, COURSE_TEXTBOOK)
where COURSE_INSTRUCTOR(course_id, instructor)
      COURSE_TEXTBOOK(course_id, textbook)

Complex Business Rule Notation

Beyond structural constraints, databases must enforce complex business rules—semantic constraints that reflect organizational policies.

Assertion Notation

Database-wide constraints spanning multiple tables:

ASSERT constraint_name: predicate

Common Patterns

business_rules.txt

Business Rules

// COMPLEX BUSINESS RULE NOTATION
// =================================
 
// CARDINALITY CONSTRAINTS
// -----------------------
// "Each department must have 1-10 employees"
ASSERT dept_size:
    ∀d ∈ r(DEPARTMENT): 
        1 ≤ |{e ∈ r(EMPLOYEE) : e[dept_id] = d[dept_id]}| ≤ 10
 
// AGGREGATE CONSTRAINTS
// ---------------------
// "Order total must equal sum of line items"
ASSERT order_total_correct:
    ∀o ∈ r(ORDER):
        o[total_amount] = Σ{li[quantity] × li[unit_price] : 
                           li ∈ r(ORDER_LINE) ∧ li[order_id] = o[order_id]}
 
// "Total salaries per dept cannot exceed budget"
ASSERT salary_budget:
    ∀d ∈ r(DEPARTMENT):
        Σ{e[salary] : e ∈ r(EMPLOYEE) ∧ e[dept_id] = d[dept_id]} ≤ d[budget]
 
// EXISTENCE CONSTRAINTS
// ---------------------
// "Every manager must also be an employee"
ASSERT manager_is_employee:
    ∀d ∈ r(DEPARTMENT): d[manager_id] IS NULL ∨
        ∃e ∈ r(EMPLOYEE): e[emp_id] = d[manager_id]
 
// TEMPORAL CONSTRAINTS
// --------------------
// "Project end_date must be after start_date"
∀p ∈ r(PROJECT): p[end_date] IS NULL ∨ p[end_date] > p[start_date]
 
// "Employee cannot be assigned to overlapping projects"
∀a₁, a₂ ∈ r(ASSIGNMENT): 
    a₁[emp_id] = a₂[emp_id] ∧ a₁[project_id] ≠ a₂[project_id] →
    INTERVAL(a₁[start], a₁[end]) ∩ INTERVAL(a₂[start], a₂[end]) = ∅
 
// CONDITIONAL CONSTRAINTS
// -----------------------
// "Gold customers get at least 10% discount"
∀o ∈ r(ORDER):
    (∃c ∈ r(CUSTOMER): c[id] = o[customer_id] ∧ c[tier] = 'Gold') →
    o[discount_percent] ≥ 10
 
// "Hazardous products require special shipping"
∀oi ∈ r(ORDER_ITEM):
    (∃p ∈ r(PRODUCT): p[id] = oi[product_id] ∧ p[hazardous] = TRUE) →
    (∃o ∈ r(ORDER): o[id] = oi[order_id] ∧ o[shipping_class] = 'Hazmat')

Implementation Reality

Most complex business rules cannot be expressed as standard SQL constraints. They require triggers, stored procedures, or application-layer enforcement. However, formal notation in documentation ensures the rules are unambiguously specified regardless of implementation mechanism.

Summary: Constraint Notation Mastery

Key Takeaways

•Key constraints use SK/CK/PK notation to specify uniqueness requirements
•Referential integrity uses R.A → S.B with action specifications
•Domain constraints define valid value ranges with WHERE conditions
•Functional dependencies X → Y express deterministic relationships
•Multivalued dependencies X ↠ Y express attribute independence
•Complex business rules use assertion notation with predicate logic

Page Complete

You can now express database constraints using formal notation—from simple key constraints to complex business rules. Next, we explore diagrammatic representation techniques that visualize schemas and relationships.

3 / 5

Loading learning content...

Database Management SystemsRelational Model Notation

Relational Model Notation

LevelIntermediate

Duration90 mins

TopicRelational Model Notation

3 / 5

Constraint Notation: Formalizing Data Rules

The Language of Data Integrity

Verified for completeness and consistency
Translated directly to database implementations
Reasoned about mathematically
Communicated precisely across teams and documentation

This page explores the notational conventions for all major constraint types, from fundamental key constraints to complex semantic rules.

Learning Objectives

After studying this page, you will be able to:

Key Constraint Notation

Key constraints ensure tuple uniqueness—no two tuples can have identical values for key attributes. Formal notation precisely distinguishes between superkeys, candidate keys, and primary keys.

Superkey Notation

A superkey is any set of attributes that uniquely identifies tuples:

SK(R) = X means attribute set X is a superkey for relation R

Formal definition: X is a superkey of R if and only if: ∀t₁, t₂ ∈ r(R): t₁[X] = t₂[X] → t₁ = t₂

Candidate Key Notation

A candidate key is a minimal superkey (no proper subset is a superkey):

CK(R) = X means X is a candidate key for R

Formal definition: X is a candidate key of R iff:

X is a superkey of R, AND
∀Y ⊂ X: Y is NOT a superkey of R (minimality)

Primary Key Notation

The designated main identifier from among candidate keys:

PK(R) = X or R(..., X̲, ...) (underlined in schema)

key_notation.txt

Key Notation

// KEY CONSTRAINT NOTATION
// ========================
 
// Schema
EMPLOYEE(emp_id, ssn, email, name, dept_id, salary)
 
// Superkey Examples (not necessarily minimal)
SK₁(EMPLOYEE) = {emp_id}
SK₂(EMPLOYEE) = {ssn}
SK₃(EMPLOYEE) = {email}
SK₄(EMPLOYEE) = {emp_id, name}     // Superkey (contains emp_id)
SK₅(EMPLOYEE) = {ssn, email, name} // Superkey (contains ssn)
 
// Candidate Keys (minimal superkeys)
CK₁(EMPLOYEE) = {emp_id}  // emp_id alone is unique
CK₂(EMPLOYEE) = {ssn}     // ssn alone is unique
CK₃(EMPLOYEE) = {email}   // email alone is unique
 
// Primary Key Selection
PK(EMPLOYEE) = {emp_id}   // Chosen as primary identifier
 
// Alternate Keys (candidate keys not chosen as primary)
AK(EMPLOYEE) = {{ssn}, {email}}
 
// Composite Key Example
ENROLLMENT(student_id, course_id, semester, grade)
PK(ENROLLMENT) = {student_id, course_id, semester}  // Composite
 
// Key Constraint in Schema Notation
EMPLOYEE(emp_id*, ssn [UNIQUE], email [UNIQUE], name, dept_id, salary)
 
// Formal Constraint Statement
∀t₁, t₂ ∈ r(EMPLOYEE): 
    t₁[emp_id] = t₂[emp_id] → t₁ = t₂    // PK uniqueness
∀t₁, t₂ ∈ r(EMPLOYEE): 
    t₁[ssn] = t₂[ssn] → t₁ = t₂          // UNIQUE constraint
∀t₁, t₂ ∈ r(EMPLOYEE): 
    t₁[email] = t₂[email] → t₁ = t₂      // UNIQUE constraint

Key Types and Notation Summary
Key Type	Notation	Property	Example
Superkey	SK(R) = X	Uniquely identifies (may not be minimal)	{emp_id, name}
Candidate Key	CK(R) = X	Minimal superkey	{emp_id}
Primary Key	PK(R) = X	Designated main identifier	{emp_id}
Alternate Key	AK(R) = X	Candidate key not chosen as PK	{ssn}, {email}
Composite Key	PK(R) = {A,B,C}	Multi-attribute key	{student_id, course_id}

Referential Integrity Notation

Referential integrity constraints ensure that foreign key values correspond to existing primary key values in referenced tables.

Basic Foreign Key Notation

R.A → S.B or R[A] ⊆ S[B]

Meaning: Every value of attribute A in relation R must appear as a value of attribute B in relation S.

Formal Definition

For FK constraint R.FK → S.PK:

∀t ∈ r(R): t[FK] ≠ NULL → ∃u ∈ r(S): t[FK] = u[PK]

Extended Notation with Referential Actions

Complete constraint specification includes update/delete actions:

R.A → S.B [ON DELETE action] [ON UPDATE action]

Where action ∈ {RESTRICT, CASCADE, SET NULL, SET DEFAULT, NO ACTION}

referential_notation.txt

FK Notation

// REFERENTIAL INTEGRITY NOTATION
// ================================
 
// Basic Foreign Key Notation
ORDER.customer_id → CUSTOMER.customer_id
EMPLOYEE.dept_id → DEPARTMENT.dept_id
ORDER_ITEM.product_id → PRODUCT.product_id
 
// Set Inclusion Notation
π_customer_id(ORDER) ⊆ π_customer_id(CUSTOMER)
// All customer_ids in ORDER must exist in CUSTOMER
 
// Complete Constraint Specification
FK₁: ORDER.customer_id → CUSTOMER.customer_id
     ON DELETE RESTRICT
     ON UPDATE CASCADE
 
FK₂: ORDER_ITEM.order_id → ORDER.order_id
     ON DELETE CASCADE
     ON UPDATE CASCADE
 
FK₃: EMPLOYEE.manager_id → EMPLOYEE.emp_id  // Self-referencing
     ON DELETE SET NULL
     ON UPDATE CASCADE
 
// Nullable Foreign Key
// Optionally references (NULL allowed)
FK₄: EMPLOYEE.dept_id →? DEPARTMENT.dept_id
     -- dept_id can be NULL (employee may be unassigned)
 
// Composite Foreign Key
ORDER_ITEM(order_id, line_num, product_id, quantity)
FK: ORDER_ITEM[order_id] → ORDER[order_id]
 
ENROLLMENT(student_id, course_id, semester, grade)
FK₁: ENROLLMENT[student_id] → STUDENT[student_id]
FK₂: ENROLLMENT[course_id] → COURSE[course_id]
 
// Constraint Verification Expression
// "FK constraint ORDER.customer_id → CUSTOMER.customer_id is satisfied"
∀t ∈ r(ORDER): 
    t[customer_id] IS NULL ∨ t[customer_id] ∈ π_customer_id(CUSTOMER)

Referential Action Notation

•RESTRICT — Prevent delete/update if referenced rows exist
•CASCADE — Propagate delete/update to referencing rows
•SET NULL — Set foreign key to NULL when referenced row changes
•SET DEFAULT — Set foreign key to default value on change
•NO ACTION — Similar to RESTRICT (deferred check in some DBMS)

Domain and Check Constraint Notation

Domain constraints restrict attribute values to valid ranges, while check constraints express arbitrary conditions on individual tuples.

Domain Constraint Notation

dom(A) = D [WHERE condition]

Examples:

dom(age) = INTEGER WHERE 0 ≤ age ≤ 150
dom(status) = {'active', 'inactive', 'pending'}
dom(email) = VARCHAR(255) WHERE email MATCHES '^[a-z0-9.]+@[a-z0-9.]+$'

Check Constraint Notation

General format: CHECK(predicate) where predicate is a Boolean expression.

Relation-level: Constraint applies to all tuples in a relation.

Cross-relation: Constraint involves multiple relations (implemented via triggers).

check_notation.txt

Constraint Notation

// DOMAIN AND CHECK CONSTRAINT NOTATION
// =====================================
 
// Domain Constraints
dom(salary) = DECIMAL(10,2) WHERE salary ≥ 0
dom(age) = INTEGER WHERE age ∈ [0, 150]
dom(gender) = CHAR(1) WHERE gender ∈ {'M', 'F', 'X'}
dom(rating) = DECIMAL(2,1) WHERE rating ∈ [0.0, 5.0]
dom(percentage) = DECIMAL(5,2) WHERE 0 ≤ percentage ≤ 100
 
// Enumeration Domain
dom(order_status) = {'pending', 'confirmed', 'shipped', 'delivered', 'cancelled'}
dom(day_of_week) = {'Mon', 'Tue', 'Wed', 'Thu', 'Fri', 'Sat', 'Sun'}
 
// Tuple-Level Check Constraints
EMPLOYEE:
  CHECK(salary ≥ 0)
  CHECK(hire_date ≤ CURRENT_DATE)
  CHECK(birth_date < hire_date)  // Must be born before hired
  
ORDER:
  CHECK(total_amount ≥ 0)
  CHECK(ship_date IS NULL OR ship_date ≥ order_date)
  CHECK(status ∈ dom(order_status))
 
// Conditional Constraints
EMPLOYEE:
  CHECK(salary ≥ min_salary)
  CHECK(title = 'Manager' → salary ≥ 80000)  // Managers earn at least 80K
  CHECK(status = 'terminated' → termination_date IS NOT NULL)
 
// Multi-Attribute Constraints
EVENT:
  CHECK(end_date > start_date OR end_date IS NULL)
  CHECK(max_attendees IS NULL OR max_attendees > 0)
  CHECK(status = 'cancelled' → cancelled_by IS NOT NULL)
 
// Formal Predicate Notation
∀t ∈ r(EMPLOYEE): t[salary] ≥ 0
∀t ∈ r(ORDER): t[ship_date] = NULL ∨ t[ship_date] ≥ t[order_date]

Constraint Enforcement Levels

Constraints operate at different granularities:

Notation should clarify which level the constraint operates at.

Functional Dependency Notation

Functional dependencies (FDs) express deterministic relationships between attribute sets. They are fundamental to normalization theory and database design.

Basic FD Notation

X → Y (X functionally determines Y)

Meaning: If two tuples agree on X, they must agree on Y.

Formal definition: ∀t₁, t₂ ∈ r(R): t₁[X] = t₂[X] → t₁[Y] = t₂[Y]

FD Set Notation

F = {X₁ → Y₁, X₂ → Y₂, ...} — Set of FDs holding in relation R

F⁺ — Closure of F (all FDs derivable from F using Armstrong's axioms)

fd_notation.txt

FD Notation

// FUNCTIONAL DEPENDENCY NOTATION
// ================================
 
// Schema: EMPLOYEE(emp_id, ssn, name, dept_id, dept_name, salary)
 
// Individual FDs
emp_id → ssn, name, dept_id, salary      // emp_id determines all
ssn → emp_id, name, dept_id, salary      // ssn also determines all
dept_id → dept_name                       // department determines its name
 
// FD Set Notation
F = {
    emp_id → ssn,
    emp_id → name,
    emp_id → dept_id,
    emp_id → salary,
    ssn → emp_id,
    dept_id → dept_name
}
 
// Compact notation (grouping RHS)
F = {
    emp_id → {ssn, name, dept_id, salary},
    ssn → {emp_id, name, dept_id, salary},
    dept_id → dept_name
}
 
// Closure of Attribute Set
// X⁺ = set of all attributes functionally determined by X
{emp_id}⁺ = {emp_id, ssn, name, dept_id, salary, dept_name}
{dept_id}⁺ = {dept_id, dept_name}
 
// Minimal Cover / Canonical Cover
// Irreducible set of FDs equivalent to F
F_min = {
    emp_id → ssn,
    emp_id → name,
    emp_id → dept_id,
    emp_id → salary,
    ssn → emp_id,
    dept_id → dept_name
}
 
// Trivial vs Non-Trivial FDs
emp_id → emp_id             // Trivial (Y ⊆ X)
{emp_id, name} → name       // Trivial
emp_id → name               // Non-trivial (useful)
 
// Transitive Dependency (for 3NF analysis)
emp_id → dept_id → dept_name
// emp_id transitively determines dept_name via dept_id

Armstrong's Axioms (Inference Rules)

•Reflexivity: If Y ⊆ X, then X → Y
•Augmentation: If X → Y, then XZ → YZ
•Transitivity: If X → Y and Y → Z, then X → Z
•Union: If X → Y and X → Z, then X → YZ
•Decomposition: If X → YZ, then X → Y and X → Z
•Pseudotransitivity: If X → Y and WY → Z, then WX → Z

Multivalued Dependency Notation

Multivalued dependencies (MVDs) express independence between sets of attributes—relevant for 4NF analysis.

MVD Notation

X ↠ Y (X multidetermines Y)

Meaning: For a fixed X value, the Y values are independent of R-X-Y values.

Formal definition: In R(X, Y, Z) where Z = R - X - Y: ∀t₁, t₂ ∈ r(R): t₁[X] = t₂[X] → ∃t₃ ∈ r(R): t₃[X] = t₁[X] ∧ t₃[Y] = t₁[Y] ∧ t₃[Z] = t₂[Z]

Relationship to FDs

Every FD implies an MVD: X → Y implies X ↠ Y

But not vice versa: X ↠ Y does not imply X → Y

mvd_notation.txt

MVD Notation

// MULTIVALUED DEPENDENCY NOTATION
// =================================
 
// Schema: COURSE_INFO(course_id, instructor, textbook)
// One course can have multiple instructors AND multiple textbooks
// But instructors and textbooks are INDEPENDENT
 
// MVD Notation
course_id ↠ instructor
course_id ↠ textbook
 
// Equivalently (complementation rule)
course_id ↠ instructor | textbook
// The | indicates the MVDs partition the non-key attributes
 
// Example Instance showing MVD
r(COURSE_INFO) = {
    (CS101, 'Dr. Smith', 'Database Systems'),
    (CS101, 'Dr. Smith', 'SQL Fundamentals'),
    (CS101, 'Dr. Jones', 'Database Systems'),
    (CS101, 'Dr. Jones', 'SQL Fundamentals')
}
// Note: For CS101, EVERY instructor is paired with EVERY textbook
// This is the hallmark of a multivalued dependency
 
// MVD violations occur when pairs are incomplete
// Violation example:
r_bad = {
    (CS101, 'Dr. Smith', 'Database Systems'),
    (CS101, 'Dr. Jones', 'SQL Fundamentals')
}
// This violates course_id ↠ instructor because not all combinations exist
 
// Join Dependency (generalization of MVD)
// *(R₁, R₂, ..., Rₙ) means R decomposes losslessly into R₁, R₂, ..., Rₙ
*(COURSE_INSTRUCTOR, COURSE_TEXTBOOK)
where COURSE_INSTRUCTOR(course_id, instructor)
      COURSE_TEXTBOOK(course_id, textbook)

Complex Business Rule Notation

Beyond structural constraints, databases must enforce complex business rules—semantic constraints that reflect organizational policies.

Assertion Notation

Database-wide constraints spanning multiple tables:

ASSERT constraint_name: predicate

Common Patterns

business_rules.txt

Business Rules

// COMPLEX BUSINESS RULE NOTATION
// =================================
 
// CARDINALITY CONSTRAINTS
// -----------------------
// "Each department must have 1-10 employees"
ASSERT dept_size:
    ∀d ∈ r(DEPARTMENT): 
        1 ≤ |{e ∈ r(EMPLOYEE) : e[dept_id] = d[dept_id]}| ≤ 10
 
// AGGREGATE CONSTRAINTS
// ---------------------
// "Order total must equal sum of line items"
ASSERT order_total_correct:
    ∀o ∈ r(ORDER):
        o[total_amount] = Σ{li[quantity] × li[unit_price] : 
                           li ∈ r(ORDER_LINE) ∧ li[order_id] = o[order_id]}
 
// "Total salaries per dept cannot exceed budget"
ASSERT salary_budget:
    ∀d ∈ r(DEPARTMENT):
        Σ{e[salary] : e ∈ r(EMPLOYEE) ∧ e[dept_id] = d[dept_id]} ≤ d[budget]
 
// EXISTENCE CONSTRAINTS
// ---------------------
// "Every manager must also be an employee"
ASSERT manager_is_employee:
    ∀d ∈ r(DEPARTMENT): d[manager_id] IS NULL ∨
        ∃e ∈ r(EMPLOYEE): e[emp_id] = d[manager_id]
 
// TEMPORAL CONSTRAINTS
// --------------------
// "Project end_date must be after start_date"
∀p ∈ r(PROJECT): p[end_date] IS NULL ∨ p[end_date] > p[start_date]
 
// "Employee cannot be assigned to overlapping projects"
∀a₁, a₂ ∈ r(ASSIGNMENT): 
    a₁[emp_id] = a₂[emp_id] ∧ a₁[project_id] ≠ a₂[project_id] →
    INTERVAL(a₁[start], a₁[end]) ∩ INTERVAL(a₂[start], a₂[end]) = ∅
 
// CONDITIONAL CONSTRAINTS
// -----------------------
// "Gold customers get at least 10% discount"
∀o ∈ r(ORDER):
    (∃c ∈ r(CUSTOMER): c[id] = o[customer_id] ∧ c[tier] = 'Gold') →
    o[discount_percent] ≥ 10
 
// "Hazardous products require special shipping"
∀oi ∈ r(ORDER_ITEM):
    (∃p ∈ r(PRODUCT): p[id] = oi[product_id] ∧ p[hazardous] = TRUE) →
    (∃o ∈ r(ORDER): o[id] = oi[order_id] ∧ o[shipping_class] = 'Hazmat')

Implementation Reality

Summary: Constraint Notation Mastery

Key Takeaways

•Key constraints use SK/CK/PK notation to specify uniqueness requirements
•Referential integrity uses R.A → S.B with action specifications
•Domain constraints define valid value ranges with WHERE conditions
•Functional dependencies X → Y express deterministic relationships
•Multivalued dependencies X ↠ Y express attribute independence
•Complex business rules use assertion notation with predicate logic

Page Complete

3 / 5