PadhaikoAll subjects

Data Models

Database Management System (ENCT 301)

Open in the Padhaiko app

2.1 Introduction to data models (Entity-relationship, relational, object model, hierarchical, network, graph data models)

A data model is a collection of conceptual tools for describing data, data relationships, data semantics, and consistency constraints. It provides the blueprint used to structure a database at the conceptual and logical levels.

Definition

Categories of Data Models

  1. Entity-Relationship (E-R) Data Model: A high-level conceptual model that represents the real world as a collection of basic objects called entities and relationships among those objects. Primarily used during database design before mapping to tables.
  2. Relational Model: Represents both data and relationships as a collection of mathematical tables (relations), each consisting of named columns (attributes) and unordered rows (tuples). Forms the foundation of modern SQL databases.
  3. Object-Oriented Data Model: Extends the E-R and programming object paradigms by encapsulating attributes (state) and methods (behavior) inside objects, supporting classes, inheritance, object identity (OID), and complex nested structures.
  4. Hierarchical Model: One of the earliest database models (e.g., IBM IMS), organizing records in an inverted tree structure with parent-child links. Every child record has at most one parent ( relationships only), making relationships awkward via record duplication or virtual pointers.
  5. Network Model: Standardized by CODASYL DBTG, extending the hierarchical model into a general directed graph of record types and owner-member set links, allowing a child (member) record to have multiple parents (owners) and directly supporting relationships.
  6. Graph Data Model: Stores data as nodes (vertices) representing entities, edges (relationships) with types and directions, and properties (key-value pairs) on both nodes and edges (e.g., Neo4j). Optimized for multi-hop traversals, social networks, and recommendation engines.
Comparison of Major Data Models
Data ModelCore StructureRelationship HandlingPrimary Use / Era
Entity-Relationship (E-R)Entities, attributes, relationshipsExplicit diamond sets with cardinalitiesConceptual database design & schema diagramming
RelationalTables (relations), rows, columnsForeign keys referencing primary keysGeneral-purpose OLTP & enterprise DBMS (PostgreSQL, MySQL, Oracle)
Object-OrientedClasses, objects, OIDs, methodsObject references & class inheritanceCAD/CAM, multimedia, complex engineering data
HierarchicalInverted tree (parent-child segments)Strictly and (single parent)Legacy mainframe systems (IBM IMS), directory trees
NetworkDirected graph (owner-member sets)Supports via pointer chainsLegacy CODASYL databases; requires manual pointer navigation
GraphNodes, directed labeled edges, propertiesFirst-class edges stored directlySocial graphs, fraud detection, knowledge graphs

2.2 E-R model

The Entity-Relationship (E-R) model, introduced by Peter Chen (1976), describes the logical structure of a database graphically using an E-R Diagram (ERD).

Standard E-R Diagram Notations
ConstructE-R SymbolMeaning
Strong Entity SetSingle RectangleIndependent object type with its own primary key
Weak Entity SetDouble RectangleDependent entity lacking a sufficient primary key of its own
AttributeSingle EllipseSimple single-valued property of an entity or relationship
Key AttributeUnderlined text in EllipsePrimary key attribute (dashed underline for weak partial key)
Multivalued AttributeDouble EllipseAttribute that can hold multiple values for one entity
Derived AttributeDashed EllipseAttribute computed from other stored attributes
Relationship SetSingle DiamondAssociation among entity sets
Identifying RelationshipDouble DiamondLinks a weak entity set to its identifying strong owner
Total ParticipationDouble LineEvery entity in the set must participate in at least one relationship

2.2.1 Entities and entity sets

Definition

Entity and Entity Set

2.2.2 Attributes and keys

Each entity is described by a set of attributes—named properties whose allowed values come from a domain (value set). Attributes are classified along several orthogonal dimensions:

Classification of Attributes in the E-R Model
TypeDescriptionExample (Student)
Simple (Atomic)Cannot be divided into smaller meaningful subparts.RollNo, Gender
CompositeCan be subdivided into smaller component attributes with independent meanings.Name (FirstName, MiddleName, LastName); Address (Ward, City, District)
Single-ValuedHolds at most one value for a single entity instance.DateOfBirth, RollNo
MultivaluedCan hold multiple values simultaneously for a single entity instance.PhoneNumbers, Skills
StoredExplicitly stored in the database.DateOfBirth
DerivedComputed dynamically from other stored attributes or system clock.Age (derived from DateOfBirth and current date)
Null-ValuedUsed when an attribute value is not applicable, unknown, or missing.MiddleName (for someone without one)

