DBMS

Resources

• https://www.youtube.com/watch?v=khKoJUpcXUE&list=PLG9aCp4uE-s0bu-I8fgDXXhVLO4qVROGy&index=1&t=1825s&ab_channel=UnacademyComputerScience

Introduction

Database: The collection of data, usually referred to as the database, contains information relevant to an enterprise.

Database-management System: A database-management system (DBMS) is a collection of interrelated data and a set of programs to access (retrieve, insertion, deletion, update) those data.

Goal of DBMS

• Providing a way to store and retrieve database information that is both convenient (easy) and efficient (quick, correct).

• Ensuring the safety of the information.

File System:

Disadvantage of File System

• Data redundancy and inconsistency

• Difficulty in accessing data

• Data Isolation

• Integrity Problem: applying constraints

• Atomicity Problem

• Concurrent-Access Anomalies

• Security Problem

Database Architecture

Schema: The overall design of the database is called the database schema.

Instance: The collection of information stored in the database at a particular moment is called an instance of the database.

Database Language

• Data-Definition Model (DDL): for Schema

• Data-Manipulation Language (DML) : for Instance
  • Procedural DMLs: Require a user to specify what data are needed and how to get this data
  • Non-procedurals (Declarative): Require a user to specify what data are needed without specifying how to get those data. Example: SQL

Database Users and Admins

• Naive users : Accessing database without even knowing

• Application programmers: Accessing databasing using some statements

• Sophisticated users: Accessing database using query

• Specialized users: Database design or who makes DBMS

• Database Administrator: Maintaining database, authentication, authorization, clean up

View of Data

1. Physical Level: Describes how data is physically stored in the database. The Database Administrators(DBA) decide that which data should be kept at which particular disk drive, how the data has to be fragmented, where it has to be stored etc. It ensures efficient data storage and retrieval.

2. Logical/Conceptual Level: Describes the logical structure of the entire database. It focuses on designing how data is organized conceptually.

3. View Level: Defines how data is viewed by specific users or applications. It enhances security and ease of access by showing only relevant data to users.

3 Levels of Data Abstraction: Data Abstraction refers to the process of hiding irrelevant details from the user.

Database System Structure

The functional components of a database system

1. Storage manager: The storage manager is responsible for storing, retrieving, and updating the database

2. Query processor components: The interactive query processor helps the database system to simplify and facilitate access to data

2-tier and 3-tier database

Database Designing

Data Models: A collection of conceptual tools for describing data, data relationship, data semantics and consistency constraints.

Data Models types:

1. Entity-Relationship Model: The entity-relationship (E-R) data model consists of collection of basic objects, called entities and of relationship among these objects.

2. Relational Model: The relational model is a collection of tables to represent both data and the relationship among these data.

3. Object-oriented data model

4. Network data model

5. Hierarchical data model

Database design:

1. Requirement Analysis

2. Conceptual Database Design: E-R Model

3. Schema Refinement: Finetuning the relations, Normalization

4. Logical database design: Relational Modelling

5. Physical database design: Decide the data structure to store database (storage), indexing

6. Security Design: Authentication, authorization

The Entity-Relationship Model

The Entity-Relationship data model consists of collection of objects called entities and of relationship among these objects.

Entity: Object in the real world that is distinguishable from another object.

Entity-set: A collection of similar entities called an entity set.

Attribute: An entity is described using a set of attributes.

Domain: A unique set of values permitted for an attribute.

Relationship: An association among two or more entities.

Relationship-set: A set of similar relationship.

Key: An attribute or set of attributes whose values can uniquely identify an entity in a set.

E-R Diagram: An Entity-Relationship (E-R) Diagram is a visual/graphical representation of the data model for a system. It uses specific symbols to depict the entities relationships , and attributes in a database.

Types of Relationships

1. Unary: Relationship between entities of same entity set.

2. Binary: Relationship between entities of two entity-sets.

3. Ternary: Relationship between entities of three entity sets.

Descriptive attribute: Attribute of relationship.

Mapping Cardinality: The maximum number of relationship in which an entity can participate.

Participation Constraints: Specifies the presence of an entity when it is related to another entity in a relationship type.

Weak and Strong Entities

