Case Study 9: Payroll System (BCNF Decomposition and 3NF Synthesis)

exercises
tutorial
case-study
databases
bcnf
3nf
normalisation

Practice for 2026-05-04-normalisation-and-relational-database-schema-design. Continues week10-tutorial-case-study-8-dirt-road-driving — Peter has now resent Dirt Road Driving’s payroll schema with the full set of functional dependencies included (his earlier email accidentally omitted them).

The corrected payroll schema

Employee [id, firstName, lastName, role]

Project [name, description, funding, projectLeader]
Project.projectLeader references Employee.id

TimeLog [employeeID, projectName, date, hoursWorked, approved]
TimeLog.employeeID references Employee.id
TimeLog.projectName references Project.name

AssetUse [employeeID, assetID, timestamp, useDuration, assetType, purchaseDate, insuranceValue]
assetID → assetType, purchaseDate
assetType → insuranceValue
AssetUse.employeeID references Employee.id

Department [code, name, manager, buildingID, buildingName, buildingLocation, floor]
buildingID → buildingLocation, buildingName
buildingName → buildingLocation, buildingID
Department.manager references Employee.id

EmployeeHistory [employeeID, departmentCode, seniorityLevel, baseSalary, securityLevel]
seniorityLevel, securityLevel → baseSalary
EmployeeHistory.employeeID references Employee.id
EmployeeHistory.departmentCode references Department.code

TripExpenseAllocations [tripName, expenseType, quantity, organiser, startDate, endDate, location, allowance, restrictions, description]
tripName, expenseType → quantity, description
tripName → startDate, endDate, location, organiser
expenseType → allowance, restrictions
TripExpenseAllocations.organiser references Employee.id

TravelInsuranceHistory [tripName, approved, insuranceLevel, description, maxCoverage, advisedPrecautions]
tripName → approved, insuranceLevel, description
insuranceLevel → description, maxCoverage
TravelInsuranceHistory.tripName references TripExpenseAllocations.tripName

Section A — BCNF decomposition

Decompose (if needed) AssetUse, Department, EmployeeHistory, TripExpenseAllocations, and TravelInsuranceHistory into BCNF, clearly stating any new tables and all foreign keys.

AssetUse

CK = {employeeID, assetID, timestamp}. FDs: {employeeID, assetID, timestamp} → {useDuration, assetType, purchaseDate, insuranceValue}, {assetID} → {assetType, purchaseDate}, {assetType} → {insuranceValue}, and the implicit {assetID} → {insuranceValue}. Highest NF: 1NF.

Final answer:

  • Asset [assetID, assetType, purchaseDate] — {assetID} → {assetType, purchaseDate}
  • Insurance [assetID, insuranceValue] — {assetID} → {insuranceValue}, FK assetID references Asset.assetID
  • AssetUse [employeeID, assetID, timestamp, useDuration] — no non-trivial FD, FK assetID references Asset.assetID

Lost: {assetType} → {insuranceValue} (once decomposed, assetType and insuranceValue never appear together in one relation, so this FD can no longer be directly enforced/checked).

Department

CK = {code}. FDs: {code} → {name, manager, buildingID, buildingName, location, floor}, {buildingID} → {buildingLocation, buildingName}, {buildingName} → {buildingLocation, buildingID}. Highest NF: 2NF.

Final answer:

  • Building [buildingID, buildingLocation, buildingName] — {buildingID} → {buildingLocation, buildingName}, {buildingName} → {buildingID, buildingLocation}
  • Department [code, name, manager, buildingID, floor] — {code} → {name, manager, buildingID, floor}, FK buildingID references Building.buildingID

EmployeeHistory

CK = {employeeID, departmentCode}. FDs: {employeeID, departmentCode} → {seniorityLevel, baseSalary, securityLevel}, {seniorityLevel, securityLevel} → {baseSalary}. Highest NF: 2NF.

