COMP2411 - Database System

A. ER Diagram

1. ER Digram

er_symbol

2. Cardinality Notation

1).

2). Some Examples

er_1

3. (Min, Max) Notation

1). Transfer to Sentence

min_max_n_ex1

---> There have 1 or more employee manges 1 department

---> Each department have 1 or more employee

min_max_n_ex2

---> One or more employee work for one department

---> One department have many employee

2). Some Examples

er_2

er_3

B. Relation Schema

1. Relation Key Types

Super Key
- Super key is the Superset
Primary Key
- Unique identifier
- Only ONE
- Can't be NULL value
Candidate Key
- Unique identifier
- Can't be NULL value
Alternate Key
- Candidate Key without Primary Key
Foreign Key
- A Key can connect one table to another table

2. Relation Schema (Table or Bruckets)

Table
Person
ID Name Address
Bruckets
Person(ID, Name, Address)

	Person
ID	Name	Address

3. ER Diagram to Relation Schema

(Warning: Need to include both relation and entity ! ! !)

C. SQL (Oracle)

1. SQL Query

DISTINCT, LIKE


-- Use DISTINCT
SELECT DISTINCT Customer.cname, city FROM Borrow, Customer
WHERE Borrow.cname = Customer.cname AND bname = “Sai Kong”;

-- Use LIKE
SELECT cname FROM Customer
WHERE street LIKE “%Main%”;

Rename & Nested Query


-- Solution 1:
SELECT DISTINCT T.cname FROM Deposit T
WHERE T.cname != “Jones” AND T.bname IN (
    SELECT S.bname FROM Deposit S 
    WHERE S.cname = “Jones”
);

-- Solution 2:
SELECT DISTINCT T.cname FROM Deposit S, Deposit T
WHERE S.cname = “Jones” AND S.bname = T.bname AND T.cname != S.cname;

Empty & ALL


-- Solution 1:
SELECT X.bname FROM Branch X
WHERE NOT EXISTS (
    SELECT * FROM Branch Y
    WHERE Y.b-city = “New Territory” AND Y.assets >= X.assets
);

-- Solution 2:
SELECT bname FROM Branch
WHERE assets > ALL (
    SELECT assets FROM Branch
    WHERE b-city = “New Territory”
);

SOME


-- Solution 1:
SELECT bname FROM Branch
WHERE assets > SOME (
    SELECT assets FROM Branch
    WHERE b-city = “Kowloon”
);

-- Solution 2:
SELECT X.bname FROM Branch X, Branch Y
WHERE X.assets > Y.assets AND Y.b-city= “Kowloon”;

CONTAINS


SELECT DISTINCT S.cname FROM Deposit S
WHERE (
    SELECT T.bname FROM Deposit T
    WHERE S.cname = T.cname
) CONTAINS (
    SELECT bname FROM Branch
    WHERE b_city = “Kowloon”
);

EXISTS & NOT EXISTS


SELECT C.cname FROM Customer C
WHERE EXISTS (
    SELECT * FROM Deposit D
    WHERE D.cname = C.cname AND D.bname = “Central”
) AND NOT EXISTS ( 
    SELECT * FROM Borrow B
    WHERE B.cname = C.cname AND B.bname = “Central”
)；

MINUS


SELECT DISTINCT S.cname FROM Deposit S
WHERE NOT EXISTS (
    (
      SELECT bname FROM Branch
      WHERE b_city = “Kowloon”
    ) MINUS (
      SELECT T.bname FROM Deposit T
      WHERE S.cname = T.cname
    )
);

Ordering the Display of Tuples (ORDER BY | ORDER BY ... DESC | ORDER BY ... ASC)


-- ORDER BY
SELECT DISTINCT cname FROM Borrow
WHERE b_city = “Kowloon” 
ORDER BY cname;

-- ORDER BY ... DESC | ORDER BY ... ASC
SELECT * FROM Borrow
ORDER BY amount DESC, loan_no ASC;

Data Definition and Manipulation


xxxxxxxxxx
-- Table creation
CREATE TABLE table_name (
  A1, D1,
  A2, D2, ...
  Ak, Dk
);

-- Table deletion
DROP TABLE table_name;

-- Row/Tuple deletion
DELETE table_name;

-- Table update
ALTER TABLE table_name
ADD Aj, Dj

Views

A modification is permitted through a view ONLY IF the view is defined in terms of ONE base/physical relation !!!


xxxxxxxxxx
-- Example 1:
CREATE VIEW loan_info AS 
    SELECT bname, loan_no, cname FROM Borrow;

