To expand this note into a 100% comprehensive, standalone study guide, we need to inject the
precise mathematical definitions, step-by-step algorithms, and execution rules that your
university slides touch on.
We will systematically expand every module by adding concrete examples, mapping rules,
exact mathematical definitions, and the missing Transaction & Concurrency control
mechanisms. Read this document sequentially to lock down your database points.
The Complete Master Study Guide:
Fundamentals of Database Systems
Module 1: Database System Architecture & Concepts
1. Traditional File Systems vs. The DBMS Approach
In traditional file processing, each user department manages its own separate data files. This
structure introduces significant operational vulnerabilities:
● Data Redundancy: The same data item is duplicated across multiple files (e.g., a
student's address stored in both the registrar file and the dormitory file). This wastes
physical disk storage.
● Data Inconsistency: When a duplicated data item is modified in one file but remains
unchanged in another, the system enters an inconsistent state.
● Data Anomaly Types:
○ Insertion Anomaly: Inability to insert data about a new entity because it requires
the existence of another unrelated entity.
○ Deletion Anomaly: Deleting a record unintendedly destroys completely separate,
critical data.
○ Modification/Update Anomaly: Updating a value requires scanning and changing
hundreds of rows across multiple file formats, risking partial updates.
● Data-Program Dependence: The structural formatting of data is explicitly coded into the
application programs. If a file format changes (e.g., changing a zip code field from 4
digits to 5 digits), every software program interacting with that file must be manually
rewritten.
● Data-Program Isolation: A fundamental feature of a DBMS. Metadata (the description
of the database structure) is stored separately from the application programs inside a
centralized Data Dictionary or Catalog.
2. The Three-Schema Architecture (ANSI-SPARC)
To isolate user applications from the physical storage layer, the DBMS separates the database
structure into three distinct abstract layers.
● The External Level (View Schema):
○ The highest layer of abstraction, closest to end-users and developers.
○ Consists of multiple individual External Schemas or User Views.
○ Each view describes only the specific subset of data required by a specific user
group while hiding all other tables, columns, and relationships.
● The Conceptual Level (Logical Schema):
○ The middle layer of abstraction.
○ Describes the structural design of the entire database for the entire organization.
○ Defines all entities, data types, relationships, user operations, and integrity
constraints.
○ Crucial Rule: It completely abstracts away physical storage details. It focuses
purely on logic (e.g., "The Student table has an ID column of type INT").
● The Internal Level (Physical Schema):
○ The lowest layer of abstraction, closest to physical hardware.
○ Describes how data is physically laid out on the storage disk.
○ Defines file organization patterns, record block sizing, data compression
algorithms, encryption formats, and primary/secondary access paths (like B-Tree
indexes).
3. Data Independence Mechanics
Data independence is achieved through Mappings—the processes by which the DBMS
translates requests between the external, conceptual, and internal schemas.
+-----------------------------------+
| External Level (Views) |
+-----------------------------------+
||
[Logical Data Independence] -> Handled by External-to-Conceptual Mapping
||
+-----------------------------------+
| Conceptual Level (Logical) |
+-----------------------------------+
||
[Physical Data Independence] -> Handled by Conceptual-to-Internal Mapping
||
+-----------------------------------+
| Internal Level (Physical) |
+-----------------------------------+
● Logical Data Independence:
○ Definition: The capacity to alter the Conceptual Schema without forcing
changes to the External Schemas or the underlying application code.
○ Example: If you split a table into two tables or add a new column to support a
new department, you modify the External-to-Conceptual mapping so that older
user views continue to see the exact same unified data format they expect.
● Physical Data Independence:
○ Definition: The capacity to alter the Internal Schema without forcing changes to
the Conceptual Schema (and therefore, without altering External Views or
code).
○ Example: Replacing slow mechanical Hard Disk Drives (HDDs) with Solid-State
Drives (SSDs), migrating from a sequential file structure to a hashed access
path, or changing the physical indexing strategy. The logical definition of the
tables remains completely untouched.
4. Database Roles & Actor Classifications
The curriculum divides database personnel into two major categories based on their relationship
to the database software.
Category A: Actors on the Scene
People whose jobs directly involve designing, maintaining, administering, or using the
operational database content.
● Database Administrator (DBA): Responsible for authorizing database access,
monitoring system performance, acquiring hardware/software resources, managing
security policies, and executing backup/recovery plans.
● Database Designer (DBD): Responsible for identifying the data to be stored, choosing
appropriate structures, and establishing relations, keys, and constraints. They interview
end-users to create the Conceptual Schema before handing it over to the DBA.
● End-Users: The consumers who query, update, and generate reports from the
database.
○ Parametric/Naive Users: Tell the system what to do using pre-written, repetitive
menu options or interfaces (e.g., bank tellers, airline reservation agents).
○ Casual Users: Access the database occasionally but require different information
each time. They write custom, high-level ad-hoc queries using SQL.
○ Sophisticated/Standalone Users: Engineers, scientists, and analysts who
thoroughly understand the DBMS capabilities and build complex data structures
for their own specific analytical needs.
Category B: Workers Behind the Scene
People who develop the underlying software tools and hardware infrastructure; they do not
interact with your specific operational data.
● DBMS Designers & Implementers: The software engineers who build the actual
commercial DBMS engine (e.g., writing the code that compiles SQL queries, manages
buffer pools, or executes disk writes for Oracle, MySQL, or PostgreSQL).
● Tool Developers: Experts who create secondary software packages that integrate with
a DBMS to facilitate database design, performance monitoring, or graphical prototyping
(e.g., ERwin, phpMyAdmin).
● Operators & Maintenance Personnel: System administrators responsible for running
and maintaining the physical data center hardware, power grids, and network
connections.
Module 2: Conceptual Design (ER & EER Modeling)
1. Structural Components & Formal Semantics
● Entity Type: A collection of real-world objects that share the same attributes (e.g., all
individual employees belong to the Employee entity type). Represented by a Rectangle.
● Entity Instance: A specific, individual record within an entity type (e.g., an employee
named "Abebe" with ID 001).
● Weak Entity Type: An entity type that does not possess its own primary key attributes.
It cannot exist independently; its existence depends on an Identifying Owner Entity
Type.
○ It must participate in an Identifying Relationship with its owner.
○ Represented by a Double Rectangle.
○ Its unique identifier is formed by combining the primary key of the owner entity
with its own Partial Key / Discriminator (the attribute that distinguishes weak
entities belonging to the same owner, underlined with a dashed/dotted line).
2. Attribute Types & Mapping Symbols
● Simple (Atomic): An attribute that contains a single, indivisible value (e.g., Gender).
Represented by a standard Oval.
● Composite: An attribute composed of multiple sub-attributes, each with its own
independent meaning (e.g., Address composed of City, Sub-City, Woreda, House_No).
Represented by branching ovals out of a parent oval.
● Single-Valued: Holds exactly one value for a specific entity instance (e.g.,
Social_Security_Number).
● Multi-Valued: Can store a set of multiple values for a single entity instance (e.g., an
employee who speaks multiple Languages or holds multiple Certificates). Represented
by a Double Oval.
● Derived: An attribute whose value is computed dynamically from other attributes or
system states, meaning it is not permanently stored on disk (e.g., Total_Price calculated
from Quantity * Unit_Price). Represented by a Dashed Oval.
3. Structural Constraints on Relationships
● Relationship Type: A structural association among two or more entity types.
Represented by a Diamond.
● Degree of a Relationship Type: The number of participating entity types.
○ Binary: Degree 2 (Two entity types involved).
○ Ternary: Degree 3 (Three entity types involved simultaneously).
● Cardinality Ratio (Maximum Constraint): Specifies the maximum number of
relationship instances an individual entity can participate in:
○ $1:1$ (One-to-One): An employee can manage exactly one department; a
department is managed by exactly one employee.
○ $1:N$ (One-to-Many): A department can employ many employees, but an
employee can belong to only one department.
○ $M:N$ (Many-to-Many): A student can register for many courses; a course can
accept many students.
● Participation Constraint (Minimum Constraint):
○ Total Participation (Mandatory Existence): Every single instance in the entity
set must participate in the relationship. (e.g., Every Section must belong to a
Course). Represented by a Double Line.
○ Partial Participation (Optional Existence): Instances can exist without
participating in the relationship. (e.g., Not every Employee is required to manage
a Department). Represented by a Single Line.
4. Enhanced ER (EER) Extensions
EER introduces advanced modeling structures to handle complex data relationships.
● Subclass and Superclass: An entity type can be broken down into specialized
groupings. A subclass inherits every attribute and relationship of its parent superclass,
but adds its own specific local attributes. (e.g., Employee is a superclass; Secretary,
Engineer, and Manager are subclasses).
● Specialization: The process of breaking down a superclass into subclasses based on
distinguishing features (Top-down design approach).
● Generalization: The process of combining multiple entity types with shared
characteristics into a single, broader superclass (Bottom-up design approach).
● EER Constraints:
○ Disjointness Constraint: Specifies whether an instance of a superclass can
belong to more than one subclass simultaneously.
■ Disjoint ($d$): An instance can belong to at most one subclass. (e.g., An
employee can be a Temporary_Staff OR a Permanent_Staff, but never
both).
■ Overlapping ($o$): An instance can belong to multiple subclasses at the
same time. (e.g., A person at a university can be both a Student AND an
Employee).
○ Completeness Constraint: Specifies whether every instance in the superclass
must belong to at least one subclass.
■ Total Completeness (Double Line): Every superclass instance must be
a member of a subclass.
■ Partial Completeness (Single Line): A superclass instance can exist
without belonging to any subclass.
Module 3: Relational Model Constraints & Integrity Rules
1. Formal Relational Terminology
The Relational Model represents data as a collection of relations (informally called tables). You
must know the formal terms used in MCQ questions:
● Relation: A table structure containing rows and columns.
● Attribute: A named column header in a relation.
● Tuple: A horizontal row within a relation.
● Domain: The set of all valid, atomic values permitted for a specific attribute (e.g., a
domain for Age restricted to positive integers between 18 and 65).
● Degree (Arity): The total number of attributes (columns) in a relation schema.
● Cardinality: The total number of tuples (rows) currently stored in a relation instance.
2. Key Hierarchy Rules
● Superkey (SK): A set of one or more attributes whose combined values are guaranteed
to uniquely identify a tuple within a relation. It can include extra, non-essential columns
($SK \subseteq R$).
● Candidate Key (CK): A minimal superkey. It is a set of attributes that uniquely identifies
tuples, but if you remove even one attribute from it, it loses its uniqueness property. A
relation can possess multiple candidate keys.
● Primary Key (PK): The specific candidate key chosen by the database designer to
uniquely identify tuples throughout the relation.
● Foreign Key (FK): An attribute in a relation ($R_2$) that references a candidate key
(usually the primary key) of another relation ($R_1$), establishing a logical connection
between the two.
3. Core Relational Constraints
● Domain Constraint: The value of every attribute inside a tuple must be atomic and
must belong to the specified domain of that attribute.
● Key Constraint (Uniqueness): No two distinct tuples in a relation instance can ever
share identical values across their primary key attributes.
● Entity Integrity Rule: No attribute that forms any part of the primary key is permitted to
hold a NULL value.
● Referential Integrity Rule: If a tuple in relation $R_2$ contains a foreign key that
references relation $R_1$, the value of that foreign key must either:
1. Perfect match an active primary key value within a tuple in $R_1$.
2. Be completely NULL (provided the foreign key attribute is not part of $R_2$'s
own primary key).
Module 4: The 7-Step ER-to-Relational Mapping Algorithm
This algorithm governs exactly how a conceptual ER diagram transforms into concrete relational
tables. The exam will test how specific configurations impact table counts and foreign key
placement.
Step 1: Mapping of Regular (Strong) Entity Types
● Rule: Create a separate, dedicated relation $R$ for every regular entity type. Include all
simple attributes as columns.
● Composite Attribute Exception: Do not create a column for the parent composite
attribute name. Only map its individual, atomic sub-parts as columns. (e.g., If Name is
composed of First and Last, create columns First and Last. Throw away the word
Name).
● Key: Choose the entity's primary key as the relation's primary key.
Step 2: Mapping of Weak Entity Types
● Rule: Create a separate relation $R$ for every weak entity type. Include all its simple
and composite sub-attributes as columns.
● Foreign Key Placement: Identify the owner entity type. Take the primary key of the
owner entity and insert it into $R$ as a Foreign Key.
● Primary Key Formation: The primary key of the weak entity relation is a Composite
Key, formed by combining the owner's primary key with the weak entity's own partial key
(discriminator).
Step 3: Mapping of Binary $1:1$ Relationship Types
You have three approaches depending on participation constraints, but the exam focuses on the
most efficient one:
● Foreign Key Approach (Standard): Identify the relations participating in the
relationship ($S$ and $T$). Choose one relation (ideally the one with Total
Participation) and insert the primary key of the other relation into it as a Foreign Key.
● Example: An employee manages a department. Participation is total on the department
side (every department must have a manager). Therefore, place Employee_ID as a
Foreign Key inside the Department table.
Step 4: Mapping of Binary $1:N$ Relationship Types
● Rule: Identify the relation $S$ that represents the entity type on the "$N$" (Many) side
of the relationship.
● Action: Take the primary key of the relation on the "$1$" (One) side and insert it as a
Foreign Key inside relation $S$.
● Example: A department has many employees. The Employee table is the "$N$" side.
Therefore, place Department_No as a Foreign Key inside the Employee table. Never
place it on the "One" side, as that would create multi-valued cells.
Step 5: Mapping of Binary $M:N$ Relationship Types
● Rule: You must create a completely new relation $R$ (Relationship/Bridge Table)
to represent the relationship.
● Columns: Include the primary keys of both participating entity relations as foreign keys
inside $R$. Also add any attributes that were attached to the relationship diamond itself.
● Primary Key Formation: The primary key of this new relation is a Composite Key
formed by combining both foreign keys.
Step 6: Mapping of Multi-Valued Attributes
● Rule: You must create a completely new, separate relation $R$ specifically for the
multi-valued attribute.
● Columns: Include a column for the attribute values, along with a foreign key referencing
the primary key of the parent entity relation.
● Primary Key Formation: The primary key is a composite key consisting of all columns
combined.
● Example: If an employee has a multi-valued attribute Locations, create a table
Employee_Locations(Emp_ID, Location). Both columns together form the primary key.
Step 7: Mapping of $N$-ary Relationships (Ternary and Above)
● Rule: Create a separate, new relation $R$ to represent the relationship.
● Columns: Bring in the primary keys of all $N$ participating entities as foreign keys.
● Primary Key Formation: The combination of all foreign keys forms the composite
primary key.
Module 5: Functional Dependencies & Normalization
Normalization organizes a relational database schema to eliminate data redundancy and
prevent modification anomalies.
1. Functional Dependency (FD) Semantics
● Definition: A functional dependency $X \rightarrow Y$ between two sets of attributes
$X$ and $Y$ (which are subsets of a relation $R$) states that the values of the $X$
component textually and uniquely determine the values of the $Y$ component.
● If two tuples have identical values in column $X$, they must have identical values in
column $Y$.
● Determinant: The left-hand attribute set $X$.
● Dependent: The right-hand attribute set $Y$.
● Prime Attribute: An attribute that is a member of any candidate key for that relation.
● Non-Prime Attribute: An attribute that is not a member of any candidate key.
2. The Normal Forms Walkthrough
First Normal Form (1NF)
● Core Operational Test: A relation is in 1NF if and only if the domain of every attribute
contains only atomic (indivisible) values, and every attribute value in a tuple is a single
value from that domain.
● Violation: Tables containing multi-valued attributes, comma-separated lists, or nested
child tables inside cells.
● Remedy: Separate the multi-valued field into its own table (Step 6 of mapping) or create
new rows for each value in the list.
Second Normal Form (2NF)
● Core Operational Test: The relation must be in 1NF, and every non-prime attribute
must be fully functionally dependent on the primary key. No non-prime attribute can
exhibit a Partial Dependency.
● Partial Dependency Definition: A dependency where a non-prime attribute is
determined by a subset of a composite candidate key.
● Example of Violation: Consider a table Property_Dues(Project_No, Employee_No,
Employee_Name). The primary key is a composite key (Project_No, Employee_No).
However, Employee_Name is fully determined by just Employee_No alone. This is a
partial dependency.
● Remedy: Split the relation. Move the partial key attributes and their dependents into a
separate table: Employees(Employee_No, Employee_Name).
Third Normal Form (3NF)
● Core Operational Test: The relation must be in 2NF, and no non-prime attribute can
be transitively dependent on the primary key.
● Transitive Dependency Definition: A dependency chain where a non-prime attribute
determines another non-prime attribute ($PK \rightarrow X$ and $X \rightarrow Y$,
meaning $PK \rightarrow Y$ is transitive).
● Example of Violation: Consider a table Department(Emp_ID, Dept_No, Dept_Name).
The primary key is Emp_ID. Emp_ID determines Dept_No, and Dept_No determines
Dept_Name. Since Dept_No and Dept_Name are both non-prime fields, a transitive
dependency exists.
● Remedy: Remove the transitively dependent attributes and place them into their own
table: Departments(Dept_No, Dept_Name).
Boyce-Codd Normal Form (BCNF)
● Core Operational Test: A relation is in BCNF if and only if for every non-trivial
functional dependency $X \rightarrow Y$ that holds on it, $X$ is a Superkey.
● When does BCNF matter? It handles edge-case anomalies that arise when a table has
multiple overlapping composite candidate keys.
● Key Theoretical Truths: * BCNF is stricter than 3NF.
○ If a table is in BCNF, it is guaranteed to be in 3NF.
○ If a table is in 3NF, it might not be in BCNF.
Module 6: Structured Query Language (SQL) Execution
1. The 5 Formal Sub-Languages
● Data Definition Language (DDL): Used to construct, modify, or destroy database
structures (schemas, tables, views). These actions automatically commit changes to the
disk.
○ Commands: CREATE, ALTER, DROP, TRUNCATE (removes all data rows from
a table but keeps the column structure intact).
● Data Manipulation Language (DML): Used to populate, modify, or erase data rows
within existing structures.
○ Commands: INSERT, UPDATE, DELETE (removes specific rows based on a
condition; can be rolled back).
● Data Query Language (DQL): Used to read and retrieve stored data.
○ Command: SELECT.
● Data Control Language (DCL): Manages user access security and privileges.
○ Commands: GRANT (gives permissions), REVOKE (takes away permissions).
● Transaction Control Language (TCL): Manages the processing boundaries of
transactions.
○ Commands: COMMIT (saves changes permanently), ROLLBACK (reverts
changes), SAVEPOINT (sets a checkpoint to roll back to).
2. Logical Query Processing Sequence
When you execute an SQL query statement, the DBMS evaluates the clauses in a specific, rigid
logical order—not from top-to-bottom.
$$\text{编写顺序 (Syntax Order): } \texttt{SELECT} \rightarrow \texttt{FROM} \
rightarrow \texttt{WHERE} \rightarrow \texttt{GROUP BY} \rightarrow \
texttt{HAVING} \rightarrow \texttt{ORDER BY}$$
$$\text{执行顺序 (Execution Order): } \mathbf{FROM} \rightarrow \mathbf{WHERE} \
rightarrow \mathbf{GROUP BY} \rightarrow \mathbf{HAVING} \rightarrow \
mathbf{SELECT} \rightarrow \mathbf{ORDER BY}$$
● WHERE vs. HAVING Operational Rule:
○ WHERE filters incoming raw record tuples before the system aggregates them. It
cannot contain aggregate functions (SUM, AVG, COUNT, MAX, MIN).
○ HAVING filters compiled group summaries after a GROUP BY clause has run. It
is designed explicitly to filter based on aggregate conditions.
3. Join Behaviors
● INNER JOIN: Returns rows only when the join condition evaluates to true across both
tables. Mismatched rows are excluded.
● LEFT OUTER JOIN: Returns every row from the left table. If a row has no matching
counterpart in the right table, the right table's columns are padded with NULL values.
● RIGHT OUTER JOIN: Returns every row from the right table, padding missing columns
on the left with NULL values.
4. Database Views
● Definition: A View is a virtual table. It does not physically store its own copy of data
records on disk. Instead, it stores a pre-compiled SELECT query string.
● When a user queries a view, the DBMS dynamically executes the underlying query to
pull data from the source tables.
● Benefits: Restricts access to sensitive columns (security), simplifies complex multi-table
joins for end-users, and provides logical data independence.
Module 7: Transaction Processing & Concurrency
Control
1. The ACID Properties
A Transaction is an execution sequence containing one or more SQL commands that forms a
single logical unit of database work. It must enforce all four ACID properties:
● Atomicity: The "All-or-Nothing" property. The DBMS guarantees that either all
database modifications within the transaction commit successfully, or the entire
transaction is aborted and rolled back to its original state.
● Consistency: A transaction must transform the database from one valid, consistent
state to another, ensuring that all explicit schema constraints (data types, unique
attributes, foreign keys) are maintained.
● Isolation: Concurrent transactions must execute without cross-interference. The
uncommitted, intermediate changes made by a running transaction must remain
completely invisible to all other concurrent transactions.
● Durability: Once a transaction commits, its modifications are permanently recorded in
non-volatile storage (the disk). These changes cannot be lost, even if a total system
crash or power failure occurs immediately after.
2. Concurrency Anomalies
When multiple transactions execute concurrently and access the same data elements without
lock protection, three major conflicts can occur:
● The Dirty Read (Reading Uncommitted Data):
○ Scenario: Transaction 1 modifies a row's value. Transaction 2 reads that
modified value. Transaction 1 then fails and issues a ROLLBACK. Transaction 2
is now operating with data that technically never existed in the database.
● The Lost Update Problem:
○ Scenario: Transaction 1 and Transaction 2 read the same account balance
($100$) concurrently. Transaction 1 subtracts $\$20$ and updates the balance to
$\$80$. Simultaneously, Transaction 2 adds $\$50$ to the original balance and
writes back $\$150$. Transaction 2's write completely overwrites and obliterates
the update made by Transaction 1.
● The Unrepeatable Read:
○ Scenario: Transaction 1 reads a row value. Transaction 2 modifies or deletes that
row and issues a COMMIT. Transaction 1 re-reads the same row within its own
transaction boundary and discovers the value has changed or vanished.
3. Concurrency Remediation: Two-Phase Locking (2PL)
To prevent these anomalies and ensure serializability, databases use lock managers. The
standard protocol tested on the exit exam is Two-Phase Locking (2PL).
● Lock Types:
1. Shared Lock ($S$): Placed on data items for read-only access. Multiple
transactions can hold shared locks on the same item concurrently.
2. Exclusive Lock ($X$): Placed on data items for write/update operations. Only one
transaction can hold an exclusive lock on an item, blocking all other read or write
requests.
● The 2PL Protocol Rules:
1. The Growing Phase: A transaction can acquire new locks of any type but is
strictly forbidden from releasing any locks it currently holds.
2. The Shrinking Phase: A transaction can release its existing locks but is strictly
forbidden from acquiring any new locks.
● Crucial Property: 2PL guarantees serializability (meaning concurrent transactions
produce the same results as running them sequentially), but it does not prevent
Deadlocks (situations where two transactions are stuck waiting for locks held by each
other).
Print this complete guide or save it to your study folder. It maps directly to the conceptual
architecture, rules, and structures evaluated on the MoE exam blueprint. Use your 2-week
schedule to drill this material, and you will be completely prepared for the Database Systems
section. Good luck!