• Weak Entity: A weak entity is an entity that cannot be uniquely identified by its attributes alone.

• Strong Entity: A strong entity is an entity that can be uniquely identified by its own attributes without relying on other entity.

Extended E-R Features

• Specialization

• Generalization

• Higher-and-lower-level entity sets

• Attribute inheritance

• Aggregation

Specialization: The process of designating subgroupings withing an entity sets is called specialization.

Higher and lower level entity sets:

Higher-level entity sets: A generalized entity set that represents common attributes of multiple specialized entities.

Lower-level entity sets: A specialized entity set that represents a subset of the higher-level entity with additional, specific attributes.

Generalization : This commonality can be expressed by generalization, which is a containment relationship that exists between a higher-level-entity-set and one or more lower-level entity sets.

• Total generalization/specialization: Each higher-level entity must belong to a lower-level entity set.

• Partial generalization/specialization: Some higher-level entities may not belong to any lower level entity.

Attribute Inheritance: Attribute inheritance refers to the concept in generalization and specialization where lower-level entities (subclasses) inherit the attributes of their higher-level entity (superclass).

Aggregation: Aggregation is an abstraction used in Entity-Relationship (E-R) diagrams to represent a relationship between a relationship and another entity.

Attributes

Single vs Multivalued Attributes

Simple vs Composite Attributes

Given vs Derives Attributes

Prime vs Non-prime attribute

Relational Model

The Relational Model is a data model used to organize data into tables (relations) consisting of rows (tuples) and columns (attributes). It was introduced by E.F. Codd in 1970 and forms the basis for most modern relational database management systems (RDBMS).

Relation: The main construct for representing data in the relational model is a relation, which is a table.

Attribute/Field: Attributes are used to describe relations. Columns of relations are attributes.

Tuple/Record: A row in a relation.

Instance: Snapshot of the data in the database at a given instant in time.

Database Schema: Logical design of database. Example: Reation_name(attribute1, attribute2)

Domain: A unique set of values permitted for an attribute.

Domain Constraint: Specifies an important condition that we want each instance of relation to satisfy,

Degree/Arity: Number of attributes in a relation.

Cardinality: Number of tuples in a relation.

Relational Databases: A relational databases is a collection relations.

Keys: An attribute or set of attributes which value can uniquely identify a tuple in a relation.

Types of keys

1. Super Key: A super key is a set of one or more attributes in a relation (table) that can uniquely identify each tuple (row) in that relation.

2. Candidate Key: A candidate key is a minimal set of attributes in a table that can uniquely identify each tuple (row) in the relation. It contains the smallest possible number of attributes required for unique identification.

3. Primary Key: A primary key is a specific type of candidate key chosen to uniquely identify each tuple (row) in a relational database table. Primary keys cannot contain NULL values.

4. Alternate Key: All candidate keys apart from primary key,

5. Foreign Key: A foreign key is an attribute (or a set of attributes) in a table that references the primary key in another table. It establishes a relationship between two tables, enforcing referential integrity by ensuring that the value in the foreign key column corresponds to a valid value in the referenced table’s primary key.

Referential Integrity: Referential integrity ensures data consistency between tables by enforcing that a foreign key in one table either matches a primary key in another table..

ERD to Relational Model

Many → One

Best solutions:

Many to many relationship : one extra table is needed for relationship information along with the two tables.

One to Many relationship: creates only two tables keep relationship information toward many sides.

One to one relationship: Keep information any of them, no extra table is needed. If only one entity set having total participation then keep relationship information towards total participation table to avoid multiple null tables.

Specialization and generalization: Possible with two tables.

Functional Dependency (FD)

Consider a relation R and 2 attributes A and B

B is functionally dependent on A (denoted by A → B), if each value of A is associated with exactly one value in B in relation.

• Functional dependencies play a key role in differentiating good database design from bad database design.

• A functional dependency is a type of constraint that is a generalization of the notion of key. (By helping of FD, we can say which attribute or attributes gonna be key. )

• X → Y, where X is a set of attributes that can determine the value of Y.

Closure of Attributes: The closure of a set of attributes (denoted as $X^+$ ) is a set of attributes that can be functionally determined by the given set of attributes X in a relation.

Properties

