Relational Algebra and SQL Queries for Banking Database

Given Schema

• Customer(<u>CustomerID</u>, CustomerName, Address, Phone, Email)
• Owns(<u>CustomerID</u>, <u>AccountNumber</u>)
• Account(<u>AccountNumber</u>, AccountType, Balance)

a. Display name of all customers who live in 'Kathmandu'

Relational Algebra

π CustomerName (σ Address = 'Kathmandu' (Customer))

Steps:

1. Apply selection (σ) on Customer table where Address = 'Kathmandu'
2. Apply projection (π) to retrieve only CustomerName

SQL Query

SELECT CustomerName
FROM Customer
WHERE Address = 'Kathmandu';

b. Count total number of customers

Relational Algebra

ℱ COUNT(CustomerID) (Customer)

Note: Aggregate functions use the aggregate operator ℱ (script F) in relational algebra.

SQL Query

SELECT COUNT(CustomerID) AS TotalCustomers
FROM Customer;

c. Find name of customers who have balance greater than or equal to 100000

Relational Algebra

π CustomerName (Customer ⋈ Owns ⋈ (σ Balance >= 100000 (Account)))

Steps:

1. Apply selection (σ) on Account table where Balance >= 100000
2. Natural join (⋈) the result with Owns on AccountNumber
3. Natural join (⋈) the result with Customer on CustomerID
4. Apply projection (π) to retrieve only CustomerName

SQL Query

SELECT DISTINCT C.CustomerName
FROM Customer C
JOIN Owns O ON C.CustomerID = O.CustomerID
JOIN Account A ON O.AccountNumber = A.AccountNumber
WHERE A.Balance >= 100000;

DISTINCT is used to avoid duplicate customer names if a customer owns multiple qualifying accounts.

d. Find average balance of each account type

Relational Algebra

AccountType ℱ AVG(Balance) (Account)

The attribute before ℱ denotes the grouping attribute (GROUP BY equivalent).

SQL Query

SELECT AccountType, AVG(Balance) AS AverageBalance
FROM Account
GROUP BY AccountType;

Summary Table

Normalization in Database Design

Definition of Normalization

Normalization is the process of organizing the attributes and tables of a relational database to minimize data redundancy and dependency. It involves decomposing a large, poorly structured table into smaller, well-structured tables while preserving data integrity and relationships. The process is guided by a series of rules called Normal Forms (NF).

Why Normalization is Important in Database Design

Normalization is important for the following reasons:

Types of Anomalies (Before Normalization)

Consider the following unnormalized table:

• Update Anomaly: If Dr. Sharma's name changes, it must be updated in multiple rows.
• Insertion Anomaly: A new course cannot be added without a student.
• Deletion Anomaly: Deleting Sita's record also deletes information about Course C01.

Normal Forms

1. First Normal Form (1NF)

Definition: A relation is in 1NF if:

• All attributes contain only atomic (indivisible) values.
• Each column contains values of a single type.
• Each row is unique (has a primary key).
• There are no repeating groups or multi-valued attributes.

Example of a table NOT in 1NF:

Here, the Courses column contains multiple values, which violates 1NF.

Converting to 1NF:

Now each cell has an atomic value. This table is in 1NF. Primary Key: (StudentID, Course)

2. Second Normal Form (2NF)

Definition: A relation is in 2NF if:

• It is already in 1NF.
• Every non-key attribute is fully functionally dependent on the entire primary key (no partial dependency).

Partial Dependency: A non-key attribute depends on only a part of a composite primary key.

Example of a table in 1NF but NOT in 2NF:

Primary Key: (StudentID, Course)

Functional Dependencies:

• (StudentID, Course) --> InstructorName (full dependency - OK)
• StudentID --> StudentName (partial dependency - VIOLATION)

StudentName depends only on StudentID, not on the full composite key.

Converting to 2NF (Remove partial dependencies):

Student Table:

Enrollment Table:

Now all non-key attributes are fully dependent on the primary key. Both tables are in 2NF.

3. Third Normal Form (3NF)

Definition: A relation is in 3NF if:

• It is already in 2NF.
• There is no transitive dependency of non-key attributes on the primary key.

Transitive Dependency: A non-key attribute depends on another non-key attribute, which in turn depends on the primary key. If A --> B and B --> C, then A --> C is a transitive dependency.

Example of a table in 2NF but NOT in 3NF:

Primary Key: (StudentID, Course)

Functional Dependencies:

• (StudentID, Course) --> InstructorID (full dependency - OK)
• InstructorID --> InstructorName (transitive dependency - VIOLATION)

