Data Base Management System
DBMS Deadlock
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.
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
Indexing
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
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.
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.
- 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
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.
- The candidate keys are composite.
- There are more than one candidate keys in the relation.
- 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:
- A professor can work in more than one department
- The percentage of the time he spends in each department is given.
- Each department has only one Head of Department.
- The relation diagram for the above relation is given as the following:
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.
Posted By-: Vissicomp Technology Pvt. Ltd.
Website -: http://www.vissicomp.com
Atomicity Consistency Isolation Durability (ACID)
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)
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
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:
In first normal form the table : –
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
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
DATA BASE ARCHITECTURE
USEFULL FOR FYBSC (IT) & TYBSC (CS) STUDENTS
DATABASE MODEL
- A database model defines the logical design of data. The model describes the relationships between different parts of the data.
- Basically three models are –
(i) Hierarchical model
(ii) Network model
(iii) Relational model
- Hierarchical model
In his model each entity has only one parent but can have several children. At the top of hierarchy there is only one entity which is called ROOT.
- Network model
In the network model, entities are organized in a graph, in which some entities can be accessed through several paths.
- Relational model
In this model, data is organized in two-dimensional tables called relations. The tables or relation are related to each other.
Posted By-: Vissicomp Technology Pvt. Ltd.
Website -: http://www.vissicomp.com
DATA BASE ARCHITECTURE
USEFULL FOR FYBSC (IT) & TYBSC (CS) STUDENTS
Data base architecture is logically divided into two types: –
1) Logical two-tier Client/Server Architecture
2) Logical three-tier Client/Server Architecture
LOGICAL TWO-TIER CLIENT/SERVER ARCHITECTURE
1) This architecture is used for user interface program and application program that runs on client side. An interface called ODBC (Open DataBase Connectivity) provides an API (Application Programming Interface) that allows client side program to call the DBMS.
2) Most DBMS vendors provide ODBC drivers. A client program may connect to several DBMS.
3) In this architecture, some variation of client is also possible for example in some DBMS more functionality is transferred to the client including data dictionary, optimization etc. such clients are called data server.
LOGICAL THREE-TIER CLIENT/SERVER ARCHITECTURE
1) This architecture is commonly used for web applications. Intermediate layer called application server or web server stores the web connectivity software and the business logic (constraints) part of application used to access the right amount of data from the database server.
2) This layer acts like medium for sending partially processed data between the database server and the client.
Posted By-: Vissicomp Technology Pvt. Ltd.
Website -: http://www.vissicomp.com
DBMS
USEFULL FOR FYBSC (IT) & TYBSC (CS) STUDENTS
Qu-What is the difference between Cluster and Non cluster Index?
A clustered index reorders the way records in the table are physically stored. There can be only one clustered index per table. It makes data retrieval faster. A non clustered index does not alter the way it was stored but creates a complete separate object within the table. As a result insert and update command will be faster.
Qu-Explain the difference between DELETE, TRUNCATE and DROP commands?
Once delete operation is performed Commit and Rollback can be performed to retrieve data. But after truncate statement, Commit and Rollback statement can’t be performed. Where condition can be used along with delete statement but it can’t be used with truncate statement. Drop command is used to drop the table or keys like primary, foreign from a table.
Qu-What is a trigger?
Databases are set of commands that get executed when an event (Before Insert, After Insert, On Update, on delete of a row) occurs on a table, views.
Qu-What is the difference between Cluster and Non cluster Index?
A clustered index reorders the way records in the table are physically stored. There can be only one clustered index per table. It makes data retrieval faster. A non clustered index does not alter the way it was stored but creates a complete separate object within the table. As a result insert and update command will be faster.
Qu-What is Union, minus and Interact commands?
MINUS operator is used to return rows from the first query but not from the second query. INTERSECT operator is used to return rows returned by both the queries.
Qu-What is a stored procedure?
Stored Procedure is a function which contains collection of SQL Queries. Procedure can take inputs, process them and send back output.
Qu-What are the advantages a stored procedure?
Stored Procedures are precompiled and stored in database. This enables the database to execute the queries much faster. Since many queries can be included in a stored procedure, round trip time to execute multiple queries from source code to database and back is avoided.
Posted By-: Vissicomp Technology Pvt. Ltd.
Website -: http://www.vissicomp.com
Visicomp Codder 
You must be logged in to post a comment.