Trivial: Some functional dependencies are said to be trivial because they are satisfied by all relations. (Trivial means obvious) Example: A→ A

Armstrong’s Axioms

• Reflexivity Rule: $A \to B$, if $B \subseteq A$

• Augmentation Rule: If $A\to B,$ then $C A \to C B$

• Transitivity Rule: If $A \to B$, $B \to C$, then $A \to C$

Additivity Rules

• Union Rule: If $A \to B,$ $A \to C,$ then $A \to BC$

• Decomposition Rule: If $A \to BC,$ then $A \to B$ and $A \to C$

• Pseudo-transitivity rule: If $A \to B$, $BC \to D$ then $AC \to D$

Finding keys from FD

Normalization

Normalization is the process of minimizing redundancy from a relation or set of relations.

Redundancy in relation may cause insertion, deletion and update anomalies.

Essence of Normalization : One relation should have one theme.

Process of Normalization

1 NF : 1st Normal Form

A relation R is said to be in 1NF if there are no any multivalued attribute in R.

2NF : 2nd Normal Form

A relation R is said to be in 2NF if it is already in 1NF and there is no any non-prime attribute R which is partially dependent on prime attribute of R.

$\text{PartOfCK(proper subset of CK)} → NPA$ is present in FD, then it is not in 2NF.

Partial Dependency: Partial dependency in a relational database occurs when a nonprime attribute (i.e., not part of any candidate key) is functionally dependent on only a part of the candidate key, rather than the entire candidate key.

3 NF : 3rd Normal Form

A relation is said to be in 3NF if there is already in 2NF and there is no any non-prime attribute in R which is transitively dependent on the key of R.

It won’t be 3 NF if

• Not in 2NF

• Key → X, X → A or

  NPA→NPA

BCNF : Boyce Codd Normal From

A relation R is said to be in BCNF if it is already in 3NF and for every functional dependency A→B, A should be super key in R.

Lossy, Lossless, and Dependency Preserving Decomposition

Lossy Decomposition: The decomposition of relation R into R1, R2, R3, R4 … RN is lossy when the join of R1, R2, R3…RN does not produce the same relation as in R.

Lossless Decomposition: The decomposition of relation R into R1, R2, .., Rn is lossless when the join of R1,R2,…,Rn produces the same relation as in R.

• Upto 3NF all decompositions are lossless and dependency preserving

• BCNF may give lossy decomposition and may/ mayn’t be dependency preserving

Note:

• During the normalization process BCNF gives lossy decomposition, then BCNF decomposition wont be applied. Because, we will decompose until it gives lossless decomposition.

• Any relation with 2 attributes is always into BCNF.

Dependency Preserving Decomposition: A decomposition D = {R1, R2, …, Rn} of R is dependency preserving with respect to a set F of functional dependency if

$\{F_1 \cup F_2 ... \cup F_n \}^+ = F^+$

• Upto 3NF all decompositions are lossless and dependency preserving

• BCNF may give lossy decomposition and may/ may not be dependency preserving

SQL : Structured Query Language

Domain-specific language used in programming and designed for managing data held in RDBMS.

Operations

• Inserting

• Retrieving

• Updating

• Deleting and more

SQL Datatypes

• String

• Varchar

• Bit

• BOOL, BOOLEAN

• INT, INTEGER

• BIGINT

• FLOAT (size, d)

• FLOAT(p), p is 0-24, then it is float, if > 24, it will be in double.

More

• SQL is not case sensitivity

• Semicolon mandatory: nor always. If more than one sql statements to be run together, then semicolon is mandatory,

Select Command

Syntax: Select column1. column2 from table_name

To Select all columns: Select * from table

Using distinct: Select distinct column1, column2 from table [unique value of combination of column1, column2]

Where (Used to filter): select * from table where column2 = “something”

Sequence of running: from → where → select

Relational Operators in where:

• Equal =

• Not Equal <>

• Less than <

• Less than equal to <=

• Greater than >

• Greater than > =

Logical Operators

• AND : having multiple conditions

• OR :having multiple conditions

• NOT

Select * from order where NOT quantity > 10 = quantity ≤ 10

Between Operators: Used to filter records in the specific in range.