-- Example 2:
CREATE VIEW branch-city AS
    SELECT bname, city FROM Borrow, Customer
    WHERE Borrow.cname = Customer.cname;

Modifying the Database

Deletion


xxxxxxxxxx
-- Syntax
DELETE r
WHERE P

-- Example 1:
DELETE Deposit
WHERE b-name IN (
    SELECT b-name FROM Branch
    WHERE b-city = “Laguna”
);

-- Example 2:
DELETE Deposit
WHERE balance < (
    SELECT AVG(balance) FROM Deposit
);

Insertion


xxxxxxxxxx
-- Syntax
INSERT INTO r VALUES (v1, v2, …, vn);
-- or
INSERT INTO r
SELECT clmn_name1, clmn_name2, …, clmn_namek FROM s1, s2, …
WHERE ...

-- Example 1:
INSERT INTO Deposit
SELECT b-name, loan_no, c-name, 0 FROM Borrow 
WHERE b-name = “ClearWaterBay”

-- Example 2:
INSERT INTO Deposit
SELECT * FROM Deposit

Update


xxxxxxxxxx
-- Syntax
UPDATE r
SET clmn1 = expression
WHERE ...

-- Example 1:
UPDATE Deposit
SET balance = balance * 1.05

-- Example 2:
UPDATE Deposit
SET balance = balance * 1.06 WHERE balance > 10000
UPDATE Deposit
SET balance = balance * 1.05 WHERE balance <= 10000

Null Values


xxxxxxxxxx
SELECT c_name FROM Deposit
WHERE balance IS NULL; -- WHERE balance IS NOT NULL;

Aggregate Functions


xxxxxxxxxx
-- Functions: avg, sum, min, count, max

-- Example 1:
SELECT b-name, AVG(balance) FROM Deposit
GROUP BY b-name
HAVING AVG(balance) > 12000;

-- Example 2:
SELECT AVG(balance) FROM Deposit, Customer
WHERE Deposit.c_name = Customer.c_name AND city = “Laguna”
GROUP BY Deposit.c_name HAVING COUNT(DISTINCT acct_no) >= 3;

2. SQL to Sentence


xxxxxxxxxx
SELECT c_name FROM Deposit
WHERE balance IS NULL;
-- Find the person name which have null balance in the their deposit.

SELECT X.bname FROM Branch X, Branch Y
WHERE X.assets > Y.assets AND Y.b_city= “Kowloon”;
-- Find which brank assets is more than every each Kowloon's branch assets.

D. Relational Algebra

1. SELECT σ & PROJECT π operations

SELECT σ Operations

Form of the operation: σ c(R)

Example:


xxxxxxxxxx
σ topic = "Database" (Tutorials)
-- Selects tuples from Tutorials where topic = ‘Database’.

σ sales > 50000 (Customers)
-- Selects tuples from Customers where sales more than 50000.

σ DNO = 4(EMPLOYEE)
-- Selects tuples from EMPLOYEE who department number is 4.

PROJECT π operations
- π A1, A2, An (r)
- Example:

2. Set Operations

o_example

UNION: R1 U R2
INTERSECTION: R1 ∩ R2
SET DIFFERENCE: R1 - R2

CARTESIAN PRODUCT: R1 X R2

c_product_o_example

Example:


xxxxxxxxxx
-- Combine each female EMPLOYEE tuple with the DEPENDENTS tuple to get her dependent(s).
FemEMPNAMES ← π FNAME,LNAME,SSN (σ Sex=F (EMPLOYEE))
EMPDEPENDENTS← FemEMPNAMES X DEPENDENTS
ActualDEPENDENTS ← σ SSN=ESSN (EMPDEPENDENTS)
Result ← π FNAME,LNAME,DEPENDENT_NAME (ActualDEPENDENTS)

3. (INNER) JOIN Operations

join_operations_1

Theta Join

Example


xxxxxxxxxx
select distinct h.name
from hospitals h, schools s
where
distance(h.location,s.location) < 5;


xxxxxxxxxx
EMPLOYEE ⋈θ EMPLOYEE.EXPERIENCE >= DEPARTMENT.MIN_EXPERIENCE DEPARTMENT

Equi Join


xxxxxxxxxx
EMPLOYEE ⋈EMPLOYEE.E_NO = DEPARTMENT.E_NO DEPARTMENT

Natural Join


xxxxxxxxxx
EMPLOYEE ⋈ DEPARTMENT

OUTER JOIN & OUTER UNION
- Left outer join
- Right outer join
- Full outer join

