Data Base Management System

DBMS Deadlock

Posted on Updated on

DBMS Deadlock

In a multi-process system, deadlock is a situation, which arises in shared resource environment where a process indefinitely waits for a resource, which is held by some other process, which in turn waiting for a resource held by some other process.

For example, assume a set of transactions {T0, T1, T2, …,Tn}. T0 needs a resource X to complete its task. Resource X is held by T1 and T1 is waiting for a resource Y, which is held by T2. T2 is waiting for resource Z, which is held by T0. Thus, all processes wait for each other to release resources. In this situation, none of processes can finish their task. This situation is known as ‘deadlock’.

Deadlock is not a good phenomenon for a healthy system. To keep system deadlock free few methods can be used. In case the system is stuck because of deadlock, either the transactions involved in deadlock are rolled back and restarted.

Deadlock Prevention

To prevent any deadlock situation in the system, the DBMS aggressively inspects all the operations which transactions are about to execute. DBMS inspects operations and analyze if they can create a deadlock situation. If it finds that a deadlock situation might occur then that transaction is never allowed to be executed.

There are a deadlock prevention scheme, which uses time-stamp ordering mechanism of transactions in order to pre-decide a deadlock situation.

WAIT-DIE SCHEME:

In this scheme, if a transaction request to lock a resource (data item), which is already held with conflicting lock by some other transaction, one of the two possibilities may occur:

  • If TS(Ti) < TS(Tj), that is Ti, which is requesting a conflicting lock, is older than Tj, Tiis allowed to wait until the data-item is available.
  • If TS(Ti) > TS(tj), that is Tiis younger than Tj, Ti  Ti is restarted later with random delay but with same timestamp.

This scheme allows the older transaction to wait but kills the younger one.

WOUND-WAIT SCHEME:

In this scheme, if a transaction request to lock a resource (data item), which is already held with conflicting lock by some other transaction, one of the two possibilities may occur:

  • If TS(Ti) < TS(Tj), that is Ti, which is requesting a conflicting lock, is older than Tj, Tiforces Tj to be rolled back, that is Ti wounds Tj. Tj is restarted later with random delay but with same timestamp.
  • If TS(Ti) > TS(Tj), that is Tiis younger than Tj, Ti is forced to wait until the resource is available.

This scheme, allows the younger transaction to wait but when an older transaction request an item held by younger one, the older transaction forces the younger one to abort and release the item.

In both cases, transaction, which enters late in the system, is aborted.

Deadlock Avoidance

Aborting a transaction is not always a practical approach. Instead deadlock avoidance mechanisms can be used to detect any deadlock situation in advance. Methods like “wait-for graph” are available but for the system where transactions are light in weight and have hold on fewer instances of resource. In a bulky system deadlock prevention techniques may work well.

WAIT-FOR GRAPH

This is a simple method available to track if any deadlock situation may arise. For each transaction entering in the system, a node is created. When transaction Ti requests for a lock on item, say X, which is held by some other transaction Tj, a directed edge is created from Ti to Tj. If Tj releases item X, the edge between them is dropped and Ti locks the data item.

The system maintains this wait-for graph for every transaction waiting for some data items held by others. System keeps checking if there’s any cycle in the graph.

1

Two approaches can be used, first not to allow any request for an item, which is already locked by some other transaction. This is not always feasible and may cause starvation, where a transaction indefinitely waits for data item and can never acquire it. Second option is to roll back one of the transactions.

It is not feasible to always roll back the younger transaction, as it may be important than the older one. With help of some relative algorithm a transaction is chosen, which is to be aborted, this transaction is called victim and the process is known as victim selection.

Posted By-: Vissicomp Technology Pvt. Ltd.

Website -: http://www.vissicomp.com

Advertisements

Indexing

Posted on Updated on