select * from table where quantity between 10 and 20. = 10 ≤ quantity ≤ 20

Return all such orders details when quantity is lesser than 10 or greater than 20 = select * from table where NOT between 10 and 20

Limit: Used to limit number of fetched records from a huge database table.

select * from table where price > 10 limit 10 = first 10 records where price > 10

show 4 records after leaving first 5 records = select * from table1 limit 5,4

NULL : null is a representation of having no value

select * from table where column is NULL

select * from table where column is not NULL

Aggregate Function: performs a calculation on multiple values and return a single value

• used in select

• it ignores null values

Min : select min(column) from table

Max : select max(column) from table

Sum : select sum(column) from table

Count : select count(column) from table ⇒ count the number of rows

Average: select avg(column) from table

In Operator: it allows you to specify multiple values in a where clause. it is shorthand for multiple or conditions.

select * from table where country in (”BD”, “USA”, “UK”)

Alias: used to give a temporary name to a table or column in a table

• used to make table names or column name more reliable

• only exists for the duration of the query

• created with the keyword : AS

Alias of table: select * from table1 as tb1

Alias of column: select column1 as col1 from table where col1 = “Test”

select column1 as [Column One] from table

SQL Joins

Needed to retrieve records from more than one table

Requirement of Joint : 2 tables must have one common column

Types of Joins

Natural Join: Inner, Left and Right join

Inner Join

• select * from table1 inner join table2 on table1.column = table2.column

• without join: select * from table1, table2 where table1.column = table2.column

Left Join/Left outer join

• select * from table1 left join table2 on table1.column=table2.column

• if there is no value of right table, then they will be filled with NULL

Right Join/Right Outer Join

• select * from table1 right join table2 on table1.column = table2.column

Full Join/Full Outer Join

• all records from left and right table are fetched

• if any of them is not matching, then records are filed NULL

• select * from table1 full join table2 on table1.column = table2.column

Self Join

• only one table is involved, act like inner join

• select * from table1 as tb1, table2 as tb2 where tb1.column=tb2.column

Cartesian Product

• super set of all combinations of all records

• no any common column is needed

• select * from table1, table2

• if table 1 has c1 column and r1 rows, table2 c2 and r2
  then cartesian product : column = c1 + c2, rows = r1*r2

Group By clause

• SELECT count(customer) as [Total Customer], status as [Status] from shippings group by status

select sum(price), catID from products where group by catID

• select sum(price), catID where catID > 2 group by catID

WHERE should be used before executing the group by

Can’t use where after group by/with aggregate function. HAVING

Having Clause

The having clause in sql is used if we need to filter the result based on aggregate functions such min, max, sum, avg, or sum. The having clause was introduced because the where clause does not support aggregate function. Also, group by must be use before the having clause.

Execution: where → group → having

Set Operators

• Used to combine results from two or more select statements

• Syntax : (select * from table1) SetOperation (Select * from table2)

• no. of columns selected by both queries must be equal

Types

• Union
  • duplicate rows are eliminated
  • Syntax : (select * from table1) union (Select * from table2)

• Union all
  • it selects all rows from both select statements
  • does not eliminate duplicates
  • Syntax : (select * from table1) union all (Select * from table2)

• Intersect
  • selects only common rows from both select statements
  • Syntax : (select * from table1) intersect (Select * from table2)

• Minus/except
  • it selects only those rows which are unique in first select statement
  • Syntax : (select * from table1) except (Select * from table2)

ORDER BY Clause

• used to sort the result-set in ascending or descending order

• Ascending: SELECT * FROM table ORDER BY column1 asc

• Descending: SELECT * FROM table ORDER BY column DESC

• Default → Ascending : SELECT * FROM table ORDER BY column1

• it executes at last

• Multiple column : select * from table order by column1 desc, column2 asc [if column1 is same for multiple rows, then column2 will be considered]

Subquery

A subquery or inner query or a nested query is a query within another sql query and embedded within the where clause.

Types of subquery

1. Single row subquery : fetch only one row

