Relational Database Design 3.1 Basic Concepts Q.1 What is relational database ? Ans. : * Relation database is a collection of tables having unique names. ¢ For example - Consider the example of Student table in which the information about the student is stored. - RollNo Name _. Phone 001 AAA 1111111111 002 BBB 2222222222 003 ccc 3333333333 Fig. Q.1.1 : Student table 3.2 Attributes and Domains Q.2 Explain the terms attributes and domains with reference to relational database = Ans. : Attribute or columns : It is a part of table that contains several records. Each record can be broken down into several small parts of data known as attributes. For example the above table Consists of four attributes such as RollINo,Name,Marks and Phone. B-D apatabase Management Systems 3-2 Relational Database Design Domain : For each attribute of relation, there is a set of permitted values called domain. For example - in above table, the domain of attribute Marks is set of all possible permitted marks of the students. similarly the domain of Name attribute is all possible names of students. That means Domain of Marks attribute is (88,83,98) 3.3 CODD's Rules Q.3 One of the rule designed by Codd's for good relational database management system is integrity independence, which states that all integrity constraints can be independently modified without the need of any change in the application. Justify the significance of rule in relational database management system. UG [SPU : Aug.-17, In Sem, Marks 5] OR Twelve rules are proposed by codd, which according to him, a database must obey in order to be regarded as a true relational database. One of the rule is comprehensive data sub language rule. ‘A database can only be accessed using a language having linear syntax that supports data definition, data manipulation and transaction management operations. Explain in brief above tule. Also state its significance. UE} [SPPU : Oct.-19, In Sem, Marks 5) Ans. : Rule 0: This rule states for a database to be relational, it must use relational capabilities to manage the database. information in an RDBMS is its Rule 1: The Information rule - All represented logically only by storing the values in tables. Each item of data in an Rule 2: The Guaranteed Access rule - RDBMS is guaranteed to be logically accessible by specifying the table name, primary key value and column name. Rule 3: The Systematic Treatment of Null Values rule - Null values are supported in a fully relational DBMS for representing missing information or inapplicable information in a systematic way which is independent of the data type: ‘A Guide for Enics Database Manage 3-3 Relational Database Des Rule 4: The Dynamic Online Catalog Based on the Relational Model rule - Database dictionary which is called as catalog-is the structure description of the complete Database and it must be Stored online. This Catalog must be governed by same rules as rest of the database. The same query language should be used on catalog as used to query database. ‘Rule 5: The Comprehensive Data Sublanguage rule - At least one well structured, well-defined language must be there which can access all the data present in the database. Rule 6 : The View Updating rule - All views of the data which are theoretically updatable must be updatable in practice by the DBMS. Rule 7 : Relational level operation - The High-level Insert, Update and Delete rule: There must be insert, delete and update operations at each level of relations. Rule 8 : The Physical Data Independence rule - Physical storage should not matter the system. Whenever any changes are made in either storage representations or access methods then it should not affect the application. Rule 9 : The Logical Data Independence rule - If any changes are made in table structure then the logical view of the user should not get affected. Fpr Rule example - if a table is split ‘into two tables internally, the view of the table to the user should be an entire table and not the split tables. Rule 10 : The Integrity Independence rule - The Integrity constraints must be defined by the RDBMS stored in the system and it should not be enforced by the external application programs, Rule 11 : The Distribution Independence rule - An RDBMS must have distribution independence. That means, even if database js scattered geographically, user should get a feel as if it is stored in one piece at one location.y pata yje 12: The Non-sub-version rule - If low-level language is allowed access the system, then that low-level language must not be able to ubvert OF bypass the integrity rules which are expressed in a higher- jevel language. pase Management Systems 3-4 Relational Database Desi; sign | Relational Integrity a4 Explain the concept of candidate key and super key. Ans. + 4) Super Key(SK) : » It isa set of one or more attributes within a table that can uniquely identify each record within a table. For example - Consider the Student table as follows - | Reg No. ‘Roll No| Phone | Name | Marks R101 001 | 11111111 | AAA | > 88 R102 002 | 2222222222| BBB | 83 R103 003 | 3333333333 | CCC | 98 R104 004 .| 4444444444 | DDD 67 | Fig. Q.4.1 ; Student The superkey can be represented as follows (RolINo, Phone, Name) Superkey Superkey 2222222222 3333333333 aaasaaasad )) and (RollNo,Phone,Name) we can © Clearly using the (RegNo ) of two students identify the records uniquely but (Name, Marks; can be same, hence this combination not necessarily help in identifying the record uniquely. — foo ‘A Guide for Engineering Students>, Database Management Systems 3-5 Relational Database Desi 2) Candidate Key(CK) : ¢ The candidate key is a subset of superset. In other words candidate key is a single attribute or least or minimal combination of attributes that uniquely identify each record in the table. Fo, example - in above given Student table, the candidate key is RegNo, (RolINo,Phone). The candidate key can be Candidate key Candidate key | ice a [ee ee [To [wr | a [© | ssssss|[ ee [J Le tess Te © Thus every candidate key is a superkey but every superkey is not a candidate key. Q.5 Explain the concepts of referential integrity constraint and entity integrity constraint with example. U@ [SPPU : May-18, Dec.-19, End Sem, Marks 5] Ans. : |) Entity Integrity Constraint This rule states that “In the relations, the value of attribute of primary key can not be null”, The NULL represents a value for an attribute that is currently unknown or is not applicable for this tuple. The Nulls are always to deal with incomplete or exceptional data. The primary key value helps in uniquely identifying every row in the table. Thus if the users of the database want to retrieve any row from the table or perform any action on that table, they musi the value of the key for that ‘row. Hence it is necessay primary key should not have the NULL value, AGuide for Enginecrigs «= dens t know ry that thewrit pase Management Systems - patal y§ 3-6 Relational Database Design « For example - NULL is not allowed !!! | ii) Referential Integrity Constraint Inrelationships, data is linked between two or more tables. This is achieved by having the foreign key (in the associated table) primary key value (in the primary - or parent - table). reference @ we need to ensure that data on both sides of the Because of this, relationship remain intact. The referential integrity rule states that key value is used it must reference a valid, existing in the parent table”. For example - Consider two tables “whenever a foreign primary key [Prego | Raine [Name | Mara | Prone pir | oor | Aw | 88 | tei R102 oot 388 3 |zzzzaza222| mis} ems ccc | m8 *issseesaeny pice} os | 000 | 67‘ Student ale as parentable CourselD CourseName Rego emt Computers R103 on Etecrical Riot This value is ens Mechanic rot present in arent tabie ena Chil ‘Course table as child | a "A Guide for Engineering StudentsRelational Database © In above relation, the registration no. R555 is not fee is present in the course table, then we say referential integrity constraint. Database Management Systems 3-7 Design NG still if j ae it that it is not following 3.5 Enterprise Constraints | Q.6 Write short note - Enterprise Constraints. Ans. : * Enterprise constraints are also called as semantic constraints, ¢ The enterprise constraints are basically the additional Tules specified by users or database administrators. These Constraints are normally based on multiple tables. Examples of enterprise constraints are - 1) The salary of teacher should not exceed the salary of Principal. 2) A Student can not opt for more than two courses at a time. 3) A class can have maximum 50 students. | 3.6 Features of Good Relational Designs Q.7 What are two primary goals of relational database design ? Ans. : There are two primary goals of relational database design - i) To generate a set of relation schemas that allows us to store information without unnecessary redundancy and ii) To allow us to retrieve information easily. Q.8 Explain what is meant by repetition of information and inability to represent information. Explain why each of these properties may indicate a bad relational database design. USP [SPPU : Dec.-18, End Sem, Marks 5] Ans, : Repetition of information and inability to represent the required information are considered to be bad features of relational design. Consider following schema.7 tase Mans ement Systems 3:8 Relational Database Design C DeptID Deptloe | DeptiD | DeptName | DeptLoc | DeptName | 1ooo0 | Wor | XYZ | Pune 20000 | 101 | x¥Z | Pune 30000 | tol | x¥Z | Pune Pee ect ppp | 40000 102 PQR | Mumbai we want to insert a record 5,EEE,50000 for the DeptID 101, here will be repletion of information about DeptID, ptLoc i.e. (101,XYZ,Pune). That means if we want ration (insertion, updation, deletion) on the ‘ot cause repetition of information. Now if then again ¢ DeptName and De| rm some opel relational schema then it should no 1s bad database design. to perfor The above scenario indicate Q.9 What is normalization ? What Is the need of normalized database ? UG [SPPU : Dec.-17, End Sem, Marks 5] Ans. ¢ « No that it meets two basic requirements : 0 redundancy of data (all data is stored in only one rmalization is the process of reorganizing data in a database SO 1) There is ne place) and 2) Data dependencies together) are logical (all related data items are stored Need for normalization 1) It eliminates redundant data. 2) It reduces chances of data error. 3) The normalization is important becal take up less disk space. 4) It also help in increasing the performance. use it allows database to 5) It improves the data integrity and consistency. "A Guide for Engineering Students*;.; Database Management Relational Database Desig, del overall design of database ? How normalization let mal is used ¢ to nae 5 these anomalies ? - USP [SPU : May-18, End Sem, Marks 5) Ans, : * Redundancy is at the root of several problems associated With relational schemas. Problems caused by redundancy : Following problems can be caused by redundancy- i) Redundant storage : Some information is stored Tepeatedly, ii) Update anomalies : If one copy of such repeated data js updated then inconsistency is created unless all other copies are similarly updated. iii) Insertion anomalies : Due to insertion of new record Tepeated information get added to the relation schema. iv) Deletion anomalies : Due to deletion of particular record some other important information associated with the deleted record get deleted and thus we may lose some other important information from the schema. Example : Following example illustrates the above discussed anomalies or redundancy problems. Consider following Schema in which all possible information about Employee is stored. EmpiD | EName | Salary | DeptiD | DepiName DeptLoc 4 AAA 410000 401 XYZ Pune 2 BBB 20000 (| 101 xyz Pune 3 ccc 30000 401 XYZ Pun: [4 DDD 40000 102 POR] | Mumbai Redundaneyii A Guide Retell a aepase Management Systeme _3 20 __Relational Database Design 1) Redundant storage : Note that the information about em DeptName and DeptLoc is repeated. Oe 2) Update anomalies : In above table if we change DeptLoc of Pune to Chennai, then it will result inconsistency as for DeptID 101 the DeptLoc is Pune. Or otherwise. we need to update multiple copies of DeptLoc from Pune to Chennai. Hence this is an update anomaly. 3) Insertion anomalies : For above table if we want to add new tuple say (5, EEE,50000) for DeptID 101 then it will cause repeated information of (101, XYZ,Pune) will occur. 4) Deletion anomalies : For above table, if we delete a record for EmpID 4, then automatically information about the DeptID 102, DeptName PQR and DeptLoc Mumbai will get deleted and one may not be aware about DeptID 102. This causes deletion anomaly. Normalization : Refer Q9. 3.8 Atomic Domains and First Normal Form Q.11 Explain the concept of atomic domain and First Normal Form. Ans. + « By atomic value, we mean that each value in the domain is indivisible. «The first normal form rule defines that all the attributes in a relation must have atomic domains. The values in an atomic domain are indivisible units. The table is said to be in INF if it follows following rules - i) Itshould only have single (atomic) valued attributes/columns. ii) Values stored in a column should be of the same domain. iii) All the columns ina table should have unique names. + iv) And the order in which data is stored, does not matter. 4 Guidle for Eng usdentsDatabase Management Systems 3-11 Relational Database De. a © Consider following student table Student : _ sid sname — Phone 1 AAA M1 22222 2 BBB 33333 3 ccc 44444 55555 ¢ As there are multiple values of phone number for sid 1 and 3, the above table is not in INF. We can make it in INF. The conversion is as follows - sid | | 3.9 Decomposition using Functional Dependencies Q.12 Explain in brief with suitable example full functional dependency and partial dependency. 5S [SPPU : Oct.-19, In Sem, Marks 3] Ans. : ¢ Definition : A functional dependency A->B in a relation holds if two tuples having same value of attribute A also have the same value for attribute B. It is denoted by A->B where A is calleq determinant and B is called dependent. 4 — a :ase Management Systems. 3-12 Relational Database Design pata ‘ For example - Consider Student table as follows Roll bp Nite hs City | ana | Man 2 jane BEB | Pune 3 ccc Gandhinagar Here Roll ->Name hold But Name->City does not hold In above table, student roll number is unique hence each student’s name and city can be uniquely identified using his roll number. But using name we cannot uniquely identify his/her city because there can be same names of the students. Similarly using city name we can not identify the student uniquely. As in the same city may belong to multiple students. Q.13 State inference rules of Armstrong’s axioms. Ans. = The closure set is a set of all functional dependencies implied by 4 given set F. It is denoted by Ft The closure set of functional dependency can be computed using basic three rules which are also called as Armstrong’s Axioms. These are as follows - i) Reflexivity : If X 2 Y, then X 7 Y ii) Augmentation : If X > Y, then XZ > YZ for any Z iii) Transitivity : IfX + Y and Y > Z, then XZ In addition to above axioms some additional rules for computing closure set of functional dependency are as follows - © Union: If X + Yand X + Z then X > YZ © Decomposition : If X + YZ, then X > Yand X > Z ‘A Guide for Engineering StudentsDatabase Management Systems 3-13 Relational Datab, 8e Dy Q.14 Compute the cl a re of the following set F of funcy dependencies for relational schema R = (A.B,C,D.E) 4 ctlonal CD->E,B->D,E->A Be, + Ans. : The closure of F is denoted by F and it can be co; following steps Mputed jy Step 1: As A -> BC is given we get A->BandA->C By decomposition rule Step 2: As A>B (Refer step 1) B->D (given) A>D (transitivity rule) Step 3: A->CD because A ->C and A->D (From step 'l and Step 2 applying union rule) Step 4: CD->E (given) A>E (transitive rule as A->CD, CD->E hence A->E) Step 5: Since A— A, we have (reflexive), A— ABCDE from the above steps (union) Step 6: Since E — A, E— ABCDE (transitive) Step 7: Since CD + E, CD > ABCDE (transitive) Step 8: Since B > D and BC — CD, BC > ABCDE (augmentative, transitive)pase Management Systems 3-4 Relational Database Design step 9: Also. C7 & Thus any functional dependency with A, E, BC or CD on the left hand side of the arrow is inF. ats Give oe axloms and using it find the closure of flowing ABs Oe /D->AC, DDE Ans. + step 1: Consider the rules D -> AC and D ->E pD-> ACE (Union rule) step 2: Consider AB -> C then we get D—D,BD>D »A>CandB>C (decomposition rule) Thus F ={A->C,B->C,D-> ACE} Give R = {A,B,C,G,H,I}. The following set F of functional pendencies holds A-> B,A-> C,CG->H,CG->1,B->H Computer AG* . Is AG candidate key ? Ans. : step 1: A->B,A->C, Hence add A, B, C to the set of AG . step2: A> BB->H, hence add H to the set of AG” step 3: CG->I, hence add] to the set of ‘AG . Also add G to the set. Thus (AG) = {A,B,C,G,H,} = Relation R Hence (AG) is a candidate key. Q.17 Compute the closure of R(A,B, C,D,E) with the following set of functional dependencies A -> BC, CD -> E,B->D,E->A List the candidate keys of R Ans. ¢ step 1: A-> BC hence add A,B,C to (Ay ‘A ->BC can be decomposed into A > B and A -> C. Also B > D. Thus A -> D is also true by transitivity rule. Hence add D to (A)" ah A Guide for Engineering Students>. Relational Database De; >C,A->D « By union rule A > CD, As CD>Eadd Eto (A) (ay = {ABCDE} Step2 : Consider (B) = {B,D}: Database Management Systems 3-15 FR hence it is not a candidate key Step 3 : Consider (BC) = {B,C,D,E,A} = {A,B,C,D,E} = R. Hence it is a candidate key Step 4: Consider CD -> E, E> A, hence (CD)+= {A,B,C,D.E}, Hence it is a candidate key Step 5: Consider E > A, A -> BC, B > D,CD>E. Hence (E) = {A,B,C.DE} is a candidate key, Thus we get the candidate keys as {A,BC, CD, E} Q.18 Consider schema R = (A,B,C,G,H,I) and the set F of functional dependencies {A-> B,A-> C, CG -> H, CG-> 1, B-> H}. Use (F)* Prove (AG)* «> | Ans. : Step 1: AsA>B BH AH (Transitivity rule) Step2: CG>H CG>1 CG->HI (Union rule) Step3: ADC CG>1 AG>I (Pseudo transitive rule) Thus AG -> lis proved (F) = {A>B,A>C,CG>H,CG>1LB>HA CG >HI, AG>T} >H, A Guide for Engineeringnent Systems Ans: * from all the FDs of FD2. from all the FDs of FD1. For given two sets 1 tent ? iS 2) A-> BC 1) AB’? Cc D-> AE WeAC pase Manage 3-16 Relational Database Design patal “4g Here are two sete of FDs for RIA.B,C.D,E). Are they 2E Two sets of FDs are said to be equivalent if Rule 1 :1f FD2 > FD1. That means all FDs of FD1 can be derived Rule 2: If FD1 > FD2, That means all FDs of FD2 can be derived Rule 3: Ifboth rule | and rule 2 are true then FD1 = FD2. step1: We will first check if all the FDs of FD1 are present in FD2 A-> Bis present in FD1. A->BC is in FD2, that also means A>BandA>Cby ieD->A,D>Cby decomposition rule. decomposition rule Similarly AB -> C is in FD1 Hence + 1(A) = {ABC} (A) = {ABC} + 1 w. (AB) = {A,B,C} As D-> AE then by decomposition rule, D>A,D>E | D>AC ‘As A->B, then by transitivity tuleD-> A, A>B,D>B The D> A,A-> Band C 1. (0) = {A,B,C.D.E} D->A,D->B,D->Cby transitivity rule D-> Eis given |.) = ABODE) A Guide for Engineering StudentsDatabase Management Systems 3-17 Relational Database Dex eso, Step 2: We will first check if'all the FDs of FD2 are present j in a (Ay = {A,B,C} (ay = {A,B,C} (AC) = {ABO} (D)" = {4,B,C,D,E} .E) 7. | + FD1 and FD1 > Fpp, Hence both the sets are equivalent. Q.20 Consider two sets of functional dependency. F = {A-> C,AC-> D, E-> AD, E -: cece -> CD, . > AH}. Are they equivalent ? : We will find the FDs of both F and G and then check for F iosteag se Step1: ForF Using G functional dependencies - (A) = {ACD} © AsA>CDisinG (AC) = {ACD} © AsA>CDisinG ©) = {ACDEH} -AsE>AH,A->CDisinG Using F functional dependencies - (A). = {ACD} © As A> Cand AC > Dis inF (AC) = {ACD} < AC>DisinF (E) = {A.C.D.EH} CAsE>AD,E>Hand A> Cis inF Step2: ForG i Using F functional dependencies - (A) = {ACD} © AsA->Cand AC>DisinF (€) = {ACDEH) CAsE->AD,E>HisinF Using G functional dependencies - (A) = {A,C,D} — As A> CDis inG (BE) = {A.C.D.EH) CAsE> AH and A> CDis inG Step 3: From both these steps G2F and F2G " Hence F and G are equivalentsaa Mana ment Systems _3-18 Relational Database Design ye xplain the concept of Minimal cover, , Formal definition : A minimal cover for a set F of FDs is a G of FDs such that : 1) Every dependency in G is of the form X -> A, where A is a single gat E Ans: attribute. 3) The closure F is equal to the closure Gc. 3) If we obtain a set H of dependencies from G by deleting one or more dependencies or by deleting attributes from a dependency in + G,thenF #H. 22 A relation R(A,C,D,E,H) satisfies the following FDs A -> C, Re.» D, E-> AD, E-> H, Find the canonical cover for this set of FD’s. ‘Ans. : For obtaining canonical cover we have to find the redundant entries from both LHS and RHS and eliminate them. step 1: Suppose we minimize LHS first, then go through each production tule one by one considering LHS. A->C, Keep itas itis. AC -> D, Here A > C and A -> D, So we remove A > C , hence A-> Dis kept by eliminating C from LHS. E-> AD, keep it as it is as E is a single attribute at LHS. E->H, keep it as it is Step 2: Now we will minimize RHS. A->C, keep itas itis A->D, keep itas it is E-> AD. That means E -> A and E -> D. As A -> Dis also present in the FD, so we get E -> Aand A -> D. Thus E -> D is transitive . Hence neglect it. So we keep E -> A only E> H, Keep it as it is. Gao A Guide for Engineering StudentsDatabase Management Systems 3-19 Relational Datatng 1 Desi Step 3: From steps | and 2. we get minimal cover of FD as i A>C A>D E>A E>H Hence the canonical for is A>CD E>AH Q.23 What is functional dependency ? Find the minimal cover using the minimal cover algorithm for the following functional dependency F = {AB-> D,B -> C, AE-> B, A-> D, D -> EF} Ans. : Step 1: We will make right hand sides atomic AB->D B>C AE->B A>D D>E D->F Step 2: Now we will remove redundant FDs using RHS ¢ For AB > D. Now compute (AB)+ without considering the AB -> Di.e.{G-(AB->D)} We get (AB)+ = {ABCDEF}. That means we can remove AB>D as it is redundant entry. Hence grammar is BC AE->B A>D D->E D->Fpat pase Management Systems 329 Relati —SAtttonal Database Design For C compute (B)+ by Considering {G - (B -> ©} ore {AEBDF}. As C is not Present in this set, That means p-> Cis not redundant. So we can not remove it, Hence grammar is BC AE>B A>D DoE D>F For AE -> B, we will compute (AE)+ under (G-(AE>B)) (AE)+ = {AEDF} as B is not Present in (AE}+. So we cannot remove AE -> B from grammar. Hence grammar will be BC AE>B A>D D>E D>F For A -> D, we will compute(A)+ under (G - (A>D)) (A)+ = {AEBC}. As D is not Present in (A)+, hence we can not eliminate A > D. The grammar is B>C AE->B A>D DE D->F For D -> E, compute (D)+ under (G - (D > E)) (D)+ = {DF}. As E is not present in (D)+, We cannot remove D->E Becooe) A Gulde for Engineering StudentsDatabase Management Systems 3-21 Relational Da e Deg ¢ ForD->F, compute (D)+ under (G-(D -> F)) “ey (D)+ = {DE}. As F is not present in (D)+, We cannot remoy, D->F. Finally the grammar is B->C AE>B A>D D>E D>F Step 3 : Remove redundant entries based on RHS B->C,A>D,D->E and D ->F as LHS is atomic. Now we consider AE -> B For A : compute E+ with respect to (G - (AEB) U (EB)) E+ using {BC, EB, AD, DE, DF} = EBC E+ doesn’t contain A, so A not redundant in AE>B For E ; compute A+ with respect to (G - (AEB) U (A—B)) A+ using {B+C, A+B, A>D, DE, DF} = ABDEFC A+ contains E, so E is redundant in AEB Hence we consider AE-> BasA>B. Finally minimal closure is {B -> CA > B, A> D, D> E, D->F} for Decomposition — Q.24 What is decomposition ? Ans, : ¢ A decomposition of relation schema R consists of replacing the relation schema by two relation schema that each contain a subset of attributes of R and together include all attributes of R by storing projections of the instance. For example - Consider the following table Neen TTT TTT cerealpile © ployee Deparment table as follows : : (a [sme Age | city | Salary | Deptt | —Depetame ol ABC | 29 Pune 20000 | D001 Finance | (eo pQR | 30 Pune | 30000 | D002 | _ Production oo LMN | 25 | Mumbai | 5000 | D003 Sales oa | XYZ_| 24 | Mumbai_| 4000 | Doo4 | Marketing 0 stu | 32 | Hyderabad | 25000 | D005 | Human Resource « We can decompose the above relation Schema into two relation schemas as Employee (Eid, Ename, Age, City, Salary) and Department (Deptid, Eid, DeptName) as follows - Employee Table : : “gid |. mame | Age | Cty | Salary E001 ABC 29 Pune | 20000 E002 PQR 30 Pune 30000 | £003 LMN 25 Mumbai 5000 E004 XYZ 24 Mumbai 4000 E005 STU 32 Hyderabad 25000 Department Table Detid | ‘Eid. DeptName D001 E001 - Finance D002 E002 Production D003 E003 Sales pos | E004 Marketing D005 “E005 Human Resource ¢ The decomposition is used for eliminating redundancy. A Guide for Engineering Studentssean Petabase De Q.25 State and explain the properties assoc, 7 gy decomposition. with ‘Ans. ; There are two properties associated with decomposition a those are - Mn 1) Loss-less join or non loss decomposition : When all inform, found in the original database is preserved after decompositig call it as loss less or non loss decomposition. Database Management Systems 3-23 Relational lation N, We 2) Dependency preservation : This is a property in Which th, constraints on the original table can be maintained by simply enforcing some constraints on each of the smaller relations, Q.26 List the properties of decomposition. Explain lossless joi, with example. BaF [SPPU : May-38, End Sem, Marks 6) Ans. : Properties of Decomposition : Refer Q.25. Lossless join: The lossless join can be defined using following three conditions : i) Union of attributes of R1 and R2 must be equal to attribute of R, Each attribute of R must be either in R1 or in R2. Att(R1) U Att(R2) = Att(R) ii) Intersection of attributes of R1 and R2 must not be NULL. Att(R1) N Att(R2)4#® iii)Common attribute must be a key for at least one relation (RI or R2) Att(R1) M Att(R2) -> Att(R1) or Att(R1) N Att(R2) -> Att(R2) Q.27 Consider the following relation R(A, B, C, D)and FDs A->BC, is the decomposition of R into R1(A, B, C), R2(A, D). Check if the decomposition Is lossless join or not. Ans. : Stép 1: Here Att(R1) U Att(R2) = Att(R) ie R1(A,B,C) U R2A,D) = (A,B,C,D) ie R. Thus first condition gets satisfied.t Systems| 3-4 patase ‘Managemen quo Here RIR2= (AP, Thus AWRI) 1 ArtR2) 4, Here the econd condition gets satisfied. ‘ op 32 AWRI) M1 AM(R2) > {A}, No - pat : }. Now (A}t = {A,B,C} ie. : tes of R1. Thus the third condition gets satisfied. } Le. Relational Database Design si ttribu : his shows that the given decomposition is a lossless join. 0.26 What is dependency preservation ? Ans: + Definition + A decomposition D = {R1, R2, R3....Rn} of R is dependency preserving for a set F of functional dependency if - (FLUF2U... UFm)=F. + If decomposition is not dependency-preserving, some dependency js lost in the decomposition.- a.29 Suppose we decompose the scheme R=(A,B,C,D,E) into (ABC) and (A,D.E). Show that this decomposition is the lossless Gecomposition if following functional dependencies hold : A->BC,CD->E, B->D Show that decomposition is dependency preserving decomposition. Ams. + : step 1 : Construct table with five columns for given five attributes i.e. A,B, C, D, E and two rows for given two relations i.e. RI (A. B, Cc) and R2 (A, D, E). A B Cc D E Rl R2 step 2: The attributes of the scheme of RI are A, B, C. Therefore, we place d,, Og and 1, under these columns respectively. The remaining entries of this row are filled with B,, and B,,. Same as for R2 have attributes A, D, E. Therefore, we place 4, Op and O, under these columns respectively. The remaining entries of this row are filled with Bop and Bac. A B c D E Rt | og | % | % | Bip Bie R2 | a | Bop | Bc | Mp | % ‘A Guide for Engineering StudentsDatabase, Management ‘Systems 3-25 Relational Da tals, base py, Peay Step 3: ‘e check if the two rows of the 4, ‘ab, i) Considering A BC Ww the same value under the columns that make up the dete, have FD. Rows RI and R2 has values Oty under column A, eR A » Theres, we need to equate all the corresponding entries for ee under columns B and C. Se Toy, Since entry under column B is (for row R1) and coluny Og (for row R2). In Cig | | ] A B Cc D E RI | Oy Op Ae Bin | Be oe D> E, we check for rows that have the same valu, C and D. Here, rows do not same values, the ia remain unchanged and we repeat step 3 by another FD. iii) Considering B 7 D, we check for rows that have the same value in the columns B here rows have same values Op under the Therefore, We need to equate all the corresponding D. Since entry under column ii) Considering cl in the columns column B. entries for these rows under column Dis Op for row RI. A B ri | % | %B R2 Now there are no more FDs to consider. Step 4: Since row R2 has become OL,» Ops Sher Op» dt ie. R2 has all e decomposition is lossless. o. values. Hence 3,11 Two Normal Form Q.30 Explain why database normaliz relational database design ? Explain wi second normal form. [3PPU : Oct-49, InSem, Marks 7] ation is required for good ith example requirements ofase Management System c patavase MEE Relational Database Design a! Need of Normalization ; Refer Q.9, Anse! wo Normal » Fora table to be in the Second Normal Form, following conditions must be followed Form : i) It should be in the First Normal form. ii) It should not have partial functional dependency. » For example : Consider following table in which every information about a the Student is maintained in a table such as student id(sid), student name(sname), course id(cid) and course name(cname). Student_Course oe sid sname cid | cname | 1 | aa 101 c.| 2 BBB 102 Co | 3 | ce fc 4 DDD | 103 | Java | This table is not in 2NF. For converting above table to 2NF we must follow the following steps - Step 1; The above table is in INF. Step 2: Here sname and sid are associated similarly cid and cname are associated with each other. Now if we delete a record with sid = 2, then automatically the course C++ will also get deleted. Thus, sid->sname or cid->ename is a partial functional dependency, because {sid,eid} should be essentially a candidate key for above table. Hence to bring the above table to 2NF we must decompose itas follows : 4 Guide for Engineering SuulensDatabase Management Systems ge27 R A y 2 cational — ational Datay 7a Databa tbare i, in Student | sid | sname cid XS Here candidat, : ndidate Key 1 | AAA 101 (Sid, cig) '8 a _, and (Sid, cid) spay Here candidate key is cid here cid- > cname * Thus now table is in 2NF as there is no partial functional dependency. ———— | 3.12. Third Normal Form | Q.31 Explain Third Normal Form with suitable example. Ans. : © A table is said to be in the third normal form when, i) It is in the second normal form.(i¢. it does not have partial functional dependency). ii) It doesn't have transitive dependency. Or in other words «In other words 3NF can be defined as : A table is in 3NF if 2NF and for each functional dependency X>Y at least one of the following conditions hold : i) X isa super key of table. Y isa prime attribute of table. ee "A Guide for Engineering Students | _— —— —Management Systems 3-28 Relational Database Design Consider following table Student_details as tase” mple + , for examp follows ~ oe sname zipcode cityname state r) ra] AAA Wil Pune Maharashtra 22222 aa BBB Surat Gujarat ccc 33333 Chennai Tamilnadu fa 7 | ppp | 44444 | Jaipur | Rajastan 5 EEE 55555 Mumbai | Maharashtra Here » super keys? {sid}, {sid,sname}, {sidsname,zipcode}, {sid,zipcode,cityname}... and so on. « Candidate keys : {sid} « Non-prime attributes : {sname,zipcode,cityname,state} « The dependencies can be denoted as sid->sname ” sid->zipcode zipcode->cityname cityname->state « The above denotes the transitive dependency. Hence above table is not in 3NF. We can convert it into 3NF as follows : Student sid sname zipcode 1 AAA M111 2 BBB 22222 3 ccc 33333 4 DDD 44444 5 EEE 55555 A Guide for Engineering StudentsDatabase Managemen 3-29 ___Relationat Datay, ——atabnce ty, Zip ———_ Pune Maharashtra | __——~ ~ Surat Gujarat —_ Chennai Tamilnadu 4 Jaipur Rajasthan Mumbai Maharashtra Q.32 Students_Detail (Stud_id, Stud_name, Zip, City) Consider above schema, check whether it is in 3NF, if not justi and propose the schema in 3NF. ty B® [SPU : Oct.-18, In Sem, Marks 5) Ans. : The given schema is not in 3NF because there exists following transitive dependencies. Because city is associated with Stud_id and city depends upon the zip code. When this dependency is removed then the table will be in 3NF, Iris as follows - Student | stud id Stud_name | Zip Student_address Zip City Q.33 Consider a table having structure student (Roll_no, Branch_code, Marks_obtained, Exam_name, Total_marks). Note following point i) Composite primary key for Branch_code). ii) Branch_code column stores the code of branch for which students have taken admission. iii) Exam name attribute is depend on both roll_no and branch_code. : iv) Total marks attribute is depend on exam. student table is (Roll_no,nt Systems 3-30 Relational Database Design ab base Manageme pe dering above requirement state whether the table created is cond normal form or not ? Why ? If not in third normal for inf! the database design for above requirements which is in td normal form. GH [SPPU : Oct.-19, In Sem, Marks 7] | Clearly the above table is not there in third normal form as there exists transitive dependencies. This is because, exam_name axtribute depend upon the primary key roll_no and branch_code and total marks are associated with exam_name attribute. Roll_no Branch_code marks_obtained To convert the above schema to third normal form we need to decompose the schema into different relations - Student_info [Rott | branch_code | Exam_name Exam_info Exam_name | Total_marks | Marks_obtained | Q.34 Explain why database normalization is required for good relational database design ? Explain with example requirements of different normal forms like INF, 2NF and 3NF. UH [SPPU : Dec.-18, End Sem, Marks 5] Ans. : Need for Normalization : Refer Q.9. ANF: Refer Q.14. 2NF: Refer Q.30. ‘NF: Refer Q.31. e A Guide for Engineering StudentsDatabase Management Systems Q.35 Explain 3NF and BCNF. Also enlist their differences, U@ [SPU : May-18, Dec, Ans. : 3NF : Refer Q.31. BCNF : 18,19, End Sem, Mats 5 | ¢ Fora table to be in] BCNF, following conditions must be Satisfieg i) Rmustbein3 Normal Form ii) For each functional dependency ( X + Y ), X should bea Super key. In simple words if Y is a prime attribu te then X can not be non prime attribute. For example - Consider following table that Tepresents that g student enrollment for the course - Enrollment table sid Course Teacher 1 ce Ankita il Java Poonam 2 Cc Ankita 3 CH Supriya 4 c Archana From above table following observations can be made : © One student can enroll for multiple courses. For example student with sid = 1 can enroll for C as well as Java. © For each course, a teacher is assigned to the student. There can be multiple teachers teaching one course for example course C can be taught by both the teachers namely - Ankita and Archana. The candidate key for above table can be (sid, course), because using these two columns we can find, A Gulde for Engineering Studensage Manas nt Systems 3-32 Relational Database Design pal re above table holds following dependencies . sid course)->Teacher o (sid. a Teache 4 The above table is not in BCNF because of the dependency teacher? course. Note that the teacher is not a superkey or in other words, teacher is a non prime attribute and course is a prime attribute and non-prime attribute derives the prime attribute. » To convert the above table to BCNF we must decompose above table into student and course tables r->COUrSE student sid Teacher 1 Ankita 1 Poonam | 2 Ankita 3 Supriya 4 Archana Course Teacher Course Ankita Cc Poonam Java Ankita Cc Supriya CH Archana Cc Now the table is in BCNF ST * ‘A Guide for Engineering StudentsDatabase Management Systems 3-33 1 SNF stands for Third Normal Form. 2. | The table is in 3NF iffitis | in 2NF and for each functional dependency | X>Y at least following condition hold: |.G) X isa superkey, | (ii) Y is prime attribute of | aaa ee Sr.No. 3NF 3 rt should be super key, BNF stands for Boyes Codd Normal Fom,. The table isin BONE j in3 Pit is normal form ang for each relation X->y x table. ee 3. | 3NF can be obtained Dependencies may not be without sacrificing all preserved in BCNF, | dependencies. 4. | Lossless decomposition can | Lossless decomposition is be achieved in 3NF. hard to obtain in BCNF. 5. | 3NF can be achieved For obtaining BCNE we | without loosing any may loose some | information from the old | information from old table. | | table. END ...&Unit iv Database Transaction Management | 4.1 Introduction to Database Transaction .1 Define the term - transaction. Ans. « Definition of Transaction : A transaction can be defined as a group of tasks that form a single logical unit. For example - Suppose we want to withdraw & 100 from an account then we will follow following operations : 1) Check account balance 2) If sufficient balance is present request for withdrawal. 3) Get the money 4) Calculate Balance = Balance - 100 5) Update account with new balance. The above mentioned five steps denote one transaction. | 42. Transaction States L = Q.2 Transaction during its execution should be in one of the different states at any point of time, explain the different states of transactions during its execution. U® [SPPU : Dec. 17, End Sem, Marks 8] Ans. : Each transaction has following five states : 1) Active : This is the first state of transaction. For example : Insertion, deletion or updation of record is done here. But data is not saved to database. eum i> ab4-2 Database Transac tion Ma, ton Manacey, ger "emp Fig. Q.2.1: Transaction states 2) Partially committed : When a transaction executes its final operation, it is said to be in a partially committed state, 3) Failed : A transaction is said to be in a failed State if any of the checks made by the database Tecovery system fails, A failed transaction can no longer proceed further. 4) Aborted : If a transaction is failed to execute, then the database Tecovery system will make sure that the database is in its Previous consistent state. If not, it brings the database to consistent state by aborting or rolling back the transaction. 5) Committed : If a transaction executes all its operations successfully, it is said to be committed. This is the last step of a transaction, if it executes without fail. i | 43 ACID Properties | ei ree eh sneae Q.3 State and explain in brief the ACID properties. During execution of transaction, a transaction passes through several states, until it finally commits or aborts. List all possible sequences of states through which a transaction may pass. Explain why each state transition occurs. SP [SPPU : May-18,19, Dec,-18,19, End Sem, Marks 8] Ans. : Acid properties : 1) Atomicity : This property states that each transaction must be considered as a single unit and must be completed fully or not completed at all, = AGuilde for —_cae igement Systems 4-3 Database Transaction Management vans" in the database is left half completed. Not i ; al . should be in a state either before the transaction atabas A : Ds seution OF after the transaction execution. It should not be in a ex state ‘executing. or example - In above mentioned withdrawal of money transaction all the five steps must be completed fully or none of the step iS completed. Suppose if transaction gets failed after step 3, then the customer will get the money but the balance will not be updated accordingly. The state of database should be either at pefore ATM withdrawal (i.e customer without withdrawn money) or after ATM withdrawal (i.e. customer with money and account updated). This will make the system in consistent state. 2 Consistency : « The database must remain in consistent state after performing any transaction. For example : In ATM withdrawal operation, the balance must be updated appropriately after performing transaction.’ Thus the database can be in consistent state. 3) Isolation : Ina database system where more than one transaction are being executed simultaneously and in parallel, the property of isolation states that all the transactions will be carried out and executed as if it is the only transaction in the system. No transaction will affect the existence of any other transaction. . For example : If a bank manager is checking the account balance of particular customer, then manager should see the balance either before withdrawing the money or after withdrawing the money. This will make sure that each individual transaction is completed and any other dependent transaction will get the consistent data out of it. Any failure to any transaction will not affect other transaction in this case. Hence it makes all the transactions consistent. A Guide for Engineering StudentsDatabase Management Systems 4-4 Database Transaction a Manaccney 4) Durability : © The database should be strong enough to handle any failure. If there is any set of insert /update. then it should be able to hi and commit to the database. If there is any failure, the database should be able to Fecover it to the consistent state. For example : In ATM withdrawal example, if the system failure happens after customer getting the money then the system should be strong enough to update Database with his new balance, after system recovers. For that purpose the system has to keep the log of each transaction and its failure. So when the system Tecovers, jt should be able to know when a system has failed and if there is any pending transaction, then it should be updated to Database. Stem andle Transaction states : Refer Q.2. oi Q.4 Explain the concept of serial and Non-serial schedule. Ans. : * Serial schedule : The schedule in which the transactions execute one after the other is called serial schedule. It is consistent in nature. For example : Consider following two transactions T1 and 12. Ti T2 R(A) WA) RB) Wo)cement Systems agement 5 4-5 r ut Mat 5. Database Transaction Management s of trans | atthe operation: | transaction T1 on data items A and then B excotes and then in transaction T2 all the operations on data items aand B execute, The R stands for read operation and W stands for write operation. ial schedule : i + Non serial s! i schedule in which operations present within the transaction are intermixed. This may lead to conflicts in the result or inconsistency in the resultant data, For example - « Consider following two transactions, R(A) W(A) R(A) We) R(A) We) R(B) We) The above transaction is said to be non serial which result in inconsistency or conflicts in the data. ‘onflict and View Q.5 Explain the concept of conflict serializability with example. Ans. : © Definition ; Suppose T, and T, are,two transactions and I, and 1, are the instructions in T, and T, respectively. Then these two transactions are said to be conflict serializable, if both the instruction access the data item d and at least one of the instruction is write operation. AG for Engineering SuudentsDatabase Management Systems 4-6 Database Transaction " Ma, ing for serializability Shen * Following method is used for testing the Serializability « sto conflict serializability we can draw a graph G = test the We V = Vertices which represent the number of transactions, : here ¢ E=Edges for conflicting pairs, Step 1: Create a node for each transaction. Step 2: Find the conflicting pairs RW, WR, WW) on the = variable (or data item) by different transactions, . Step 3: Draw edge for the given schedule. Consider follo 1. T; executes write(Q) before T; executes read(Q), th from T; to T;. 2. T; executes read(Q) before T; executes write| from T; to Tj. wing Cases en draw Cdge (Q), then draw edge 3. Tj executes write(Q) before T executes write(Q), then draw edge from T, to T,. Step 4: Now, if precedence graph is cyclic then it is a Non conflict serializable schedule and if the precedence graph is acyclic then it is conflict serializable schedule. Q.6 Check whether following schedule is conflict serializable or not. If it is not conflict serializable then find the serializability order. Tl T2 T3 R(A) R(B) R(B) WB) A Guide for Eng,Mans cement Systems 4-7 Database Transaction Management a yee — Ans? _ We will read from top to bottom and build a precedence gtel eo | conflicting entries. We will build a precedence graph by gat OF node from each transaction. In above given scenario as three transactions, there will be two nodes namely Tl T2 and per ° ® @ ® Fig. 6.1 step 2: The conflicts are found as follows - P| A Guide for Engineering StudentsDatabas 4-8 Database Management Sus ‘Ansactio, Step 4: As there is no cycle in the precedence sequence is conflict serializable. Hence we can cony, schedule to serial schedule. For that purpose we steps to find the serializable order. Saph, 4, M this nop “en . Sey Will follow ‘ Se Step 5: A serializability order of the transactions can finding a linear order consistent with the partial precedence graph. This process is called topological sort be Sbtaineg ‘ Order of ing, Step 6: Find the vertex which has no incoming edge wh; we delete T1 node then T3 is a node that has no incomin; delete T3, then T2 is a node that has no incoming edge, Thus the nodes can be deleted in a order Tl, T3 and T2. Hence the order will be T1-T3-T2 the ich is Ty, Ir ig edge, Ive Q.7 Explain the concept of conflict serializability. Decide whether following schedule is conflict serializable or not. Justify your answer. TL T2 read (A) write (A) | tead (A) write (A) | read (B) write (B) tead (B) write (B) BG [SPPU : May 18, End Sem, Marks 9]went Systems 4-9 Database Transacti erent Systems 8-9 Databa Management abase M Manag pate canst ? 4: We will read from top to bottom and build a precedence ph for conflicting entries. flicting entries are as follows - nM 12 read (A) write (A) N ME read (A) ) The m write (A) read (B) write (B) : — read(8) _/ write (8) step 2: Now.we will build precedence graph as follows - Step 3: There is no cycle in the precedence graph. That means this schedule is conflict serializable. Hence we can convert this.non serial schedule to serial schedule. For that purpose we will follow the following steps to find the serializable order. 1) Find the vertex which has no incoming edge which is T1. 2) Then find the vertex having no outgoing edge which is T2. In between them there is no other transaction. 3) Hence the order will be T1-T2 Q.8 What is view serializability ? Explain. Ans. : « Ifa given schedule is found to be view equivalent to some serial schedule, then it is called as a view serializable schedule. © View Equivalent Schedule : Consider two schedules $1 and S2 consisting of transactions T1 and T2 respectively, then schedules $1 and S2 are said to be view equivalent schedule if it satisfies following three conditions : Fe A Guide for Engineering SaulentsDatabase Management Systems 4-10 Database Transacti, Mang © If transaction TI reads a data item A from the datat men ‘al Oa in schedule $2, then in schedule $2 also, T1 must at ata initial read of the data item X from the database, This 2 the for all the data items. In other words - the initial reagg same for all data items. © If data item A has been updated at last by, Tansaction 7; . schedule $1, then in schedule $2 also, the data item A a i updated at last by transaction Ti. be © If transaction Ti reads a data item that has been transaction Tj in schedule $1, then in schedule 9 also transaction Ti must read the same data item that has te updated by transaction Tj. In other words the Write-Reaq sequence must be same, Q.9 Check whether following schedule is view serial Justify your answer. (Note : T1 and T2 are trans: explain the concept of view equivalent schedul equivalent schedule considering the example sched MUSt be Updated by the lizable or not, actions). Algo les and conflict lule given below T1 T2 read (A) A =A-50 write (A) read (A) temp: = A*0.1 A: = A-temp write (A) read (B) B:=B+50 write (B) read (B) B: = B + temp write (B) BG [SPPU : Dec. 18,19, End Sem, Marks 9) ‘A Guide for Engineering Sater| eabase Management Systems 4-11 Database Transaction Management pata as stop 1 . . we will first find if the given schedule is conflict serializable or ’ ot. For that purpose, we will find the conflicting operations. These are a « The precedence graph is as follows - Fig. 0.9.1 : Precedence graph © As there exists no cycle, the schedule is conflict serializable. The possible serializability order can be T1-T2 * Now we check it for view serializability. As we get the serializability order as T] - T2, we will find the view equivalence with the given schedule as serializable schedule. © Let S be the given schedule as given in the problem statement. Let the serializable schedule is S’={T1,12}. These two schedules are Tepresented as follows. A Guide for Engineering Studentsread (A) read (A) |. A=A-50 AL=A-50 L write (A) write (A) i; | read (A) tead (B) Fea | | temp: = A*0.1 B:=B+50 | A:=A-temp | write (a) write (B) | | read @) B:=B+350 : | write (B) read (B) tead (B) B:=B+temp B:=B+temp write (B) write (B) Schedule Schedule $? * Now we will check the equivalence between them using following conditions - . Initial Read In schedule initial read on A is in transactic tead on B is in transaction T1, Similarly in schedule Ss, Similarly initial read on B i Final Write ion TI. Similarly initial initial read on A is in transaction TI. is in transaction T1. x In schedule $ final write on A is in transaction T2. Similarly final write on Bis in transaction T2, In schedule §’ final write on A is in transaction T2. Similarly final write on Bis in transaction T2 A Guide for E1ementt nm Management Manas diate Read chedule $ for finding intermediate read operation ‘read (A) —~_| temp :=A‘0.1 i A:= A-temp write (A) Intermediate Read obtained only after Tt performs Write operation read (8) B:=B+temp « Similarly consider schedule §? for finding intermediate read operation. 1 12 read (A) A= A=50 write (A) read (8) B:=B+50 write (8) 7 \ read (A) temp: =A°0.1 Intermediate Read operation ea obtained only after Tt | Ais A-temp __ performs Write operation write (A) bo Treat (8) ————] B:=B+temp pos wate (B) Seen TE TTT —_ "A Guide for Engineering Students” 4-14 Database Transaction Man, Database Management « In both the schedules S and S’, the intermediate reag a Frey erat performed by T2 only after TI performs write operation, ion i, © Thus all the above three conditions get satisfied, Hence schedule is view serializable. a, Ven 4.6 Cascaded Aborts, Recoverable and Nonrecoverable, Schedules nee b_ Q.10 Write a short note on - Cascaded Aborts. Ans. : * Cascaded Abort is a situation in which the abort of one Transaction forces the abort of another transaction to prevent the secong transaction from reading invalid. It is also called as cascading Rollback or Cascading Schedule. © For example - consider the following schedule Tl T2 T3 Read(A) Write(A) Read(A) Write(A) Read(A) Write(A) Failure * In above schedule, transaction T2 depends upon TI, transaction T3 depends upon T2.Now failure of transaction TI, causes the transaction T1 to rollback, the rollback of transaction T2 causes T3 to rollback. Such rollbacks is called cascading rollback or cascading abort. A Guide for Engincering Students oevement Systems __4- 15 Database T atase Mame Miche Transaction Manageret terms - Revoverabj, —= petine the © and non recoverable schedule, ecoverable schedule ; A recoverahj : ans? h pai of transactions T; and T one where, le schedule is j Such that T, feads a data item for Cr ritten by T;, the commit o vio tion of 1 Peration fT, appears before recount opera 7 N nracoverebl® schedule : If in a schedule, when a transaction oa irty read operation fr : peforms a dirty Pp om an ‘uncommitted transaction and mits before the transaction from which it has read the value then a cha schedule is known as an irrecoverable schedule, gl ————— [47 comune cont | i ai2 What is concurrency control ? Ans. ¢ : + A mechanism which ensures that simultaneous execution of more than one transactions does not lead to any database inconsistencies js called concurrency control mechanism, « The concurrency control can be achieved with the help of various protocols such as - Lock based protocol, deadlock handling, multiple granularity, timestamp based protocol and validation based protocols. | 4.8 Lock-based Protocol — Q.13 What is lock based protocol ? What are the types of locks ? Ans. : * Concept of protocol : The lock based protocol is a mechanism in which there is exclusive use of locks on the data item for current transaction. © Types of locks : There are two types of locks used - i) Shared lock : The shared lock is used for reading data items only. It is denoted by Lock-S. This is also called as read lock. ii) Exclusive lock ; The exclusive lock is used for both read and write operations. It is denoted as Lock-X. This is also called as write lock. ‘A Guide for Engineering StudentsDatabase Management Systems Ans. : - 4-16 Database Transaction Manag, men 14 Explain two phase locking protocol. ~ © The two phase locking is a protocol in which there are two Phase, i) Growing phase (Locking phase) : It is a phase in whi transaction may obtain locks but does not release any lock, ii) Shrinking phase (Unlocking phase) : It is a phase in the transaction may release the locks but does not obtain new lock. ch the hich any * Lock Point : The last lock position or first unlock position is called lock point. ¢ For example - Lock(A) ' Lock(B) ' cectpte | Lect) ie | 1 acguired released 1 (Growing (Shviging Lock } phate) Phase) ~ Point | {transaction sa 1 begins Unlock(A) : 1 Unlock(B) t Unlock(C) © Consider following transactions Ce Ty | Lock-X(A) Lock-S(B) Read(A) Read(B) A=A-50 Unlock-S(B) Write(A) Lock-X(B) .-Unlock-X(A) B=B+100 Lock-S(A) Write(B) Read(A) Unlock-X(B) Unlock-S(A) A Guide for Engineering SuulentsJems : _ananagentent Sut Systems __4- 17 Database Transaction Managernent i ee rule for being a two phase locking is - All lock ! , The a ons precede all the unlock operations. ie transactions T, is in two phase locking mode but m etion T, is not in two phase locking. Because in T,, the tran a axed Jock is acquired by data item B, then data item B is read and ve 10k is released. Again the lock is acquired by data item A, ther the data item A is read and the lock is then released. Thus we the wee unlock-lock-unlock sequence. Clearly this is not possible intvo phase locking. ‘eh are advantages and disadvantages of two phase jocking ? ans. Advantages of two phase locking 1) Itensures serializability. pisadvantages of two phase locking protocol (it Jeads to dealocks. ait Jeads to cascading rollback. 9.16 What are types of two phase locking ? Ans. ¢ 1) Strict two phase locking : The strict 2PL protocol is a basic two "phase protocol but all the exclusive mode locks be held until the transaction commits. That means in other words all the exclusive locks are unlocked only after the transaction is committed. That also means that if T, has exclusive lock, then T, will release the exclusive lock only after commit operation, then only other transaction is allowed to read or write. For example - Consider two transactions. 1 T, R(A) A Guitle for Engineering StudentsDatabase Management System: 4 ystems +18 Database Trans, ‘action Ma, nave If we apply the locks then Lock-X(A) | WA) Commit Unlock(A) Lock-S(A) R(A) Unlock-S(A) ¢ Thus only after commit operation in T,, we can unlock th e exclusive lock. This ensures the strict serializability. Thus compared to basic two phase locking protocol, the advantage of strict 2PL protocol is it ensures strict serializability. 2) Rigorous two phase locking : This is stricter two phase locking protocol. Here all locks are to be held until the transaction commits. The transactions can be seriealized in the order in which they commit. : ¢ Example - Consider transactions Ty | R(A) RB) WB) © Ifwe apply the locks then | T | Lock-S(A) R(A) Lock-X(B) RB) aetems 4 man nent S98 19 Database Transaction Management 38 putt ‘ommit Unlock(A) Unlock(B) the above transaction uses rigorous two phase locking Thus ; neobaniso™ f | .9 Time-stamp bi rotor | (ee eee —_nee pose a transaction, issues a read command on data item git SupP™. - stamp based protocol decides whether to allow the e a ou be executed or not using time-stamp based opecol Of concurrency control. rot B&D [SPPU : Dec.-17, May-19, End Sem, Marks 9] ans. * eae 4 (Read) ¢ Transaction T issues a read(X) operation case (T) < WTS(X), then read(X) is rejected. T has to abort and be ) HTS rejected. iif wIs(x) $< TS(T), then execute read(X) of T and update RTS(X). case 2 (Write) : Transaction T issues a write(X) operation i) IfTS(T)< RTS(X) or if TS(T) < WTS(X), then write is rejected ii) IRTS(X) $ TS(T) or WTS(X) < TS(T), then execute write(X) of Tand update WTS(X). Example for Case 1 (Read operation) (i) Suppose we have two transactions T, and T, with timestamps 10 sec. and 20 sec. respectively. | 10Sec | 20Sec Jette Ty att tats RK) | |__ woo | RX) | | ‘A Guide for Engineering StudentsDatabase Management Systems 4-20 Database Transaction M —— reese an yy ii) Suppose we have two transactions T, and T, with timestamps 20 wd ‘A Guide for Engineering Students RTS(X) and WTS(X) is initially = 0 “SH Then RTS(X) = 10, when transaction T, executes After that WTS(X) = 20 when transaction T, executes Now if read operation R(X) occurs on transaction, i TS(T,) = 10 then at TS(T, ) ie. 10 WTS(X) which is 10, hence we accept read operation on T,. The transaction T, will perform read operation and now RTS will be updated as, RTS(X) =18 : agemeltt Systems __ 4 21 Database Transaction Management a 2 (Write Operation) for Y i ewe have two transactions T, and T, with timestamps ) Su and 20 sec. respectively. ec Fececcenenaneaare ta 10 See. 20 See. B 3 eee eee wx) WX) ) and WTS(X) is initially = 0 ws C8) = 10, when transaction T, executes ve that WTS(X) = 20 when transaction T, executes Now if write operation W(X) occurs on transaction T, at qs(T,) = 10 then TS(T,) be. 10 WTS(X) which is 10, hence we accept Write operation on T,. The transaction T, will perform write Peration and now WTS will be updated as, WTS(X) = 20 | 4.10 Deadlock Handling | Q.18 What is deadlock ? Explain the four conditions for deadlock to occure. Ans. : © Definition : Deadlock can be formally defined as - “ A system is in deadlock state if there exists a set of transactions such that every transaction in the set is waiting for another transaction in the set,“ ¢ There are four conditions for a deadlock to occur © A deadlock may occur if all the following conditions holds true. 1. Mutual exclusion condition : There must be at least one resource that cannot be used by more than one process at a time. 2. Hold and wait condition : A process that is holding a resource can request for additional resources that are being held by other processes in the system. 3. No preemption condition : A resource cannot be forcibly taken from a process. Only the process can release a resource that is being held by it. A Guide for Engineering Studen’s Seedns ase ME yt tbe ular wait condition ; i 4-23 Database Transaction Management A conditi iting for a resource that is being bly es is o 4 process is waiting for third Process ....s0 on ie and oo 7 aie for the first process. Thus making a sec hail of waiting. fi explain walt for graph algorithm in detail Ans: | method, graph is created based on the transaction and their ’ a ifthe created graph has a cycle or closed loop, then there a deadlock. i it for the graph is maintained by the system for every rransactiOn which 7 waiting for can data held by the others. The system keeps checking the graph if there is any cycle in the graph. , This graph consists of a pair G = (V, E), where V is a set of vertices and E is a set of edges. + The set of ‘vertices consists of all the transactions in the system. . When transaction T, requests a data item currently being held by transaction T; , then the edge T; T; is inserted in the wait-for graph. This edge is removed only when transaction T; is no longer holding a data item needed by transaction T,. , The ™ « For example - Consider following transactions, We will draw a wait for graph for this scenario and check for deadlock. TG RA) | RA) wa) | RB) | mn) we) "A Guide for Engineering Studentsatabase Trmsaction Managey, Meng * We will use three rules for designing the wait-for graph - Rule 1: If T, has Read operation and then T, has Write Petation then draw an edge T,-> T,. Rule 2: If T, has Write operation and then T, has Read Peratign then draw an edge T, > T). Rule 3: If T, has Write operation and then T, has Write o, Peration then draw an edge T,>T;. © Let us draw wait-for graph Step 1: Draw vertices for all the transactions © Fig. Q.19.1 Step 2: We find the Read-Write pair from two different transactions reading from top to bottom. If such as pair is found then we will add the edges between corresponding directions. For instance - y Tt R(A) RA) Re) WA) we) Fig. 0.19.2 Step 3: | Fig. Q.19.3 ‘A Guide for Engineering Studen’s | ec eeecement Systems a ' senna 5 Database Transaction Management oe jetected in the wai oem a Je is © Wait-for graph there is No need to s ¢ : , further process. The deadlock is present in this transaction gcensrios ae | 4.11 Recovery Methods 20 What is the purpose of database recovery ? Ans: * A : , The purpose of recovery is to bring the database into the last consistent stage prior to occurrence of failure. | The recovery must preserve all the ACID properties of transaction. The ‘ACID properties are - Atomicity, Consistency, isolation and durability. . Thus recovery ensures high availability of the database for transaction purpose. + For example - If the system crashes before the amount transfer from one account to another then either one or both the accounts may have incorrect values. Here the database must be recovered before the modification takes place. Q.21 Explain the shadow paging technique of database recovery. ADS. ¢ « Shadow paging is a recovery scheme in which database is considered to be made up of number of fixed size disk pages. A directory or a page table is constructed with n number of pages where each i ‘page points to the i: database page on the disk. (Refer Fig. Q.21.1) The directory can be kept in the main memory. When a transaction begins executing, the current directory-whose entries point to the most recent or current database pages on disk-is copied into a another directory called shadow directory. The shadow directory is then saved on disk while the current directory is used by the transaction. eT "A Guide for Engineering StudentsDatabase Management Systems Current directory 1 2 Sho ea : 5 6 - ’ * Updates After updating Pages 3.and6 Fig. Q.21.1 : Demonstration of shadow Paging ¢ During the execution of transaction, the shadow directory is never modified. * When a write operation is to be performed then the new copy of modified database page is created but the old copy of database Page is never overwritten. This newly created database page is written somewhere else. The current directory will point to newly modified web page and the shadow page directory will point to the old web page entries of database disk. When the failure occurs then the modified database pages and current directory is discarded. The state of database before the failure occurs is now available through the shadow directory and this state can be recovered using shadow directory pages. This technique does not require any UNDO/REDO operation. Geos A Guide for Engineering Students aeagement systems 4-27 Database Transaction Management st oe pate — | pe | 4.12. Checkpoints checkpoint ? what | 22" ane kp is a mechanism where all the previous logs are a aoe from the system and stored permanently in a storage disk. (el : ‘i point declares a point before which the DBMS was in check z onsistent state and all the transactions were committed. c The recovery system reads the logs backwards from the end to the jast checkpoint. rming a checkpoint consists of the following operations : perfol suspending executions of transactions temporarily; Writing (force-writing) all modified database buffers of committed transactions out to disk; ° ° Writing a checkpoint record to the log; and ° Writing (force-writing) all log records in main memory out to disk. ° E 4.13 Log-based Recovery Q.23 Explain deferred.database modification. Ans. + « In this technique, the database is not updated immediately. Only log file is updated on each transaction. « When the transaction reaches to its commit point, then only the database is physically updated from the log file. ¢ In this technique, if a transaction fails before reaching to its commit point, it will not have changed database anyway. Hence there is no need for the UNDO operation. The REDO operation is required to record the operations from log file to physical database. Hence deferred database modification technique is also called as NO UNDO/REDO algorithm. ‘A Guide for Engineering Studentsy Database Management Systems e. For example : 4-28 Database Transaction Mange Consider two transactions T, and T, as follows : T T, Read (A, a) | Read (C, c) a=a-10 c=c-20 Write (A, a) | Write (C, ¢) Read (B, b) b=b+10 Write (B, b) If T, and T, are executed seri ally with initial values of A = 199 B = 200 and C = 300, then the state of log and database if crash occurs a) Just after write (B, b) b) Just after write (C, c) c) Just after © The result of above 3 scenarios is as follows : ¢ Initially the log and database will be Log Database A=90 B=210 C= 280 Becoom A Guide for Engineering Students eeent Systems 4-29 Dap, ps ~Mhate Transaction Management ju A ion, : 1) cr write OPETREION, NO Commit recon Pears in log. Heng ' i a Just i operation is performed on database So databag wr a 0 old values: Hence A = 100 and B = 200 respectively, retains onl hus Tl ation take place. oI lete transaction of T ee redo The incomP 1 64N be deleted from log. : ot after write (C, ¢) ‘ . state of log records is as follows . Note that crash occurs before T, commits, At this point T, is . completed successfully, so new values of AandB ae ‘writen from Jog to database. But as T, - Not committed, there is no redo qT) and the incomplete transaction T, can be deleted from log. « The redo (T,) is done as gets executed. Therefore A= 90, B= 210 and C = 300 are the values for database. ¢) Just after « The log records are as follows : Crash occurs here Clearly both T, and T, reached at commit point and then crash occurs. So both redo (T,) and redo (T,) are done and updated values will be A = 90, B = 210, C = 280. A Guide for Engineering StudentsL Database Management Systems 4-30 Database Transaction Mon Q.24 Explain immediate database modification. “hy Ans, : © Ifthe transaction gets failed before it reaches to its commit then the a ROLLBACK Operation needs to be done 10 brin, Dein database to its earlier consistent state. That means the ¢ effeg operations need to be undone on the database. For tha Pu both Redo and Undo operations are both required during recovery. This technique is known as UNDO/ REDO technique For example + Consider two transaction T, and, 8s follows an L T, | T, | Read(A.a) | Read(C, ¢) | a=a-10 =e-20 | | Wrte(A, 3) | Write(C, | Read(B, b) i b=b+l0 | Write(B, b) | Here T, and T, are executed serially. Initially A = 100, B = 299 and C = 300 If the crash occurs after i) Just after Write(B, b) ii) Just after Write(C, c) iii) Just after Then using the immediate Database modification approach the result of above three scenarios can be elaborated as follows : eran ‘A Guide for Engineering Sudents eetystems ang pment S on ents of tog and da ne e Log | 2, Start> yhr100,90 18,200,210 | The recovery scheme uses two recovery techniques - ) UNDO (T)): The transaction T; needs to be undone if the log contains but does not contain . In this phase, it restores the values of all data items updated by T; to the old values. ii) REDO (T,) ¢ The transaction T; needs to be redone if the log contains both and . In this phase, the data item values are set to the new values as per the transaction. After a failure has occurred log record is consulted to determine which transaction need to be redone. a) Just after Write (B, b) : When system comes back from this crash, it sees that there is but no . Hence T, must be undone. That means old values of A and B are restored. Thus old values of A and B are taken from log and both the transaction T, and T, are Te-executed, b) Just after Write (C, c) : Here both the redo and undo operations will occur. ‘A Guide for Engineering StudentsDatabase Management Systems 4-32 Database °) 4) e) Q.25 To ensure atomicity despite failures we uses methods. Explain in detail log-based recovery method. ‘Ans. : Refer Q.23 and Q.24, — Tre ACO Menon, Undo : When system comes back from his that there is but no , Hence es must be undone. That means old values of ¢ j inte 1, A St Thus old value of C is taken from log and the Res ‘ored, sac is re-executed. ea Redo : The transaction T, must be done as lo, both the and So A=90, B = 210 and C = 300 Just after : When the system from this crash, it sees that there are two transac T, with both start and commit points. That mean: B Contains OMes back tion T, ang ST, and T. need to be redone. So A= 90, B= 210 andc = 280. Tecovery SP [SPPU : May-18,19 End Sem, Marks a) END... a ‘A Guide for Engineering StudensUnit v NoSOQL Databases 5.1 Introduction to Distributed Database System al explain the concept of distributed database systems. 8 A gistributed database system consists of loosely coupled sites * (computer) that share no physical components and each site is associated a database system. » The software that maintains and manages the working of distributed databases is called distributed database management system. i + The database system that runs on each site is independent of each other. Refer Fig. Q.1.1 Fig, Q.1.1 : Distributed database systems . * The transactions can access data at one or more sites. 6-DON Database Management Systems 5-2 Nos et Dat 2 What are the advantages and dleadvantages of qi database system ? but Ans. : Advantages of Distributed Database System 1) There is fast data processing as several sites participate in te processing. ‘West 2) Reliability and availability of this system is high, 3) It possess reduced operating cost. 4) It is easier to expand the system by adding more sites, 5) It has improved sharing ability and local autonomy. Disadvantages of Distributed Database System 1) The system becomes complex to manage and control. 2) The security issues must be carefully managed. 3) The system require deadlock handling during the transaction processing otherwise the entire system may be in inconsisten, state. 4) There is need of some standardization for processing of distributed database system. | 5.2 CAP Theorem | Q.3 Write short note on - CAP Theorem. Ans. : © Cap theorem is also called as brewer’s theorem. © The CAP Theorem is comprised of three components (hence its name) as they relate to distributed data stores : © Consistency : All reads receive the most recent write or an error. © Availability : All reads contain data, but it might not be the most recent. © Partition tolerance : The system continues to operate despite network failures (i.e.; dropped partitions, slow network connections or unavailable network connections between nodes.) Becoo® "A Guide for Engineering Studentsment Systems $3 angen an! nee M ———___Nos pate patra theorem states that it ig Not possi fe “SCL Databares » mee de sible properties - consisten ey, avail — Nee all three ‘th ee at the same time in g distributed NY and partition rer tion. System with data repli¢ a 5.3 Types of bata | compare structured seml-structured ang Unstructured Data, a4 . 8 tured data | Semi-s Aa Struct aan Unsrcre ee | Nou itis having fixed Pisco pee I. and organized of structured and Predefined form of data, | unstructured data.| organized om Of data. 2. | It is schema Itis more flexible Ttis the most | "| dependent and less | than structured flexible data. flexible. data but less . flexible than unstructured data, | 4 3. Structured query The tags and Only textual languages are used | elements are used queries are to access the data | to access the data, Possible. present in the | schema. | 4, | Storage Storage Storage requirement for requirements for | requirements for | data is less. the data is the data is huge. | significant. | 5. | Examples : Phone Examples : Server | Examples : numbers, logs, Tweets _ | Emails and | Customer organized by messages, Image | Names,Social hashtags, emails _| files, Open ended | Security numbers. | sorted by the survey answers. | inbox, sent or l draft folders. es A Guide for Engineering Students eee