What is an Index?

  • An index is a small table having only two columns. The first column contains a copy of the primary or candidate key of a table and the second column contains a set of pointers holding the address of the disk block where that particular key value can be found.
  • The advantage of using index lies in the fact is that index makes search operation perform very fast. Suppose a table has a several rows of data, each row is 20 bytes wide.
  • If you want to search for the record number 100, the management system must thoroughly read each and every row and after reading 99×20 = 1980 bytes it will find record number 100.
  • If we have an index, the management system starts to search for record number 100 not from the table, but from the index. The index, containing only two columns, may be just 4 bytes wide in each of its rows.
  • After reading only 99×4 = 396 bytes of data from the index the management system finds an entry for record number 100, reads the address of the disk block where record number 100 is stored and directly points at the record in the physical storage device. The result is a much quicker access to the record (a speed advantage of 1980:396).

Types of Index

1

Primary Index

  • In primary index, there is a one-to-one relationship between the entries in the index table and the records in the main table.
  • Primary index can be of two types:
    i) Dense primary index: the number of entries in the index table is the same as the number of entries in the main table. In other words, each and every record in the main table has an entry in the index.

2

ii) Sparse or Non-Dense Primary Index:
For large tables the Dense Primary Index itself begins to grow in size. To keep the size of the index smaller, instead of pointing to each and every record in the main table, the index points to the records in the main table in a gap. See the following example.

3

  • As you can see, the data blocks have been divided in to several blocks, each containing a fixed number of records.
  • The pointer in the index table points to the first record of each data block, which is known as the Anchor Record for its important function.
  • If you are searching for roll 14, the index is first searched to find out the highest entry which is smaller than or equal to 14. We have 11.
  • The pointer leads us to roll 11 where a short sequential search is made to find out roll 14.

Posted By-: Vissicomp Technology Pvt. Ltd.

Website -: http://www.vissicomp.com

Normalization

Posted on Updated on

Boyce-Code Normal Form (BCNF)

  • A relationship is said to be in BCNF if it is already in 3NF and the left hand side of every dependency is a candidate key.
  • A relation which is in 3NF is almost always in BCNF. These could be same situation when a 3NF relation may not be in BCNF the following conditions are found true.
  1. The candidate keys are composite.
  2. There are more than one candidate keys in the relation.
  3. There are some common attributes in the relation
Professor Code Department Head of Dept. Percent Time
P1 Physics Ghosh 50
P1 Mathematics Krishnan 50
P2 Chemistry Rao 25
P2 Physics Ghosh 75
P3 Mathematics Krishnan 100

Consider, as an example, the above relation. It is assumed that:

  1. A professor can work in more than one department
  2. The percentage of the time he spends in each department is given.
  3. Each department has only one Head of Department.
  4. The relation diagram for the above relation is given as the following:

 

Untitled

The given relation is in 3NF. Observe, however, that the names of Dept. and Head of Dept. are duplicated. Further, if Professor P2 resigns, rows 3 and 4 are deleted. We lose the information that Rao is the Head of Department of Chemistry.

The normalization of the relation is done by creating a new relation for Dept. and Head of Dept. and deleting Head of Dept. form the given relation. The normalized relations are shown in the following.

Professor Code Department Percent Time
P1 Physics 50
P1 Mathematics 50
P2 Chemistry 25
P2 Physics 75
P3 Mathematics 100

 

Department Head of Dept.
Physics Ghosh
Mathematics Krishnan
Chemistry Rao

See the dependency diagrams for these new relations.

y1

 

 

 

 

 

Posted By-: Vissicomp Technology Pvt. Ltd.

Website -: http://www.vissicomp.com

Atomicity Consistency Isolation Durability (ACID)

Posted on

USEFULL FOR FYBSC (IT) & TYBSC (CS) STUDENTS

Atomicity Consistency Isolation Durability (ACID)

Qu.1 – What does Atomicity Consistency Isolation Durability (ACID) mean?

Atomicity Consistency Isolation Durability (ACID) is a concept referring to a database system’s four transaction properties: atomicity, consistency, isolation and durability.

Qu.2 – Explain Atomicity Consistency Isolation Durability (ACID).

A database guarantees the following four properties to ensure database reliability, as follows:

Atomicity: A database follows the all or nothing rule, i.e., the database considers all transaction operations as one whole unit or atom. Thus, when a database processes a transaction, it is either fully completed or not executed at all.