2. Multiple row subquery : subquery return multiple rows

   Operator Used with

   • In : used for equal to or not equal to comparison only

     select * from table where in (sub query)

     Find all customers, who are in supplier city.

     select * from customers where country in (select country from suppliers group by country)

     Find all customers, who are not in supplier city.

     select * from customers where country not in (select country from suppliers group by country)

     Find all customers, who have placed more than 2 orders.

     select * from customers where customer_id in (select customer_id from orders group by customer_id having count(order_id) > 2)

   • any : can be used more operators

     select column from table1 where column operator any (select column from table2 where condition)

     Operator : =, <>, >, ≥, <, ≤

     Find the productName of all those products which have their orders quantity larger than 50.

     select prodductName from products where productID = ANY (select productID from orders where quantity > 50)

     Find the productName of all those products which having productIDs less than any of the product having orders Quantity equal to 1.

     select productName from products where productId < any(select productId from orders where quantity=1)

     

   • all

   

   select column from table1 column operator all(subquery)

   Select all products which have productId less than all of the id which have order quantity 1.

   select * from products where productId < all(select producId from orders where quantity = 1)

   Finds all employees whose salaries are greater than the salary of all the employees in the Sales department with departmentID 2.

   select * from employee where salary > all(select salary from employee where departmentID = 2)

   select * from employee where salary > (select max(salary) from employee where departmentID = 2)

   

   • exists :
     • used to test for the existence of any record in a subquery
     • returns true if the subquery returns one or more records
     • work for multiple and single row subquery

     select * from where exists (subquery)

     

   

• NOT Exists : Opposite of exists

Why subquery not join ?

• readable and understandable

• better performance

• joins may have redundant data

Other wise join performs better than subquery.

Relational Algebra

Relational algebra is a procedural query language, which takes instance of relations as input and yields instance of relations as output.

The main application of relational algebra is to provide a theoretical foundation for relational databases, particularly for query language.

Basic Operators

• Select $\sigma$ : Same as SQL Select * from where condition

  $\sigma_{\text{<Selection-condition>}} (\text{Relation name})$

  $\sigma_{{\text{age > 18 } \wedge \text{ rating != 10}} }(\text{customers})$

  $\wedge$ → and, $\vee$ → OR

• Project $\prod$ : Selecting specific columns, similar to select distinct col from, projects should be written in outermost

  $\prod_{A1, A2, ...} (r)$

  $\prod_{\text{EmployeeId, Name}} (\text{employee})$

  

• Union $\cup$
  • no column of should be same, consecutive column of each table type must be same, duplicates are eliminated

    $\prod_{*} (R_1) \cup\prod_{*} (R_2)$

    $\prod_{Eid} (R_1) \cup\prod_{Eid} (R_2)$

    

• Set difference $-$

  $\prod_{Eid} (R_1) - \prod_{Eid} (R_2)$

• Intersection $\cap$

  $\prod_{Eid} (R_1) \cap\prod_{Eid} (R_2)$

  

• Cartesian Product $\text{X}$

  

• Joins $\Join$
  • Condition Join : join with conditions

    $E \Join_{\text{Condition}} R$

  • Equi Join : if condition is only equal to

    $E \Join_{\text{E.id=R.mid}} R$

  • Natural Join: requirement is both relations should have at least one column name common and they matched automatically

    $E \Join R$

    

  

• Rename $\rho$ : as aliasing in SQL

  $\rho_s \text{ Students}$ ⇒ Students renamed as s (table name)

  $\rho_{\text{tableNewName(colNewName, Col2NewName)}} (\text{Original })$ ⇒ Giving new name to column and table

  $\rho_{\text{std(r, n, d)}} (\text{Student})$

  $\rho_{\text{r, n, d}} (\text{Students})$ ⇒ Just columns are re named not the table

  $\rho_{\text{RollNo} \to \text{ R}} (\text{Students})$ ⇒ RollNo column named as R

• Division $\div$
  • $R_1 \div R_2 \text{ possible if} \\ R_2 \subseteq R_1$

    Attribute set of R2 should be a subset of R1

  • Answer will be that value of R1 which is associated with all the rows of R2.
  • used in for all case

  

Transaction

Logic unit of database which includes one or more database access operations.

Commit

Rollback: Back to last commit

ACID Property of Transaction

• Atomicity: All or none

• Consistency: All transaction should provide consistent result.

• Isolation: If multiple transaction which are running on same database produce the result in such a way that all are running in isolation.