Complete Set of Relational Algebra Operations
- 5 Operations ==> SELECT (σ), PROJECT (π), UNION (U), SET DIFFERENCE (-), and CARTESIAN PRODUCT (X).
- The set {σ , π , U, - , X } is called a complete set of relational algebra operations.

4. SQL to Relational Algebra

Example:


xxxxxxxxxx
-- SQL
SELECT a.name, b.capital FROM countries AS a, countries AS b
WHERE a.name = b.capital

-- Relational Algebra
π a.name, b.capital
σ a.name = b.capital
(ρ a countries × ρ b countries)

E. Compatibility Mode

1. Normal Forms

1st Normal Form (1NF)
2nd Normal Form (2NF)
- All non-key attributes depend on the entire key
3rd Normal Form (3NF)
- All non-key attributes only depend on the key
BCNF
- BCNF is stronger than 3NF
- BCNF is useful when a relation has:
  - multiple candidate keys, and
  - these candidate keys are composite ones, and
  - they overlap on some common attributes
- BCNF reduces to 3NF if the above conditions do not apply

F. File Organization & Indexs & Data Structure in DBMS

1. Disk Storage Devices

disk_storage_devices_1

Reading or writing a disk block is time consuming because of the seek time s and rotational delay (latency) rd
Double buffering can be used to speed up the transfer of contiguous disk blocks

2. Files of Records

Unspanned (no record can span two blocks)
Spanned (a record can be stored in more than one block)

1). Operations on Files

OPEN
FIND
FINDNEXT
READ
INSERT
DELETE
MODIFY
CLOSE
REORGANIZE
READ_ORDERED

2). Unordered Files & ordered Files

Unordered Files (Pile Files)
- Linear Search (Searching will be expensive)
- New records are inserted at the end of the file
- Record insertion is quite efficient (Just put at the end)
- Reading the records in order of a particular field requires sorting the file records (If have some require searching, need to sorting)
Ordered Filles (Sequential Files)
- Insertion is expensive (Records must be inserted in the correct position)
- Binary Search ( O(log2n) ) (More fast than unordered file searching & reading)
- Reading the records according to the order of the ordering field is quite efficient (Good for order reading)

4). Hash File

Search is very efficient on the hash key
Overflow handling (for Collisions)

hashed_files_1

5). Dynamic & Extendible Hash

Dynamic growth
Shrinking of the number of file records

hashed_files_2

3. Indexes as Access Paths

BFR = Block Size / Record Size

number of index blocks b = r / (Block Size / Record Size)

Avg Linear Search = (b/2)= 10000/2= 5000 block accesses

Block Access:

Binary search needs log2b = log2938= 10 block accesses +1 get file block = 11 block accesses

4. Types of Single-level Indexes

Primary Indexing (Index table is created using primary keys)
- Search Keys are unique.
- Search Keys are in sorted order.
- Search Keys cannot be null as it points to a block of data.
- Fast and Efficient Searching.
Secondary Indexing (Index table is created using candidate keys)
(There can be many secondary indexes for the same data file !!!)
- Search Keys are Candidate Keys.
- Search Keys are sorted but actual data may or may not be sorted.
- Requires more time than primary indexing.
- Search Keys cannot be null.
- Faster than clustered indexing but slower than primary indexing.
Clustered Indexing (Index table is created using non-key values)
- Search Keys are non-key values.
- Search Keys are sorted.
- Search Keys cannot be null.
- Search Keys may or may not be unique.
- Requires extra work to create indexing.

5. Multi-level Indexes

Example

muti_level_indexing

6. B Tree & B+ Tree

	B Tree	B+ Tree
Difference	Pointers to data records exist at all levels of the tree	All pointers to data records exists at the leaf-level nodes
Example
Insertion	N/A
Deletion	N/A

G. Tuning in Relational DBMS

1. Goal

To make application run faster
To lower the response time of queries/transactions
To improve the overall throughput of transactions

2. Tuning Indexes

Drop indexes or/and build new indexes
Change a non-clustered index to a clustered index (and vice versa)
Rebuilding the index

3. Tuning Queries

H. Transactions and Concurrency Control

1. Transaction

Read - Retrieval
Write - Insert or update, delete

1). Property of Transaction