Keys in an Entity Set

A key is a set of one or more attributes whose values uniquely identify each entity in an entity set:

2.2.3 Strong and weak entity sets

AspectStrong Entity SetWeak Entity Set
Key SufficiencyPossesses enough attributes to form a primary key on its own.Does not have enough attributes to form a primary key independently.
Existence DependenceExists independently in the database.Existence-dependent on an identifying (owner) strong entity set.
Discriminator (Partial Key)Uses a full primary key (solid underline).Uses a discriminator / partial key (dashed underline) that uniquely identifies weak entities within a single owner.
Full Primary KeyIts own primary key attribute(s).Owner's primary key weak entity's discriminator.
Participation & SymbolSingle rectangle; participation in relationships may be partial or total.Double rectangle; total participation (double line) in the double-diamond identifying relationship.
ExampleEmployee(EmpID, Name) or Loan(LoanNo, Amount)Dependent(DepName, Relation) owned by Employee; Payment(PayNo, PayDate, Amount) owned by Loan.

2.2.4 Relationship and relationship sets (Mapping cardinalities)

Definition

Relationship, Degree, Cardinality, and Participation

A relationship set may also carry descriptive attributes (e.g., Grade or EnrollDate on Enrolls).

Mapping Cardinalities (Cardinality Ratios)

For a binary relationship set between entity sets and , the mapping cardinality specifies the maximum number of entities to which another entity can be associated via :

Binary Mapping Cardinalities
CardinalityMeaningE-R Arrow / LabelExample
One-to-One ()An entity in is associated with at most one entity in , and an entity in is associated with at most one entity in .Arrow from to both and ().Department — HOD (each department has one head; each head leads one department).
One-to-Many ()An entity in is associated with any number ( or more) of entities in , while an entity in is associated with at most one entity in .Arrow toward ().Department — Student (one department has many students; each student belongs to one department).
Many-to-One ()An entity in is associated with at most one entity in , while an entity in can associate with many in .Arrow toward ().Employee — Department (many employees work in one department).
Many-to-Many ()An entity in can associate with many entities in , and an entity in can associate with many entities in .Undirected lines on both sides ().Student — Course (a student takes many courses; a course has many students).

Participation Constraints

2.2.5 Specialization, generalization and aggregation

Extended E-R (EER) features capture inheritance and higher-level abstractions:

AspectSpecialization (Top-Down)Generalization (Bottom-Up)
ApproachTop-down refinement process.Bottom-up synthesis process.
DirectionStarts with a higher-level superclass entity set and divides it into lower-level subclasses with distinct attributes or relationships.Combines multiple lower-level entity sets that share common features into a single higher-level superclass.
ExamplePerson specialized into Student (RollNo, GPA) and Employee (EmpID, Salary).Car and Truck generalized into Vehicle (RegNo, Price).
NotationTriangle labeled ISA pointing from subclass toward superclass; subclasses inherit all attributes and relationships of the superclass.Identical ISA triangle notation in the final EER diagram.

Constraints on Specialization / Generalization

  1. Disjointness Constraint:
    • Disjoint: An entity can belong to at most one lower-level subclass (e.g., a Vehicle is either a Car or a Truck, not both).
    • Overlapping: The same entity may belong to more than one subclass simultaneously (e.g., a Person can be both an Employee and a Student).
  2. Completeness (Participation) Constraint:
    • Total: Every superclass entity must belong to at least one subclass.
    • Partial: A superclass entity need not belong to any subclass.

Aggregation

In a standard E-R diagram, relationships cannot directly connect to other relationships. Aggregation solves this by treating a relationship set along with its participating entity sets as a single higher-level abstract entity (drawn by enclosing the relationship and entities in a dashed or solid box), which can then participate in another relationship.


2.3 Relational model

2.3.1 Concept of relational model, key constraints

Proposed by E. F. Codd (1970), the relational model represents the database as a collection of relations.

Definition

Core Terminology of the Relational Model

Relational Keys and Integrity Constraints

  1. Superkey (): A subset of attributes such that no two distinct tuples satisfy .
  2. Candidate Key: A minimal superkey (removing any attribute destroys uniqueness).
  3. Primary Key (PRIMARY KEY): The chosen candidate key. By the Entity Integrity Constraint, no attribute of a primary key may contain a NULL value.
  4. Foreign Key (FOREIGN KEY): A set of attributes in a referencing relation whose values must either match the primary key (or candidate key) value of some tuple in a referenced relation , or be wholly NULL (if permitted). This rule is called Referential Integrity.
  5. Domain Constraint: Every attribute value must be an atomic value from its declared data type/domain (e.g., INT, VARCHAR(40), Marks BETWEEN 0 AND 100).