• Durability:

Schedule

Collection of multiple transactions running on same database.

Concurrency:

Why Concurrency

• Improved throughput

• Resource utilization

• Reduced waiting time

Problem with concurrency

• Recoverability problems

• Deadlock

• Serializability issues

• Dirty read or temporary update problem
  

• Phantom read problem

  

• Unrepeatable read problem

• Lost update problem

• Incorrect summary problem

Good vs Bad Schedule

Good schedule: concurrent schedules which provides consistent result.

Serial vs Non-serial Schedule

Non-serial: concurrent

Serializable Schedule: A concurrent schedule which provides result as a serial schedule.

Checking Serializability

• Conflict Serializability
  • 2 databases statements are conflicting if and only if
    • both are in different transactions
    • both are accessing the same data item
    • at least one of them is write operation
  • Read-read no conflict
  • Conflict Equivalent

  

  • Conflict Serializability
    • Given a concurrent schedule S, find a serial schedule S’, such that

      S conflict equivalent S’

      S is a conflict serializable.

    • To prove a given schedule conflict serializable we will use a graph ⇒ conflict precedence graph (Directed graph)
      • Vertices ⇒ Transactions
      • Edges ⇒ Conflicts
      • If conflict graph has a cycle, then it is not conflict serializable

      

  

• View Serializability
  • because of conflict serializability has too hard rules

  

  • 3 points to remember: for every datwa item
    • who reads from database
    • who reads from others written value
    • who writes last
  • View equivalence
    • S1 and S2 are view equivalence if both are following similar sequence rules of view serializable

    

  • View Serializability
    • A schedule is called view serializable if it is view equivalent to any serial schedule
    • If there is a concurrent schedule S, and it is serializable iff

      S view equivalence S’, where S’ is any serial schedule

    • Will make a graph based on rule 2 and 3
      • who writes last will be in last in the sequence

      

    

Recoverable Schedule

When no any committed transaction should be rolled back.

• Cascadeless recoverable rollback

  

• Cascading recoverable rollback

  

Serializability is not possible in practically. Practical ⇒ Locking protocols…

Locking Protocols

What is Lock?

Types

• Shared : Taken for read, so that multiple read can be allowed

• Exclusive : taken for write

Busy waiting

Block transaction

Multiple shared Lock ( with Starvation)

Multiple shared Lock without starvation

Problem With Locking mechanism

2 Phase Locking Protocol

1 Phase : Locking

2 Phase : Unlocking

Basic 2 phase locking protocols (2PL)

• Systematic locking mechanism

• Once unlock done, a transaction is not allowed to lock any database item

• Every schedule which is allowed under basic 2PL, is conflict serializable also.

• 2 PL
  • Suffers from starvation
  • suffers from deadlock
    

  

Database Record Storage

File System

Logical block

Indexing

Dense vs Sparse Index

Dense: index record is for each database record

Sparse: index record is for a few database record only

Indexing Techniques

• primary
  • indexing done on primary key or any super key
  • data must be ordered on index
  • its always sparse index

  

• clustering
  • indexing done non-key field
  • data must be ordered on index field
  • It is sparse → indexing is done for each unique non-key

  

• secondary-key
  • indexing done on primary key or any super key
  • data must not be ordered on index field
  • it can be dense or sparse

  

• secondary non-key
  • indexing done on non-key field
  • data must not be ordered on index field

  

Was Linear searching..

B Trees

• Tree based indexing

• dynamic indexing technique

• based on insertion and deletion, the tree automatically adjusted

• self balancing search tree

• it grows horizontally and vertically

An order-p B-tree

• maximum children p

• every node other root should have atleast $\lceil \frac{p}{2} - 1 \rceil$ keys and ceil p/2 child

• in every node there are at most (p-1) keys and p tree pointer

• root can have minimum 1 keys and 2 tree pointer

• all leaves appear on the same level

Node structure

• key

• record pointer

• tree pointer

P-order B-tree
Total nodes = n

$H_{min} = \lceil \log_p (n+1) - 1 \rceil$

$H_{max} = \lfloor \log_{{\lceil\frac{p}{2}\rceil}} \frac{n+1}{2} \rfloor$