LOVELY PROFESSIONAL UNIVERSITY
HOME WORK: 3

School: Department CSE/IT
Name of the faculty member: Course No: CSE301
Course Title: Database Management System
Class: B.Tech (CSE) Term: 6th Section: D1803 Batch:2008
Max. Marks: 18+7=25
Date of Allotment: Date of Submission:

Submitted By: Roll No: 25

PART-A

Q-1 What is overlapping of Candidate keys? What are the problems incurred due to this overlap and how these problems can be rectified. Explain with Example.
Overlap of candidate key is a type of candidate key which occur in BCNF(Boyce Codd Normal Form). In the difference between 3NF and BCNF example: a 3NF table which doesnot have multiple overlapping candidate keys is gurantted to be in BCNF. Depending on what its functional dependencies are . a 3NF table with two or more overlapping candidate keys may or maynot be in BCNF.

Example:
The original definition of 1NF was in adequate in some situations. It was not satisfactory for the table:

• They had multiple candidate keys • Where the multiple candidate keys were composite • Where the multiple candidate keys overlapped
Therefore, a normal form, the BCNF was introduced. We must understand it in tables where the above three candidates don’t apply, we can stop the 3NF. In such cases, the 3NF is same as the BCNF.

A relation is in BCNF iff every determinant is a candidate key.
Consider the following PROJECT table

|ECODE |NAME |PROJECT |HOURS |
|E1 |veronica |P2 |48 |
|E2 |Anthony |P5 |100 |
|E3 |Mac |P6 |15 |
|E4 |Susan |P2 |250 |
|E4 |Susan |P5 |75 |
|E1 |Verinoca |P5 |40 |

This table has redundancy. If the name of the employee has been modified, the change will have to be made consistence across the table. Otherwise there will be inconsistencies.

ECODE+PROJECT is the primary key. We will notice that NAME +PROJECT could be chosen as primary key and hence is a candidate key.

• HOURS is functionally dependent on ECODE=PROJECT • HOURS is also functionally de4pendent on NAME+PROJECT • NAME is functionally dependent on ECODE • ECODE is functionally dependent on NAME
This is a situation ythat requires conversion to BCNF. The table is essentially in the 3NF. The only non_key item is HOURS, which is dependent, on the whole key, that is, ECODE+PROJECT or NAME+PROJECT.

ECODE and NAME are determinants since they are functionally dependent on each other. However, they are not candidate keys by themselves. As per BCNF, the determinants have to be candidate keys.

Q-2 Suppose you are given a relation R = (A, B, C, D, E) with the following functional

dependencies: {CE → D, D → B, C → A}.

a. Find all candidate keys. b. Identify the best normal form that R satisfies (1NF, 2NF, 3NF, or BCNF). c. If the relation is not in BCNF, decompose it until it becomes BCNF. At each step, identify a new relation, decompose and re-compute the keys and the normal forms they satisfy.
a. The candidate key is {C,E}
b. The relation is in 1NF
c. Decompose into R1=(A,C) and R2=(B,C,D,E). R1 is in BCNF, R2 is in 2NF. Decompose R2 into, R21=(C,D,E) and R22=(B,D). Both relations are in BCNF.

Q-3 Can we achieve 2NF without 1NF and How. Also differentiate 1NF and 2NF with an example. No we cannot achieve 2NF without 1NF as Normal Forms form a hierarchy in such a way that a schema in a higher normal form automatically fulfills all the criteria for all of the lower Normal Forms. First normal form
A relation R is in first normal form (1NF) if and only if all underlying domains contain atomic values only

Example: 1NF but not 2NF

FIRST (supplier_no, status, city, part_no, quantity)

Functional Dependencies:

(supplier_no, part_no) ® quantity
(supplier_no) ® status
(supplier_no) ® city city ® status (Supplier's status is determined by location)

Comments:

Non-key attributes are not mutually independent (city ® status).
Non-key attributes are not fully functionally dependent on the primary key (i.e., status and city are dependent on just part of the key, namely supplier_no).

Anomalies:

INSERT: We cannot enter the fact that a given supplier is located in a given city until that supplier supplies at least one part (otherwise, we would have to enter a null value for a column participating in the primary key C a violation of the definition of a relation).
DELETE: If we delete the last (only) row for a given supplier, we lose the information that the supplier is located in a particular city.
UPDATE: The city value appears many times for the same supplier. This can lead to inconsistency or the need to change many values of city if a supplier moves.

Decomposition (into 2NF):

SECOND (supplier_no, status, city)
SUPPLIER_PART (supplier_no, part_no, quantity)

Second normal form
A relation R is in second normal form (2NF) if and only if it is in 1NF and every non-key attribute is fully dependent on the primary key

Example

SECOND (supplier_no, status, city)

Functional Dependencies:

supplier_no → status supplier_no → city city → status

Comments:

Lacks mutual independence among non-key attributes.Mutual dependence is reflected in the transitive dependencies: supplier_no → city, city → status.

Anomalies:

INSERT: We cannot record that a particular city has a particular status until we have a supplier in that city.
DELETE: If we delete a supplier which happens to be the last row for a given city value, we lose the fact that the city has the given status.
UPDATE: The status for a given city occurs many times, therefore leading to multiple updates and possible loss of consistency.

PART-B

Q-4 What problems occur in database system when a transaction does not satisfy ACID properties? Explain explicitly using Suitable Examples.

ACID properties are as follows:

Atomicity: either all operations of the transaction are reflected properly in the database, or none are.

Consistency: execution of a transaction in isolation preserves the consistency of the database.

Isolation: even though multiple transactions may execute concurrently, the system guarantees that, for every pair of transaction Ti and T j. it appears to Ti that Tj finished execution before Ti started or Tj starts execution after Ti finished. Thus each transaction is unaware of other transaction executing concurrently in the system.

Durability: after a transaction completes successfully, the changes it has made to database persists, even if there are system failures.

Now take an example showing problem occur in database system when a transaction does not satisfy ACID properties:

Lets take an example of the banking system, let ti be a transaction that transfers $50 from account A to account B. this transaction can be defined as:

Ti: read (A);

A: =A-50;

Write (A);

B: =B+50;

Write (B);

Now lets consider the ACID properties:

Consistency: the consistency requirement here that sum of A and B be unchanged by the execution of the transaction. Without the consistency requirement, money could be created or destroyed by the transaction. It can be verified easily that, if a database is consistence before an execution of the transaction, the database remain consistent after the execution of the transaction.

Atomicity: suppose that just before the execution of transaction Ti, the values of account A and B are $1000 and $2000, respectively. Now suppose that, during the execution of transaction Ti, a failure occurs that prevents Ti from completing its execution successfully. Example of such a failures includes power failures, hardware failures and software failures. Further, suppose that the failure happened after the write (A) operation but before write (B) operation. In this case, the value of account A and B reflected in the database are $950 and $2000. The system destroys $50 as a result of this failure. In particular, we note that the sum A+B is no longer preserved.

Thus, because of the failure, the state of the system no longer reflects a real state of the world that the database is supposed to capture. We term such a state as inconsistent state.

Durability: once the execution of the transaction completes successfully, and the user who initiated the transaction has been notified that the transfer of funds has taken place, it must be the case that no system failure will result in the loss of data corresponding to this transfer of fund.

The durability property guarantees that, once a transaction completes successfully, all the updates that it carried out on the database persists, even if there is a system failure after the transaction completes its execution. In case if durability property is not hold data will be left in the inconsistent state.

Isolation: even if consistency and atomicity property is ensured for each transaction, if several transactions are executed concurrently, there operations may interleave in some undesirable way, resulting in an inconsistent state.

For example, the database is temporarily inconsistent while the transaction to transfer funds from A to B is executing, with the deducted total written to and the increased total yet to be written to B at this intermediate point and computes A+B, it will observe an inconsistent value. Furthermore, if this second transaction then performs updates on A and B based on the inconsistent values that it read, the database may be left in an inconsistent state even after both transactions have completed.

Q-5 How can we test the serializability of the schedules?

Schedule compliance with conflict serializability can be tested with the precedence graph (serializability graph, serialization graph, conflict graph) for committed transactions of the schedule. It is the directed graph representing precedence of transactions in the schedule, as reflected by precedence of conflicting operations in the transactions.
In the precedence graph transactions are nodes and precedence relations are directed edges. There exists an edge from a first transaction to a second transaction, if the second transaction is in conflict with the first (see Conflict serializability above), and the conflict is materialized (i.e., if the requested conflicting operation is actually executed: in many cases a requested/issued conflicting operation by a transaction is delayed and even never executed, typically by a lock on the operation's object, held by another transaction; as long as a requested/issued conflicting operation is not executed, the conflict is non-materialized; non-materialized conflicts are not represented by an edge in the precedence graph).
Comment: In many text books only committed transactions are included in the precedence graph. Here all transactions are included for convenience in later discussions.
The following observation is a key characterization of conflict serializability: ← A schedule is conflict-serializable if and only if its precedence graph of committed transactions (when only committed transactions are considered) is acyclic. This means that a cycle consisting of committed transactions only is generated in the (general) precedence graph, if and only if conflict-serializability is violated. ← Cycles of committed transactions can be prevented by aborting an undecided (neither committed, nor aborted) transaction on each cycle in the precedence graph of all the transactions, which can otherwise turn into a cycle of committed transactions (and a committed transaction cannot be aborted). One transaction aborted per cycle is both required and sufficient number to break and eliminate the cycle (more aborts are possible, and can happen in some mechanisms, but unnecessary for serializability). The probability of cycle generation is typically low, but nevertheless, such a situation is carefully handled, typically with a considerable overhead, since correctness is involved. Transactions aborted due to serializability violation prevention are restarted and executed again immediately.
Serializability enforcing mechanisms typically do not maintain a precedence graph as a data structure, but rather prevent or break cycles implicitly.

A precedence graph, also named conflict graph and serializability graph, is used in the context of concurrency control in databases.
The precedence graph for a schedule S contains: • A node for each committed transaction in S • An arc from Ti to Tj if an action of Ti precedes and conflicts with one of Tj's actions.

Precedence graph example

[pic][pic]
Or
D = R1(A) W2 (A) Com.2 W1(A) Com.1 W3(A) Com.3
A precedence graph of the schedule D, with 3 transactions. As there is a cycle (of length 2; with two edges) through the committed transactions T1 and T2, this schedule (history) is not Conflict serializable.

Testing Serializability with Precedence Graph

The drawing sequence for the precedence graph:- 1. For each transaction Ti participating in schedule S, create a node labeled Ti in the precedence graph. So the precedence graph contains T1, T2, T3 2. For each case in S where Tj executes a read_item(X) after Ti executes a write_item(X), create an edge (Ti --> Tj) in the precedence graph. Here this process is not happening anywhere as there is no read after write. 3. For each case in S where Tj executes a write_item(X) after Ti executes a read_item(X), create an edge (Ti --> Tj) in the precedence graph. This will bring to front a directed graph from T1 to T2. 4. For each case in S where Tjexecutes a write_item(X) after Ti executes a write_item(X), create an edge (Ti --> Tj) in the precedence graph. It creates a directed graph from T2 to T1, T1 to T3, and T2 to T3. 5. The schedule S is serializable if and only if the precedence graph has no cycles. As T1 and T2 constitute a cycle, the above schedule is not supposed to be serializable.

Q-6 During Transaction execution, a transaction passes through several states, until it finally commits and abort. List all possible sequences of states and operations through which transaction may pass.

All possible sequence of states through which transaction may pass are as follows:

1. Active state: the initial state, the transaction stays in this state while it is executing.

2. Partially committed: a database transaction enters this phase when its final statement has been executed. At this phase, the database transaction has finished its execution, but it is still possible for the transaction to be aborted because the output from the execution may remain residing temporarily in main memory - an event like hardware failure may erase the output.

3. Failed state: A database transaction enters the failed state when its normal execution can no longer proceed due to hardware or program errors).

4. Aborted state: A database transaction, if determined by the DBMS to have failed, enters the aborted state. An aborted transaction must have no effect on the database, and thus any changes it made to the database have to be undone, or in technical terms, rolled back. The database will return to its consistent state when the aborted transaction has been rolled back. The DBMS's recovery scheme is responsible to manage transaction aborts.

5. Committed state: : A database transaction enters the committed state when enough information has been written to disk after completing its execution with success. In this state, so much information has been written to disk that the effects produced by the transaction cannot be undone via aborting; even when a system failure occurs, the changes made by the committed transaction can be re-created when the system restarts.

A transaction is said to be terminated if it has either committed or terminated.

Sate diagram is as follows:

Transaction operations are as follows:

Read(X): it transfers the data iten X from the database to local buffer belonging to the transaction that executed the read operation.

Write(X): it transfers the data item X from the local buffer of the transaction that executed the write back to the database.

There are many other operations too but read and write are the important once.

-----------------------
Partially committed

committed

failed

aborted

active