2.3.2 Converting ER model into relational model

Reducing an E-R schema into relational tables follows deterministic rules so that all entities, keys, cardinalities, and constraints are preserved:

Rules for E-R to Relational Schema Reduction
E-R ConstructRelational Mapping RulePrimary Key & Foreign Key
Strong Entity Set Create table with all simple attributes.Primary key of becomes PRIMARY KEY.
Composite AttributeFlatten into separate columns for each simple component (e.g., FirstName, LastName), omitting the composite parent name.Inherited from entity.
Multivalued Attribute of Create a separate table .Composite PK: ; is a FOREIGN KEY referencing .
Weak Entity Set (owner )Create table containing all attributes of plus .Composite PK: ; is FOREIGN KEY referencing (ON DELETE CASCADE). Do not make a separate table for the identifying relationship.
Binary Relationship Create a new junction table .Composite PK: ; each references its parent table as a FOREIGN KEY.
Binary Relationship Merge into the -side table (): add and descriptive attributes of as columns in . (Create a separate table only if participation is sparse and NULLs must be avoided.)PK of stays unchanged; in is a FOREIGN KEY referencing .
Binary Relationship Merge of one side into the other as a FOREIGN KEY with a UNIQUE constraint (prefer placing the FK on the total-participation side to eliminate NULLs).PK of chosen host table stays; added FK is UNIQUE and references the other table.
ISA (Specialization / Generalization)Option A (Three tables): Superclass table and subclass tables where is FK to . Option B (Subclass tables only): Valid if total & disjoint; each duplicates superclass attributes.Option A: in is both PK and FK referencing .
AggregationTreat the inner relationship table as a normal relation, then map the outer relationship using the primary key of the inner relationship table as a foreign key.PK of outer relationship combines FK to inner relationship table and outer entity PK (depending on cardinality).

Worked Out Examples

Example 2.1

2.1

Design the E-R components (entity sets, attributes, keys, weak entities, and mapping cardinalities) for a Hospital Management System:

Identifying Entity Sets and Attributes:

  1. Strong Entity Patient:
    • Primary Key: PatientID (underlined).
    • Composite Attribute: Name (FirstName, LastName).
    • Stored Simple Attribute: DOB; Derived Attribute (dashed ellipse): Age.
    • Multivalued Attribute (double ellipse): Phone.
  2. Strong Entity Doctor:
    • Primary Key: DocID (underlined).
    • Simple Attributes: Name, Specialization.
  3. Weak Entity MedicalBill:
    • Lacks a globally unique key (BillNo repeats across different patients), so it is a weak entity (double rectangle) owned by Patient.
    • Discriminator / Partial Key: BillNo (dashed underline).
    • Simple Attributes: Amount, PaidStatus.

Defining Relationships, Cardinalities, and Participation:

  1. Treats (between Doctor and Patient):
    • Mapping cardinality: (one doctor treats many patients; one patient sees many doctors).
    • Descriptive attributes on Treats: VisitDate, Diagnosis.
    • Participation: Partial on both sides (a newly registered patient may not yet have a visit, or a newly hired doctor may have zero patients).
  2. Has_Bill (identifying relationship between Patient and MedicalBill):
    • Drawn with a double diamond.
    • Mapping cardinality: (Patient MedicalBill ).
    • Participation of MedicalBill is total (double line): every bill must belong to an existing patient; participation of Patient is partial (a patient may have zero bills).
Answer:
  • Strong entities: Patient(PatientID PK, Name(FirstName, LastName), DOB, /Age, {Phone}) and Doctor(DocID PK, Name, Specialization).
  • Weak entity: MedicalBill(BillNo [partial key], Amount, PaidStatus) linked to Patient via identifying relationship Has_Bill with total participation on MedicalBill.
  • Binary relationship: Treats(Doctor, Patient) with cardinality and descriptive attributes VisitDate, Diagnosis.
Example 2.2

2.2

Convert the Hospital E-R model from Example 2.1 into a normalized relational database schema using the ER-to-Relational reduction rules, explicitly marking all PRIMARY KEY and FOREIGN KEY constraints. Also assume Doctor is specialized (disjoint, partial) into Surgeon(OTLicenseNo) and Physician(ClinicRoom).

