Data Models
Open in the Padhaiko app2.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.
Categories of Data Models
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
| Data Model | Core Structure | Relationship Handling | Primary Use / Era |
|---|---|---|---|
| Entity-Relationship (E-R) | Entities, attributes, relationships | Explicit diamond sets with cardinalities | Conceptual database design & schema diagramming |
| Relational | Tables (relations), rows, columns | Foreign keys referencing primary keys | General-purpose OLTP & enterprise DBMS (PostgreSQL, MySQL, Oracle) |
| Object-Oriented | Classes, objects, OIDs, methods | Object references & class inheritance | CAD/CAM, multimedia, complex engineering data |
| Hierarchical | Inverted tree (parent-child segments) | Strictly and (single parent) | Legacy mainframe systems (IBM IMS), directory trees |
| Network | Directed graph (owner-member sets) | Supports via pointer chains | Legacy CODASYL databases; requires manual pointer navigation |
| Graph | Nodes, directed labeled edges, properties | First-class edges stored directly | Social 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).
| Construct | E-R Symbol | Meaning |
|---|---|---|
| Strong Entity Set | Single Rectangle | Independent object type with its own primary key |
| Weak Entity Set | Double Rectangle | Dependent entity lacking a sufficient primary key of its own |
| Attribute | Single Ellipse | Simple single-valued property of an entity or relationship |
| Key Attribute | Underlined text in Ellipse | Primary key attribute (dashed underline for weak partial key) |
| Multivalued Attribute | Double Ellipse | Attribute that can hold multiple values for one entity |
| Derived Attribute | Dashed Ellipse | Attribute computed from other stored attributes |
| Relationship Set | Single Diamond | Association among entity sets |
| Identifying Relationship | Double Diamond | Links a weak entity set to its identifying strong owner |
| Total Participation | Double Line | Every entity in the set must participate in at least one relationship |
2.2.1 Entities and entity sets
Entity and Entity Set
- Entity: A distinguishable "thing" or object in the real world that exists independently (e.g., a specific student Aarav, a specific course ENCT 301, or a bank account AC-104).
- Entity Set: A collection of entities of the same type that share the same properties or attributes (e.g., the set of all students
Student, or all coursesCourse). An entity set corresponds roughly to a class in OOP or a table in SQL, while an entity corresponds to a single object or row.
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:
| Type | Description | Example (Student) |
|---|---|---|
| Simple (Atomic) | Cannot be divided into smaller meaningful subparts. | RollNo, Gender |
| Composite | Can be subdivided into smaller component attributes with independent meanings. | Name (FirstName, MiddleName, LastName); Address (Ward, City, District) |
| Single-Valued | Holds at most one value for a single entity instance. | DateOfBirth, RollNo |
| Multivalued | Can hold multiple values simultaneously for a single entity instance. | PhoneNumbers, Skills |
| Stored | Explicitly stored in the database. | DateOfBirth |
| Derived | Computed dynamically from other stored attributes or system clock. | Age (derived from DateOfBirth and current date) |
| Null-Valued | Used 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:
- Superkey: Any set of one or more attributes that, taken collectively, uniquely identifies an entity in the entity set. If is a superkey, any superset of is also a superkey.
- Candidate Key: A minimal superkey—a superkey such that no proper subset of it is also a superkey. An entity set may have multiple candidate keys (e.g.,
RollNoandEmail). - Primary Key: The specific candidate key chosen by the database designer as the principal means of identifying entities within the entity set (underlined in an E-R diagram).
- Alternate (Secondary) Key: Any candidate key not selected as the primary key.
2.2.3 Strong and weak entity sets
| Aspect | Strong Entity Set | Weak Entity Set |
|---|---|---|
| Key Sufficiency | Possesses enough attributes to form a primary key on its own. | Does not have enough attributes to form a primary key independently. |
| Existence Dependence | Exists 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 Key | Its own primary key attribute(s). | Owner's primary key weak entity's discriminator. |
| Participation & Symbol | Single rectangle; participation in relationships may be partial or total. | Double rectangle; total participation (double line) in the double-diamond identifying relationship. |
| Example | Employee(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)
Relationship, Degree, Cardinality, and Participation
- Relationship: An association among two or more entities (e.g., student Aarav enrolls in course ENCT 301).
- Relationship Set: A mathematical relation on (possibly non-distinct) entity sets:
A relationship set may also carry descriptive attributes (e.g., Grade or EnrollDate on Enrolls).
- Degree of a Relationship Set: The number of participating entity sets—binary (degree , most common), ternary (degree , e.g.,
Supplier–Part–Project), or unary/recursive (degree , e.g.,EmployeemanagesEmployee).
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 :
| Cardinality | Meaning | E-R Arrow / Label | Example |
|---|---|---|---|
| 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
- Total Participation (Mandatory): Every entity in entity set must participate in at least one relationship in (drawn with a double line between and ). Example: Every
Loanmust have at least oneCustomerborrower. - Partial Participation (Optional): Only some entities in participate in (drawn with a single line). Example: Not every
Instructoradvises aProject.
2.2.5 Specialization, generalization and aggregation
Extended E-R (EER) features capture inheritance and higher-level abstractions:
| Aspect | Specialization (Top-Down) | Generalization (Bottom-Up) |
|---|---|---|
| Approach | Top-down refinement process. | Bottom-up synthesis process. |
| Direction | Starts 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. |
| Example | Person specialized into Student (RollNo, GPA) and Employee (EmpID, Salary). | Car and Truck generalized into Vehicle (RegNo, Price). |
| Notation | Triangle 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
- Disjointness Constraint:
- Disjoint: An entity can belong to at most one lower-level subclass (e.g., a
Vehicleis either aCaror aTruck, not both). - Overlapping: The same entity may belong to more than one subclass simultaneously (e.g., a
Personcan be both anEmployeeand aStudent).
- Disjoint: An entity can belong to at most one lower-level subclass (e.g., a
- 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.
- Classic Example:
Employeeworks_onProjectforms an aggregated relationshipWorks_On. AManagermonitors the(Employee, works_on, Project)pair—avoiding redundant ternary relationships when a manager oversees the work assignment itself.
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.
Core Terminology of the Relational Model
- Relation (Table): A two-dimensional table with a set of named columns and a set of rows. Formally, given domains , a relation is a subset of their Cartesian product:
- Tuple (Row / Record): A single ordered -tuple representing one entity or relationship instance. Tuple order in a relation is irrelevant (a relation is a mathematical set).
- Attribute (Column): A named property of a relation; every value in column must belong to its atomic domain (or be
NULLif permitted). - Degree (Arity): The number of attributes (columns) in a relation schema.
- Cardinality: The number of tuples (rows) currently stored in a relation instance.
Relational Keys and Integrity Constraints
- Superkey (): A subset of attributes such that no two distinct tuples satisfy .
- Candidate Key: A minimal superkey (removing any attribute destroys uniqueness).
- Primary Key (
PRIMARY KEY): The chosen candidate key. By the Entity Integrity Constraint, no attribute of a primary key may contain aNULLvalue. - 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 whollyNULL(if permitted). This rule is called Referential Integrity. - 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:
| E-R Construct | Relational Mapping Rule | Primary Key & Foreign Key |
|---|---|---|
| Strong Entity Set | Create table with all simple attributes. | Primary key of becomes PRIMARY KEY. |
| Composite Attribute | Flatten 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 . |
| Aggregation | Treat 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
2.1
Design the E-R components (entity sets, attributes, keys, weak entities, and mapping cardinalities) for a Hospital Management System:
- Each
Patienthas aPatientID,Name(First, Last),DOB, derivedAge, and multiplePhonenumbers. - Each
Doctorhas aDocID,Name, andSpecialization. - A
Doctortreats manyPatients, and aPatientcan consult manyDoctors; each consultation recordsVisitDateandDiagnosis. - A
Patientmay haveMedicalBillsidentified sequentially (BillNo: ) only within that patient's record, storingAmountandPaidStatus.
Identifying Entity Sets and Attributes:
- 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.
- Primary Key:
- Strong Entity
Doctor:- Primary Key:
DocID(underlined). - Simple Attributes:
Name,Specialization.
- Primary Key:
- Weak Entity
MedicalBill:- Lacks a globally unique key (
BillNorepeats across different patients), so it is a weak entity (double rectangle) owned byPatient. - Discriminator / Partial Key:
BillNo(dashed underline). - Simple Attributes:
Amount,PaidStatus.
- Lacks a globally unique key (
Defining Relationships, Cardinalities, and Participation:
Treats(betweenDoctorandPatient):- 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).
Has_Bill(identifying relationship betweenPatientandMedicalBill):- Drawn with a double diamond.
- Mapping cardinality: (
PatientMedicalBill). - Participation of
MedicalBillis total (double line): every bill must belong to an existing patient; participation ofPatientis partial (a patient may have zero bills).
- Strong entities:
Patient(PatientID PK, Name(FirstName, LastName), DOB, /Age, {Phone})andDoctor(DocID PK, Name, Specialization). - Weak entity:
MedicalBill(BillNo [partial key], Amount, PaidStatus)linked toPatientvia identifying relationshipHas_Billwith total participation onMedicalBill. - Binary relationship:
Treats(Doctor, Patient)with cardinality and descriptive attributesVisitDate,Diagnosis.
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:
Patient: flatten compositeNameintoFirstName,LastName; omit derivedAge(or compute in a view); extract multivaluedPhoneinto its own table:Patient(PatientID [PK], FirstName, LastName, DOB)Patient_Phone(PatientID [PK, FK -> Patient], Phone [PK])
Doctor:Doctor(DocID [PK], Name, Specialization)
Converting Weak Entity and Relationships:
- Weak entity
MedicalBill( identifying relationshipHas_Billmerged into weak entity):MedicalBill(PatientID [PK, FK -> Patient], BillNo [PK], Amount, PaidStatus)
- relationship
Treats:Treats(DocID [PK, FK -> Doctor], PatientID [PK, FK -> Patient], VisitDate [PK], Diagnosis)(IncludingVisitDatein 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)
Patient(PatientID [PK], FirstName, LastName, DOB)Patient_Phone(PatientID [PK, FK -> Patient], Phone [PK])Doctor(DocID [PK], Name, Specialization)Surgeon(DocID [PK, FK -> Doctor], OTLicenseNo)Physician(DocID [PK, FK -> Doctor], ClinicRoom)MedicalBill(PatientID [PK, FK -> Patient], BillNo [PK], Amount, PaidStatus)Treats(DocID [PK, FK -> Doctor], PatientID [PK, FK -> Patient], VisitDate [PK], Diagnosis)
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:
- Number of subsets containing (the remaining attributes are free):
- Number of subsets containing (the remaining attributes are free):
- Number of subsets containing both and (i.e., , leaving free attributes ):
- Total number of superkeys:
The relation has exactly superkeys.
Exercises
Practice Exercises — Data Models
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.
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).
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 toCourse).
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 isCourseCode + 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).
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.
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.,
Employeespecialized intoEngineer(Specialty)andAccountant(CPA_No). - Generalization (Bottom-Up): Abstracting common attributes of multiple entity sets into a single shared superclass—e.g.,
SavingAccountandCheckingAccountgeneralized intoAccount(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
Employeeworks_onProjectrelationship, if anEquipmentitem is assigned specifically to that work assignment rather than independently to the employee or project,Works_Onis aggregated and linked viaUsestoEquipment.
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.
Convert the following University E-R specification into relational schemas, clearly marking primary keys (PK) and foreign keys (FK):
Department(DeptCode [PK], DeptName, Building)Instructor(InstID [PK], Name, {Qualifications})whereQualificationsis multivaluedCourse(CourseID [PK], Title, Credits)Offers: relationship fromDepartmenttoCourse(every course is offered by exactly one department)Teaches: relationship betweenInstructorandCoursewith descriptive attributeSemesterHeads: relationship betweenInstructorandDepartment(every department has exactly one head)
Mapping Strong Entities and Multivalued Attributes:
Department(DeptCode [PK], DeptName, Building)Instructor(InstID [PK], Name)- Multivalued
Qualifications:Instructor_Qual(InstID [PK, FK -> Instructor], Qualification [PK]) Course(CourseID [PK], Title, Credits)
Mapping , , and Relationships:
-
Offers(Department — Course): MergeDeptCodeinto the -side (Course):Course(CourseID [PK], Title, Credits, DeptCode [FK -> Department, NOT NULL])
-
Teaches: Create a junction table:Teaches(InstID [PK, FK -> Instructor], CourseID [PK, FK -> Course], Semester [PK])
-
Heads(total participation onDepartment): PlaceHeadInstIDinDepartmentwithUNIQUEandNOT NULLso no NULLs occur:Department(DeptCode [PK], DeptName, Building, HeadInstID [UNIQUE, NOT NULL, FK -> Instructor])
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])
A relation schema has attributes and exactly two candidate keys: and .
- Determine the total number of superkeys of .
- Explain the difference between Entity Integrity and Referential Integrity in the relational model.
Counting the Superkeys of : A subset is a superkey if or :
- Subsets containing ( remaining attributes ): .
- Subsets containing ( remaining attributes ): .
- Subsets containing both and , i.e., ( remaining attributes ): .
- By inclusion–exclusion:
Entity Integrity vs. Referential Integrity:
- Entity Integrity: Requires that no primary key attribute in any base relation can ever hold a
NULLvalue, 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).
- Total number of superkeys = .
- Entity integrity forbids
NULLvalues 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.