Here: (StudentID, Course) --> InstructorID --> InstructorName

InstructorName depends on InstructorID (a non-key attribute), not directly on the primary key.

Converting to 3NF (Remove transitive dependencies):

Enrollment Table:

Instructor Table:

The transitive dependency is now gone. InstructorName is stored exactly once, in the table whose key it actually depends on, while the Enrollment table keeps only InstructorID as a foreign key. Both tables are in 3NF, and the original information can be recovered without loss by joining them on InstructorID.

The anomalies listed at the beginning disappear with it. Correcting Dr. Sharma's name now changes a single row of the Instructor table, so there is no update anomaly. A new instructor can be recorded before any student enrols under that instructor, so there is no insertion anomaly. Deleting the last enrolment for a course no longer erases the instructor's details, so there is no deletion anomaly.

Summary of the Three Normal Forms

Normalization therefore moves a design from a single wide table full of repeated facts towards a set of narrow tables in which every fact is stored once and depends on the key, the whole key and nothing but the key. Stricter forms such as BCNF and 4NF handle the remaining special cases, but 3NF is normally sufficient for practical database design, and a controlled amount of denormalization is added afterwards only where read performance demands it.

Two-Phase Locking (2-PL)

Definition

A transaction is said to follow the two-phase locking (2-PL) protocol if all locking operations (read-lock, write-lock) precede the first unlock operation in the transaction. Locking is an operation which secures permission to read or permission to write a data item. Two-phase locking is a process used to gain ownership of shared resources in a way that guarantees conflict serializable schedules. Note that basic two-phase locking does not by itself remove the possibility of deadlock: two transactions can each hold a lock the other is waiting for. Only the conservative variant, which acquires every lock before execution begins, is deadlock free.

Such a transaction is divided into exactly two phases:

The three activities in the two-phase update algorithm are:

1. Lock Acquisition
2. Modification of Data
3. Release of Lock

Types of Locks in Two-Phase Locking

The two main modes in which a data item may be locked are:

1. Exclusive (X) Mode - The data item can be both read and written. Only one transaction can hold an exclusive lock on an item at a time.
2. Shared (S) Mode - The data item can only be read. Multiple transactions can hold shared locks on the same item simultaneously.

Categories of Two-Phase Locking

1. Basic Two-Phase Locking (Basic 2-PL)

• A transaction follows the two-phase protocol: it has a growing phase where locks are acquired and a shrinking phase where locks are released.
• Once the transaction releases even one lock, it enters the shrinking phase and cannot acquire any new locks.
• Problem: It does not prevent dirty reads or cascading rollbacks, because locks may be released before the transaction commits.

|-- Growing Phase --|-- Shrinking Phase --|
  Acquire locks         Release locks
       ^
    Lock Point

2. Conservative Two-Phase Locking (Static 2-PL)

• A transaction must lock all the data items it needs before it begins execution (i.e., before any read or write operation is performed).
• If any required lock cannot be obtained, the transaction does not lock any item at all and waits.
• Advantage: Prevents deadlock because all resources are acquired upfront.
• Disadvantage: It is difficult to know in advance all the data items that will be needed; this reduces concurrency.

3. Strict Two-Phase Locking (Strict 2-PL)

• In addition to following basic 2-PL, a transaction must hold all its Exclusive (X) locks until after it commits or aborts.
• Shared (S) locks may be released before the transaction commits.
• Advantage: Prevents dirty reads and cascading rollbacks because no other transaction can read or write an item that has been exclusively locked until the holding transaction commits.
• Advantage: Ensures strict schedules, which are easier to recover from.

4. Rigorous Two-Phase Locking (Rigorous 2-PL)

• This requires, in addition to basic 2-PL, that all Exclusive (X) and Shared (S) locks held by the transaction be released only after the transaction commits or aborts.
• The key difference between Strict 2-PL and Rigorous 2-PL:
  • Strict 2-PL holds only X locks until commit.
  • Rigorous 2-PL holds both X and S locks until commit, making it more restrictive.
• Advantage: Produces serializable and easily recoverable schedules.
• Disadvantage: Lower concurrency because locks are held for a longer duration.

Summary Comparison Table

Lock Conversion

When lock conversion is allowed in two-phase locking, a transaction can change the mode of a lock it already holds on a data item. The rules are:

• Upgrading (S lock → X lock): Upgrading of a lock from Shared to Exclusive must be done during the growing (expanding) phase only.
• Downgrading (X lock → S lock): Downgrading of a lock from Exclusive to Shared must be done during the shrinking phase only.