Converting Strong Entities and Multivalued Attributes:

  1. Patient: flatten composite Name into FirstName, LastName; omit derived Age (or compute in a view); extract multivalued Phone into its own table:
    • Patient(PatientID [PK], FirstName, LastName, DOB)
    • Patient_Phone(PatientID [PK, FK -> Patient], Phone [PK])
  2. Doctor:
    • Doctor(DocID [PK], Name, Specialization)

Converting Weak Entity and Relationships:

  1. Weak entity MedicalBill ( identifying relationship Has_Bill merged into weak entity):
    • MedicalBill(PatientID [PK, FK -> Patient], BillNo [PK], Amount, PaidStatus)
  2. relationship Treats:
    • Treats(DocID [PK, FK -> Doctor], PatientID [PK, FK -> Patient], VisitDate [PK], Diagnosis) (Including VisitDate in the PK allows the same doctor to treat the same patient on multiple dates.)

Converting Specialization (Doctor Surgeon, Physician): Using the superclass + subclass tables method (Option A, always safe for partial specializations without duplicating superclass data):

  • Surgeon(DocID [PK, FK -> Doctor], OTLicenseNo)
  • Physician(DocID [PK, FK -> Doctor], ClinicRoom)
Answer:
  1. Patient(PatientID [PK], FirstName, LastName, DOB)
  2. Patient_Phone(PatientID [PK, FK -> Patient], Phone [PK])
  3. Doctor(DocID [PK], Name, Specialization)
  4. Surgeon(DocID [PK, FK -> Doctor], OTLicenseNo)
  5. Physician(DocID [PK, FK -> Doctor], ClinicRoom)
  6. MedicalBill(PatientID [PK, FK -> Patient], BillNo [PK], Amount, PaidStatus)
  7. Treats(DocID [PK, FK -> Doctor], PatientID [PK, FK -> Patient], VisitDate [PK], Diagnosis)
Example 2.3

2.3

Consider a relation schema with attributes whose only two candidate keys are and . Calculate the exact total number of superkeys of .

Applying the Definition of a Superkey: A subset is a superkey of if and only if contains at least one candidate key—that is, either:

  • , or
  • .

Counting Subsets by Inclusion–Exclusion:

  1. Number of subsets containing (the remaining attributes are free):
  1. Number of subsets containing (the remaining attributes are free):
  1. Number of subsets containing both and (i.e., , leaving free attributes ):
  1. Total number of superkeys:
Answer:

The relation has exactly superkeys.


Exercises

Practice Exercises — Data Models

Question 1

Compare the Hierarchical, Network, Relational, and Graph data models in terms of data representation, relationship handling ( vs. ), and data independence.

Data Representation and Relationship Handling:

  • Hierarchical Model: Organizes records as an inverted tree with strict parent-child links. Supports and directly; requires duplicating child records or introducing complex logical pointers.
  • Network Model: Organizes records as a directed graph using CODASYL owner-member sets. A member record can have multiple owners, directly supporting relationships.
  • Relational Model: Organizes data as mathematical tables (relations) of tuples and atomic attributes. Represents both and relationships declaratively via foreign keys and junction tables without physical pointers.
  • Graph Model: Organizes data as nodes, directed typed edges, and key-value properties. Relationships are stored directly as first-class edges, making multi-hop traversals constant-time per hop.

Data Independence Comparison:

  • Hierarchical and Network models offer low data independence because application programs must navigate physical pointer paths (GET NEXT, FIND OWNER).
  • Relational and Graph models provide high data independence because queries (SQL or graph query languages) specify what data is needed rather than how disk pointers are traversed.
Answer:

The Hierarchical model uses trees ( only, low data independence); the Network model uses pointer graphs ( supported via sets, low data independence); the Relational model uses tables and foreign keys (high data independence via declarative SQL); and the Graph model uses nodes and edges as first-class primitives (high data independence, optimized for multi-hop traversals).

Question 2

Distinguish between a strong entity set and a weak entity set with an example. Explain the terms identifying entity, partial key (discriminator), and total participation in this context.

Strong vs. Weak Entity Sets:

  • A strong entity set has sufficient attributes to form its own primary key and exists independently (e.g., Course(CourseCode, Title)).
  • A weak entity set lacks sufficient attributes to form a primary key and depends on an identifying (owner) strong entity set for existence and identification (e.g., Section(SectionNo, Room, Time) belonging to Course).