Final answer:

  • Salary [seniorityLevel, securityLevel, baseSalary] — {seniorityLevel, securityLevel} → {baseSalary}
  • EmployeeHistory [employeeID, departmentCode, seniorityLevel, securityLevel] — {employeeID, departmentCode} → {seniorityLevel, securityLevel}, FKs to Employee.id and Department.code

TripExpenseAllocations

CK = {tripName, expenseType}. FDs: {tripName, expenseType, quantity} → {organiser, startDate, endDate, location, allowance, restrictions, description}, {tripName, expenseType} → {quantity, description}, {tripName} → {startDate, endDate, location, organiser}, {expenseType} → {allowance, restrictions}. Highest NF: 1NF.

Final answer:

Relation FD
Trip [tripName, startDate, endDate, location, organiser] {tripName} → {startDate, endDate, location, organiser}
Expense [expenseType, allowance, restrictions] {expenseType} → {allowance, restrictions}
TripExpenseAllocations [tripName, expenseType, quantity, description] {tripName, expenseType} → {quantity, description}, FKs to Trip.tripName and Expense.expenseType

TravelInsuranceHistory

CK = {tripName} (the schema’s stated primary key {tripName, approved, insuranceLevel} is not minimal — tripName alone is already a key). FDs: {tripName, approved, insuranceLevel} → {description, maxCoverage, advisedPrecautions}, {tripName} → {approved, insuranceLevel, description}, {insuranceLevel} → {description, maxCoverage}. Highest NF: 2NF.

Final answer:

  • InsuranceCoverage [insuranceLevel, description, maxCoverage] — {insuranceLevel} → {description, maxCoverage}
  • TravelInsuranceHistory [tripName, approved, insuranceLevel, advisedPrecautions] — {tripName} → {approved, insuranceLevel}, {tripName, approved, insuranceLevel} → {advisedPrecautions}, FK insuranceLevel references InsuranceCoverage.insuranceLevel

Section B — 3NF synthesis

Decompose (if needed) Department and TripExpenseAllocations into 3NF via minimal-cover synthesis.

Department

CK = {code}. Highest NF (from Section A): 2NF.

Minimal cover: RHS-splitting {code} → {name, manager, buildingID, buildingName, buildingLocation, floor} and removing redundant attributes — code → buildingName and code → buildingLocation are both redundant (derivable transitively via code → buildingID then buildingID → buildingName/buildingLocation); buildingID → buildingLocation is redundant (derivable via buildingID → buildingName then buildingName → buildingLocation). Simplified cover: {code} → {name, manager, buildingID, floor}, {buildingID} → {buildingName}, {buildingName} → {buildingLocation, buildingID}.

Synthesis:

  • Department [code, name, manager, buildingID, floor] — {code} → {name, manager, buildingID, floor}
  • Building [buildingName, buildingLocation, buildingID] — {buildingID} → {buildingName}, {buildingName} → {buildingLocation, buildingID} (a candidate relation [buildingID, buildingName] from {buildingID}→{buildingName} alone is redundant — it’s a subset of this Building relation, so it’s dropped.)

TripExpenseAllocations

CK = {tripName, expenseType} (the stated primary key is not minimal). Highest NF (from Section A): 1NF.

Minimal cover: after RHS-splitting and removing every attribute already implied by {tripName} or {expenseType} alone from the {tripName, expenseType, quantity} → ... FD (all seven of its RHS attributes turn out to be redundant there, since each is already determined by tripName or expenseType individually), the simplified cover is exactly: {tripName, expenseType} → {quantity, description}, {tripName} → {startDate, endDate, location, organiser}, {expenseType} → {allowance, restrictions}.

Synthesis:

  • TripExpenseAllocations [tripName, expenseType, quantity, description] — {tripName, expenseType} → {quantity, description}
  • Trip [tripName, startDate, endDate, location, organiser] — {tripName} → {startDate, endDate, location, organiser}
  • Expense [expenseType, allowance, restrictions] — {expenseType} → {allowance, restrictions}

(Same final relations as the BCNF decomposition in Section A — in this case, decomposition and synthesis happen to converge on the same schema.)