This ensures the two-phase property is still maintained while allowing more flexibility in lock management.

Example: A transaction first reads a data item (acquires S lock), and later decides to write it. It can upgrade the S lock to an X lock during the growing phase. When it no longer needs to write but still needs to read, it can downgrade the X lock to an S lock during the shrinking phase.

Fat File System and Advantages of DBMS Approach

Part 1: Fat File System (File Processing System)

A fat file system (also called a file processing system or flat file system) is a traditional approach to data management where data is stored in separate, independent files managed directly by individual application programs. Each application maintains its own set of files, and there is no centralized control or management of the data.

Key characteristics:

• Data is stored in isolated files with no central coordination
• Each application program defines and manages its own data files
• Data is accessed through application-specific programs
• There is no standard interface for accessing or sharing data across applications

Major problems of the fat file system:

• Data redundancy and inconsistency - same data stored in multiple files
• Difficulty in accessing data - no flexible query mechanism
• Data isolation - data scattered in various files and formats
• Integrity problems - difficult to enforce constraints
• Atomicity problems - difficult to ensure all-or-nothing operations
• Concurrent access anomalies - multiple users accessing same file causes problems
• Security problems - difficult to enforce access control

Part 2: Advantages of Using DBMS Approach

A good DBMS provides the following advantages:

1. Providing Backup and Recovery

The backup and recovery subsystem of a DBMS is responsible for recovery. For example, if the computer fails in the middle of a complex update transaction, the recovery system ensures the database is restored to the state it was in before the transaction started executing. Disk backup is also necessary in case of catastrophic disk failure.

2. Providing Multiple User Interfaces

Many types of users with varying levels of technical knowledge use a database. A DBMS provides a variety of user interfaces including:

• Apps for mobile users
• Query language for casual users
• Programming language interfaces for application programmers
• Forms and commands for parametric users
• Menu-driven and natural language interfaces for standalone users
• Graphical User Interfaces (GUIs)

3. Flexibility

It may be necessary to change the structure of a database as requirements change. Modern DBMS allow certain types of evolutionary changes to the structure of the database without affecting existing application programs. For example, a new user group may emerge that needs additional information, requiring new files or extended data elements.

4. Availability of Up-to-Date Information

As soon as a user's update is applied to the database, all other users can immediately see that update. This availability of up-to-date information is essential for many transaction-processing applications such as reservation systems or banking databases.

5. Reduced Data Redundancy and Inconsistency

By centralizing data management, DBMS minimizes duplication of data across multiple files, thereby reducing inconsistency.

6. Enforcing Integrity Constraints

DBMS allows integrity constraints to be defined and automatically enforced, ensuring data accuracy and validity.

In summary, the DBMS approach overcomes all the major drawbacks of the fat file system by providing centralized, controlled, secure, and flexible data management with support for multiple users and recovery mechanisms.

Conceptual Data Model and Types of Attributes in ER Diagram

Conceptual Data Model (2 marks)

A conceptual data model is a collection of concepts used to describe the structure of a database at a high level of abstraction, independent of any physical implementation. It provides the necessary means to achieve abstraction and acts as a conceptual tool for describing data and the relationships among data.

• It describes data at the logical and view level.
• It focuses on what data is stored rather than how it is stored.
• The most widely used conceptual data model is the Entity-Relationship (ER) Model.

The ER model describes the design of a database in terms of entities and relationships among them. An entity is an object in the real world with a set of attributes (e.g., customer_id, customer_name, customer_address).

Types of Attributes in ER Diagram (3 marks)

An attribute is a property or characteristic that describes an entity. The following types of attributes are used in ER diagrams:

1. Simple (Atomic) Attribute

• An attribute that cannot be divided into smaller sub-parts.
• It holds a single value.
• Example: Roll_No, Age
• Represented by an oval in ER diagram.

2. Composite Attribute

• An attribute that can be divided into smaller sub-parts, each representing a more basic attribute.
• Example: Name can be divided into First_Name, Middle_Name, Last_Name.
• Represented by an oval connected to smaller ovals.

3. Single-Valued Attribute

• An attribute that holds only one value for a particular entity.
• Example: Date_of_Birth, SSN (Social Security Number).

4. Multi-Valued Attribute

• An attribute that can hold more than one value for a single entity.
• Example: Phone_Number (a person may have multiple phone numbers).
• Represented by a double oval in ER diagram.

5. Derived Attribute