Key Concepts for Weak Entities:

  • Identifying Entity: The strong entity set (Course) that owns and provides part of the primary key for the weak entity set (Section).
  • Partial Key (Discriminator): The attribute(s) of the weak entity set (SectionNo) that uniquely distinguish weak entities associated with the same owner entity (underlined with a dashed line). The full primary key is CourseCode + SectionNo.
  • Total Participation: Every weak entity instance must be associated with an owner entity through the identifying relationship (drawn as a double line from the weak entity to the double-diamond identifying relationship).
Answer:

A strong entity has its own primary key and independent existence, whereas a weak entity depends on an identifying strong entity and combines the owner's primary key with its partial key (discriminator) to form a composite primary key, exhibiting total participation in the identifying relationship.

Question 3

Explain specialization, generalization, and aggregation in the Extended E-R (EER) model with suitable examples and constraints.

Specialization and Generalization:

  • Specialization (Top-Down): Splitting a general superclass entity set into more specific subclasses based on distinguishing attributes or roles—e.g., Employee specialized into Engineer(Specialty) and Accountant(CPA_No).
  • Generalization (Bottom-Up): Abstracting common attributes of multiple entity sets into a single shared superclass—e.g., SavingAccount and CheckingAccount generalized into Account(AccNo, Balance).
  • Constraints: Both use the ISA triangle and are governed by disjointness (disjoint vs. overlapping) and completeness (total vs. partial).

Aggregation:

  • Aggregation treats a relationship set together with its participating entity sets as a single abstract higher-level entity so it can participate in another relationship.
  • Example: In an Employee works_on Project relationship, if an Equipment item is assigned specifically to that work assignment rather than independently to the employee or project, Works_On is aggregated and linked via Uses to Equipment.
Answer:

Specialization (top-down) refines a superclass into subclasses, generalization (bottom-up) merges common entity sets into a superclass (both subject to disjoint/overlapping and total/partial constraints), and aggregation abstracts a relationship and its entities into a composite unit that can participate in another relationship.

Question 4

Convert the following University E-R specification into relational schemas, clearly marking primary keys (PK) and foreign keys (FK):

Mapping Strong Entities and Multivalued Attributes:

  1. Department(DeptCode [PK], DeptName, Building)
  2. Instructor(InstID [PK], Name)
  3. Multivalued Qualifications: Instructor_Qual(InstID [PK, FK -> Instructor], Qualification [PK])
  4. Course(CourseID [PK], Title, Credits)

Mapping , , and Relationships:

  1. Offers (Department — Course): Merge DeptCode into the -side (Course):
    • Course(CourseID [PK], Title, Credits, DeptCode [FK -> Department, NOT NULL])
  2. Teaches: Create a junction table:
    • Teaches(InstID [PK, FK -> Instructor], CourseID [PK, FK -> Course], Semester [PK])
  3. Heads (total participation on Department): Place HeadInstID in Department with UNIQUE and NOT NULL so no NULLs occur:
    • Department(DeptCode [PK], DeptName, Building, HeadInstID [UNIQUE, NOT NULL, FK -> Instructor])
Answer:
  • Department(DeptCode [PK], DeptName, Building, HeadInstID [UNIQUE, NOT NULL, FK -> Instructor])
  • Instructor(InstID [PK], Name)
  • Instructor_Qual(InstID [PK, FK -> Instructor], Qualification [PK])
  • Course(CourseID [PK], Title, Credits, DeptCode [NOT NULL, FK -> Department])
  • Teaches(InstID [PK, FK -> Instructor], CourseID [PK, FK -> Course], Semester [PK])
Question 5

A relation schema has attributes and exactly two candidate keys: and .

  1. Determine the total number of superkeys of .
  2. Explain the difference between Entity Integrity and Referential Integrity in the relational model.

Counting the Superkeys of : A subset is a superkey if or :

  1. Subsets containing ( remaining attributes ): .
  2. Subsets containing ( remaining attributes ): .
  3. Subsets containing both and , i.e., ( remaining attributes ): .
  4. By inclusion–exclusion:

Entity Integrity vs. Referential Integrity:

  • Entity Integrity: Requires that no primary key attribute in any base relation can ever hold a NULL value, ensuring every tuple is uniquely identifiable.
  • Referential Integrity: Requires that a foreign key value in a referencing relation must either match an existing candidate/primary key value in the referenced relation or be wholly NULL (if nulls are allowed).
Answer:
  1. Total number of superkeys = .
  2. Entity integrity forbids NULL values in any primary key attribute, whereas referential integrity ensures every non-null foreign key value matches a valid primary/candidate key tuple in the referenced table.
← IntroductionRelational Query Languages →