Consistency: Ensures that only valid data following all rules and constraints is written in the database. When a transaction results in invalid data, the database reverts to its previous state, which abides by all customary rules and constraints.

Isolation: Ensures that transactions are securely and independently processed at the same time without interference, but it does not ensure the order of transactions. For example, user A withdraws $100 and user B withdraws $250 from user Z’s account, which has a balance of $1000. Since both A and B draw from Z’s account, one of the users is required to wait until the other user transaction is completed, avoiding inconsistent data. If B is required to wait, then B must wait until A’s transaction is completed, and Z’s account balance changes to $900. Now, B can withdraw $250 from this $900 balance.

Durability: In the above example, user B may withdraw $100 only after user A’s transaction is completed and is updated in the database. If the system fails before A’s transaction is logged in the database, A cannot withdraw any money, and Z’s account returns to its previous consistent state.

Posted By-: Vissicomp Technology Pvt. Ltd.

Website -: http://www.vissicomp.com

Fully Functional Dependency (FFD)

Posted on Updated on

USE-FULL FOR FYBSC (IT) & TYBSC (CS) STUDENTS

FULLY FUNCTIONAL DEPENDENCE (FFD)

  • Fully Functional Dependence (FFD) is defined, as Attribute Y is FFD  on attribute” X, if it is FD on X and not FD on any proper subset of X.
  • For example, in relation Supplier, different cities may have the same status. It may be possible that cities like Amritsar, Jalandhar may have the same status 10.
  • So, the City is not FD on Status. But, the combination of Sno, Status can give only one

corresponding City, because Sno” is unique. Thus,

(Sno, Status) -> City

  • It  means  city  is  FD  on  composite  attribute  (Sno,  Status)  however  City  is  not  fully

functional dependent on this composite attribute, which is explained below:

(Sno, Status) -> City

X   Y

  • Here  Y  is  FD  on  X,  but  X  has  two  proper  subsets  Sno  and  Status;  city  is·  FD  .on  one proper subset .of X i.e. Sno Sno -> City
  • According to ‘FFD definition Y must not be FD .on any proper subset of X, but here City is FD in one subset .of X i.e. Sno, so City is not FFD on (Sno, Status)
  •  Consider another case of SP table:

Here, Qty is FD on combination of Sna, Pno.

(Sno, Pno)   ->   Qty

X      Y

Here,  X  has  two  proper  subsets  Sno  and  Pna. Qty  is  not  FD  on  Sno,  because  one  Sna  can supply  mare  than  .one  quantity.  Qty  is  also  not  FD  on  Pno,  because  .one  Pna  may  be supplied many times by different suppliers with different .or same quantities. So, Qty is FFD and composite attribute of (Sno, Pno) -> Qty.

OTHER FUNCTIONAL DEPENDENCIES

  • There are same rather types of functional dependencies, which play a vital role during the process .of normalization of data are

i)  Candidate Functional Dependency -A candidate functional dependency is a functional dependency that includes all attributes of the table. It should also be noted that a well-fanned dependency diagram must have at least one candidate functional dependency, and that there can be more than .one candidate functional dependency for a given dependency diagram.

ii) Primary Functional Dependency A primary functional dependency is a candidate functional dependency that is selected to determine the primary key. The determinant of the primary functional dependency is the primary key of the relational database table. Each dependency diagram must have one and only on primary functional dependency.  If a relational  database  table  has  .only  .one candidate  functional  dependency,  then  it  automatically  becomes  the  primary  functional dependency. Once the primary key has been determined, there will be three possible types of functional dependencies:

iii) Partial functional dependency – is a functional dependency where the determinant consists of key attributes, but not the entire primary key, and the determined consists of

non-key attributes.

iv) Transitive functional dependency is a functional dependency where the determinant consists of non-key attributes and the determined also consists of non-key attributes.

v) Boyce-Codd functional dependency is a functional dependency where the determinant consists of non-key attributes and the determined consists of key attributes.

vi) Multi-Value Dependency (MVD) occurs when two or more independent multi valued facts about the same attribute occur within the same table. It means that if in a relation R having A, Band C as attributes, B and Care multi-value facts about A, which is represented as A ->->B and A ->->C ,then multi value dependency exist only if B and C are independent on each other.