• An attribute whose value can be derived or computed from another attribute.
• Example: Age can be derived from Date_of_Birth.
• Represented by a dashed oval in ER diagram.

6. Key Attribute

• An attribute that uniquely identifies each entity in an entity set.
• Example: Student_ID, Employee_ID.
• Represented by an oval with the attribute name underlined.

7. Null Attribute

• An attribute that may have a null (unknown or not applicable) value for some entities.
• Example: Middle_Name may be null for some persons.

Summary Table

Relational Model

Definition

The relational model is a data model that represents data in the form of relations (tables). It was proposed by E.F. Codd and is the foundation of relational database management systems (RDBMS). In this model, all data is logically structured as two-dimensional tables consisting of rows and columns. SQL uses the terms table, row, and column for the formal relational model terms relation, tuple, and attribute respectively.

Key Terms

1. Domain

A domain is a set of atomic (indivisible) values from which the actual values of an attribute are drawn.

• Domain constraints specify that within each tuple, the value of each attribute A must be an atomic value from the domain dom(A).
• Data types associated with domains include:
  • Numeric types: integer, short integer, long integer, float, double
  • Other types: characters, Booleans, fixed-length strings, etc.

Example: The domain of an attribute "Age" could be the set of positive integers.

2. Attribute

An attribute is a named column of a relation that represents a specific property or characteristic of the entity being described.

• Each attribute A takes values from its corresponding domain dom(A).
• In SQL, attributes are referred to as columns.

Example: In a Student relation, Sname, Sid, and Address are attributes.

3. Tuple

A tuple is a single row in a relation that represents a single instance or record of the entity.

• An n-tuple t in a relation r(R) is denoted as:

$$t = \langle v_1, v_2, \ldots, v_n \rangle$$

where $v_i$ is the value corresponding to attribute $A_i$.

• Both t[Aᵢ] and t.Aᵢ refer to the value $v_i$ in tuple t for attribute $A_i$.
• In SQL, tuples are referred to as rows.

Example: <101, "Ram", "Kathmandu"> is a tuple in a Student relation.

4. Relation

A relation is a two-dimensional table with rows and columns used to represent data and the relationships among data.

• A relation r defined on a relation schema R(A₁, A₂, ..., Aₙ) is a set of n-tuples.
• Each tuple in the relation contains one value for each attribute drawn from its domain.
• A relation must satisfy integrity constraints such as domain constraints, key constraints, and referential integrity constraints.
• In SQL, a relation is referred to as a table.

Example:

This table is a relation with 2 tuples and 3 attributes.

Summary Table

Short Notes

a. Natural Join

Natural Join is a binary relational operation that combines two relations based on their common attributes (columns that share the same name and same data type).

Key Characteristics:

• It is denoted by the join symbol (⋈)
• The common attribute(s) must have the same name and same data type in both relations
• It automatically performs an equi-join on all matching attribute names
• It eliminates duplicate attributes from the result, keeping only one copy of the common column(s)
• It effectively combines selection and Cartesian product into a single operation

Example:

If relation R(A, B, C) and relation S(C, D, E) share attribute C:

R ⋈ S  produces tuples where R.C = S.C, with C appearing only once
Result schema: (A, B, C, D, E)

Important Note on Lossless Decomposition:

A decomposition {R1, R2, R3} of a relation R is called a lossless decomposition if the natural join of R1, R2, R3 produces exactly the original relation R.

However, if a "fat relation" (one with too many grouped attributes) is split and then rejoined using natural join, it may generate more tuples than the original, making it impossible to recover the original table. This is known as a lossy decomposition.

b. Shadow Paging

Shadow paging is a recovery technique used in database systems to handle transaction failures without using a traditional log.

Basic Concept:

• The database is considered to be made up of a number of fixed-sized disk blocks (say n blocks)
• A directory with n entries is constructed, where the i-th entry points to the i-th database page on disk
• This directory is kept in main memory if it is not too large

How It Works:

During Transaction Execution:

1. The shadow directory is never modified during transaction execution
2. When a write operation is performed on a page:
   • A new copy of the modified page is created on a previously unused disk block
   • The old copy is NOT overwritten
3. For every page updated by the transaction, two versions are maintained:
   • Old version referenced by the shadow directory
   • New version referenced by the current directory

Recovery:

• On transaction failure: simply discard the current directory and restore the shadow directory. The old pages remain intact.
• On successful commit: the current directory replaces the shadow directory permanently.

Advantage:

Simple recovery with no need for redo/undo logs for the modified pages.

Disadvantage:

Requires extra disk space to maintain two versions of modified pages simultaneously.