Atomicity (Commit & Abort)
- Transaction take place at once if not, the transaction is aborted
- No Midway
Consistency
- The integrity constraints are maintained so that the database is consistent before and after the transaction
- The execution of a transaction will leave a database in either its prior stable state or a new stable state
- The consistent property of database states that every transaction sees a consistent database instance
- The transaction is used to transform the database from one consistent state to another consistent state
Isolation
- The data which is used at the time of execution of a transaction cannot be used by the second transaction until the first one is completed
- When a transaction T1 is using data X, other transactions can't use data X
- The concurrency control subsystem of the DBMS enforced the isolation property
Durability
- Is used to indicate the performance of the database's consistent state. It states that the transaction made the permanent changes
- That consistent state cannot be lost, even in the event of a system's failure
- The recovery subsystem of the DBMS has the responsibility of Durability property

2). States of Transaction

State_Transition_Diagram

Active state
Partially committed state
Committed state
Failed state uTerminated State

Recovery manager

Use: undo & redo

Track:

begin_transaction
read / write
end_transaction
commit_transaction
rollback (abort)

3). Transaction Schedule

Example:

Label	Transaction
T1	w1(x), r1(y), w1(y)
T2	r2(x), r2(y), w2(y)
-->	w1(x), r2(x), r1(y), w1(y), r2(y), w2(y)

Serial Schedule
- Do the Transaction one by one
Non-serial Schedule
- Interleaving of operations
Serializable Schedule
- Used to find non-serial schedules that allow the transaction to execute concurrently without interfering with one another

4). Schedules Classified on Recoverability

Cascadeless-and-Strict-Schedule

“Recoverable” Schedule (Cascading Rollback)
- Failure of one transaction causes several other dependent transactions to rollback or abort
- Example:
“Cascadeless” Schedule (only committed read operations & uncommitted write operations)
- In a schedule, a transaction is not allowed to read a data item until the last transaction that has written it is committed or aborted
- Example:
“Strict” Schedules (only committed read and write operations)
- A transaction is neither allowed to read nor write a data item until the last transaction that has written it is committed or aborted
- Example:

5). Schedules Classified on Serializability

Conflict Serializable Schedule
- Both belong to separate transactions
- They have the same data item
- They contain at least one write operation

2. Concurrency

Interleaved processing
Parallel processing

1). Concurrency Control

To enforce isolation
To preserve database consistency
To resolve read-write (RW) and write-write (WW) conflicts

2). Two-Phase Locking Techniques

Locking is an operation which secures permission
- to Read
- to Write a data item for a transcation
Unlocking is an operation which removes these permissions from the data item
Lock and Unlock are Atomic operations
Essential components
- Two Lock Modes
  - Shared (read) - shared lock (X)
    - More than one transaction can apply share lock on X for read data
  - Exclusive (write) - write lock (X)
    - Only one write lock on X can exist at any times
    - Conflict matrix
- Lock Manager
  - Managing locks on data items
- Lock Table

COMP2411 - Database System

A. ER Diagram

1. ER Digram

2. Cardinality Notation

1).

2). Some Examples

3. (Min, Max) Notation

1). Transfer to Sentence

2). Some Examples

B. Relation Schema

1. Relation Key Types

Super Key

Primary Key

Candidate Key

Alternate Key

Foreign Key

2. Relation Schema (Table or Bruckets)

3. ER Diagram to Relation Schema

C. SQL (Oracle)

1. SQL Query

DISTINCT, LIKE

Rename & Nested Query

Empty & ALL

SOME

CONTAINS

EXISTS & NOT EXISTS

MINUS

Ordering the Display of Tuples (ORDER BY | ORDER BY ... DESC | ORDER BY ... ASC)

Data Definition and Manipulation

Views

Modifying the Database

Null Values

Aggregate Functions

2. SQL to Sentence

D. Relational Algebra

1. SELECT σ & PROJECT π operations

SELECT σ Operations

PROJECT π operations

2. Set Operations

3. (INNER) JOIN Operations

OUTER JOIN & OUTER UNION

Complete Set of Relational Algebra Operations

4. SQL to Relational Algebra

Example:

E. Compatibility Mode

1. Normal Forms

F. File Organization & Indexs & Data Structure in DBMS

1. Disk Storage Devices

2. Files of Records

1). Operations on Files

2). Unordered Files & ordered Files

4). Hash File

5). Dynamic & Extendible Hash

3. Indexes as Access Paths

4. Types of Single-level Indexes

5. Multi-level Indexes

Example

6. B Tree & B+ Tree

G. Tuning in Relational DBMS

1. Goal

2. Tuning Indexes

3. Tuning Queries

H. Transactions and Concurrency Control

1. Transaction

1). Property of Transaction

2). States of Transaction

3). Transaction Schedule

4). Schedules Classified on Recoverability

5). Schedules Classified on Serializability

2. Concurrency

1). Concurrency Control

2). Two-Phase Locking Techniques