vii) Join Dependency exists if a relation R is equal to the join of the projections X Z. where

X, Y, Z projections of R.

Posted By-: Vissicomp Technology Pvt. Ltd.

Website -: http://www.vissicomp.com

Functional Dependency

Posted on Updated on

USEFULL FOR FYBSC (IT) & TYBSC (CS) STUDENTS

 

·         In the process of efficiently storing data, and eliminating redundancy, tables in a database are designed and created to be in one of five possible normal forms.  Each normal form contains and enforces the rules of the previous form, and, in turn, applies some stricter rules on the design of tables.·         A set of tables in a database are initially said to be in 0 normal form. First Normal Form:

  • Tables are said to be in first normal form when:-
  • The table has a primary key.-
  • No single attribute (column) has multiple values.-
  • The non-key attributes (columns) depend on the primary key.
  • Some examples of placing a table in first normal form are:

2

In first normal form the table : –

4

 

Second Normal Form:

  • Tables are said to be in second normal form when:
  • o   The tables meet the criteria for first normal form.
  • If the primary key is a composite of attributes (contains multiple columns), the non key attributes (columns) must depend on the whole key.
  • Third Normal Form:
  •  Tables are said to be in third normal form when:
  • o   The tables meet the criteria for second normal form.
  • o   Each non-key attribute in a row does not depend on the entry in another key column. Fourth
  • Normal Form:
  • Tables are said to be in fourth normal form when:
  • o  The table meets the criteria for third normal form.
  •  Situations where non-key attributes depend on the key column exclusive of other non-key columns are eliminated. Fifth Normal
  • Form:
  • Tables are said to be in fifth normal form when:
  • o The table meets the criteria for fourth normal form.
  • o The table consists of a key attribute and a non-key attribute only.

 

Posted By-: Vissicomp Technology Pvt. Ltd.

Website -: http://www.vissicomp.com

 

Functional Dependency

Posted on

USEFULL FOR FYBSC (IT) & TYBSC (CS) STUDENTS

Functional Dependency

Functional dependency (FD) is set of constraints between two attributes in a relation. Functional dependency says that if two tuples have same values for attributes A1, A2,…, An then those two tuples must have to have same values for attributes B1, B2, …, Bn.

Functional dependency is represented by arrow sign (→) that is X→Y, where X functionally determines Y. The left hand side attributes determines the values of attributes at right hand side.

Armstrong’s Axioms

If F is set of functional dependencies then the closure of F, denoted as F+, is the set of all functional dependencies logically implied by F. Armstrong’s Axioms are set of rules, when applied repeatedly generates closure of functional dependencies.

  • Reflexive rule: If alpha is a set of attributes and beta is_subset_of alpha, then alpha holds beta.
  • Augmentation rule: if a → b holds and y is attribute set, then ay → by also holds. That is adding attributes in dependencies, does not change the basic dependencies.
  • Transitivity rule: Same as transitive rule in algebra, if a → b holds and b → c holds then a → c also hold. a → b is called as a functionally determines b.

Trivial Functional Dependency

  • Trivial: If an FD X → Y holds where Y subset of X, then it is called a trivial FD. Trivial FDs are always hold.
  • Non-trivial: If an FD X → Y holds where Y is not subset of X, then it is called non-trivial FD.
  • Completely non-trivial: If an FD X → Y holds where x intersect Y = Φ, is said to be completely non-trivial FD.

Normalization

If a database design is not perfect it may contain anomalies, which are like a bad dream for database itself. Managing a database with anomalies is next to impossible.

  • Update anomalies: if data items are scattered and are not linked to each other properly, then there may be instances when we try to update one data item that has copies of it scattered at several places, few instances of it get updated properly while few are left with there old values. This leaves database in an inconsistent state.
  • Deletion anomalies: we tried to delete a record, but parts of it left undeleted because of unawareness, the data is also saved somewhere else.
  • Insert anomalies: we tried to insert data in a record that does not exist at all.

Posted By-: Vissicomp Technology Pvt. Ltd.

Website -: http://www.vissicomp.com