Tlachileer - ‘suBsect cove. 210241 (Chole Goued Crea Sem ‘SAVITRIBAI PHULE PUNE UNIVERSITY - 2019 SYLLABUS TE, (Computer/ AlBDS) Semeter-V DATABASE MANAGEMENT SYSTEMS (For END SEM Exam - 70 Marks) Mrs. Anuradha A. Puntambekar ME (Compute) Formerly Asstont Professor in PES. Modern Collegeof Engineering, Pore -——Features }——— © Written by Popular Authors of Text Books of Technical Publications Z Covers Entre Syiibus Question ~ Answer Format Exact Answers and Solutlons Solved Model Queston Papeis (As Per 2019 Pactern) ‘SOLVED SPPU QUESTION PAPERS ) + Aug.-2017 + Dec.-2017 *May-2018 + Oct. - 2018 sDec.-2018 +May-2019 + Oct.- 2019 + Dec. - 2019MongoDB (with syntax and usage) : CRUD Operations, Indexing. Aggregation, MapReduce, Replication, Sharding. (Chapter - 5) Unit VI Advances in Databases Emerging Databases : Active and Deductive Databases, Main Memory Databases, ‘Semantic Databases, Complex Data Types Semi-Structured Data, Features of Semi-Structured Data Models Nested Data Types : JSON, XML. Object Orientation : Object-Relational Database System, Table Inheritance, Object- Relational Mapping. Spatial Data : Geographic Data, Geometric Data. (Chapter - 6) TABLE OF CONTENTS Uni pig ze Chapter-3 Relational Database Design (3-1) to @ 733) 3.1 Basic Concepts 3-1 3.2. Attributes and Domains. 3-1 3.3. CODD's Rules. woB-2 2.4 Relational Integrity vn 3.5 Enterprise Constraints... 3.6 Features of Good Relational Designs.. 3.7 Normalization. 3.8 Atomic Domains and First Normal Form. 3.9 Decomposition using Functional Dependencies 3.10 Algorithms for Decomposition... 3.11 Two Normal Form... 3.12. Third Normal Form... 3.13 BCNF. = ction Management Chapter-4 Database Transaction (4-1) to (4-32) 4.1 _ Introduction to Database Transaction. 4.2. Transaction Si4.3. ACID Properti 44 45 Concept of Schedule. Serializability : Conflict and View... 4.6 Cascaded Aborts, Recoverable and Non, Schedules... recoverable, 4.7 Concurrency Control... 4.8 — Lock-based Protocol, 4.3 Time-stamp based Protocol 4.10 Deadlock Handling. 4.11 Recovery Methods. 4.12 Checkpoints. 4.13 Log-based Recovery. Chapter NoSQL Databases 6-16-15 5.1 _ Introduction to Distributed Database System 5.2 CAP Theorem 5.3 Types of Data 5.4 NoSQL Database .. 5.5 Types of NoSQL Databases 5.6 BASE Properties 5.7 ACID Vs BASE. 5.8 Comparative Study of RDBMS and NoSQL.. 5.9 MongoDB.. Chapter-6 Advances in Databases 6-1) to6-7) 61 62 6.3 Nested Data Types.. 6.4 Object Orientation. 6.5 Spatial Data... ‘Solved Model Question Papersee Database Design —— 3.1 Basic Concepts Q.1 What is relational database ? Ans. : * Relation database i a collection of tables having unique names * For example - Consider the example of Student table in which information about the student is stored. RollNo __Name __ Phone 001 AAA HUW 002 BBB 2222222229 003 ccc 3333333333 Fig. Q.1.1 : Student table 3.2 Attributes and Domains 22 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 RollNo,Name,Marks and Phone. —_—————___— Database Mo men Systems 3-2 elation Datataee Design Domain : For each attibute of relation, there is a set of penned values called domain, For example - in above table, the domain of attribute Marks is set ofall possible permitted marks ofthe students Similarly the domain of Name attibute is all possible names of students That means Domain of Marks attribute is (88,83,98) —— 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. ES [SPPU : 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 briel above rule. Also state its significance. {EB [SPPU Oct-19, In Sem, Marks 5] Ans. Rute 0 : This rule states for a database to be relational, it must use its relational capabilities to manage the database, Rule 1: The Information rule - All information in an RDBMS is represented logically only by storing the values in tables.” Rule 2: The Guaranteed Access rule - Each item of data in an 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) fo missing information or inapplicable information in presenting,ment Systems Relational Database, Database Mant Rule 4: The Dynamic Online Model rule ~ Database dictionary which : soca description of the complete Database and it must be gy online, This Catalog must be governed by same rules as rest of database. The same query language should be used on catalog ag wma to query database. log, Based on the tlonay called as catalog Rule §: The Comprehensive Data Sublanguage rule - At leat ogg well structured, well-defined language must be there which can ese all the data present in the database. ule 6 : The View Updating rule - All views of the data which age 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 a 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 net 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 is scattered geographically, user should get a feel as if it is stored in one piece at one location. =— ‘A Guide for Engineering Stdens Database Management Systems 3-4 Relational Database Design Rule 12: The Non-sub-version rule - If low-level language is allowed to access the system, then that low-level language must not be able to subvert or bypass the integrity rules which are expressed in a higher- level language. 3.4 Relational integrity G4 Explain the concept of candidate key and super key. ‘Ans. + 1) Super Koy(SK) : «Tris a 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 rior | 001 | iittiiiiii | AAA | 88 Rio2 | 002 | 2222222222] BBB | 383 R103 | 003 | 3333333333] ccc | 98 Rio | 004 | 44aaaaaaaa | DDD | 67 Fig. 0.4.1; Student ‘© The superkey can be represented as follows wae [me [ew [Ye [et R101 oor aint [Pw et a one em | 1 ees st ios 03 meee | | eco = wo [Tom aver Poe Jo * Clearly using the (RegNo) and (RollNo,Phone.Name) we can identify the records uniquely but (Name, Marks) of two students can be same, hence this combination not necessarily help in identifying the record uniquely. Gecooss 1 Guide for Engineering Students iit aoe Relations! Database Dp zo tase Mange Sertens_3-5__REREGRAL Dette Dey 2) Candidate Key(CK) : The candidate Key is subset of superset, In other Words canggy key is a single attribute or least oF minimal combination avribures that uniguely identify ench record in the table, Fy, example ~ in above given Student table, the candidate key i, -RegNo, (RolINo.Phone). The candidate key can be canssete Database Management Syste 3 Relational Database Design For example - S Candsate key een eno Ph Name ia Rie oor sant oy = Rica 002 pea Bee @ Re 003 3999988883 occ, 7 rae 008 eaaeenaes ‘p00 7 ‘+ Thus every candidate key is a superkey but every superkey is not a candidate 5 Explain the concepts of referential integrity constraint and entity integrity constraint with example. ES [SPPU : May-18, Dec.-19, End Sem, Marks 5] Ans. 1) Entity integrity Constraint + This rule states that “In the relations, the value of attribute of primary key ean not be null”, * The NULL represents @ 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 must know the value of the key for that row. Hence it is necessary that the primary Key should not have the NULL valu RollNo | Name Marks | Phone 01 AAA 23 qanttitt oot BEB 3 | zzazzzz222 003 ‘cco Ee DoD o7 | aaaaaaaaaa NULL is not ‘allowed Il I) Referential Integrity Constraint ‘In relationships, data is linked between two or more tables. This is achieved by having the foreign key (in the associated table) reference a primary key value (in the primary - or parent - table). Because of this, we need to ensure that data on both sides of the relationship remain intact. «The referential integrity rule states that “whenever a foreign key value is used it must reference a valid, existing primary key in the parent table”. + For example - Cor reo37 atabase Management Systems on, the registration no. RSSS is not existing sip » it « Inabove relat is present in the b referential integrity constraint. Database Management Systems 3:8 Relational Database Design the course able then we sey that 1S ot flow EmplD | EName | Salary | DeptID | DeptName | DeptLoc 1 AAA 10000 101 XYZ Pune 35. Enterprise Constraints | Ca | sooo (Eso Sates 26 Write short note - Enterprise Constraints 3 CcC_| 30000 | 101 XYZ Pune 4 DDD 40000 102 PQR: Mumbai nee constraints are also called as semantic constraints, «+ The enterprise constraints are basically the additional mgs specified by users or database administrators. These constraint ae 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. 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 ji) To allow us to retrieve information easily. 28 Explain what is meant by repetition of information and inability (0 represent information. Explain why each of these properties may indicate a bad relational database design. sis EB [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, Now if we want to insert a record ,EEE,S0000 for the DeptID 101, then again there will be repletion of information about DeptID, DeptName and DeptLoc ie. (101,X¥Z,Pune). That means if we want to perform some operation (insertion, updation, deletion) on the relational schema then it should not cause repetition of information. The above scenario indicates bad database design. Normali Q9 What is normalization ? What Is the need of normalized database ? [SPU : Dec.-17, End Sem, Marks 5] Ans. ‘* Normalization is the process of reorganizing data in a database so that it meets two basie requirements : 1) There is no redundancy of data (all data is stored in only one place) and 2) Data dependencies are logical (all related data items are stored together) Nood for normalization 1) It eliminates redundant data. 2) Itreduces chanees of data error. take up less disk space. 4y Italso help 5) Itimprovesclational Datatas, ramagement SUSEMS me Database Deg Data act of 20 What fe the I 920s af database ? these anomalies ? Insert, update and delete anomaly How normalization 16 used to rem" a [SPPU: May8, End Sem, Hak Ans. / Redundancy is at the root of several problems associated wy, relational schemas, «Problems caused by redundancy. : Following problems can jy caused by redundancy Redundant storag Update anomalies : If one copy of such repeated data ig updated then inconsistency is created unless all other copies arg similarly updated. iii) Insertion anomalies : Due to insertion of new record repeated information get added to the relation schema. Some information is stored repeatedly ix) 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 Deptid | BaniName] _Deptboe + AMA Tor | xyz | Pune 2 238 wor | _xvz_| Pane 3 | ccc’ aor [vz Pane 2 ‘00 102 [POR] | Mom Redundancyill 1) Redundant storage : Note thatthe information about DeptID, DeptName and DeptL.oe is repeated. 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,S0000) 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 EmplD 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 Q.9 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 - 4) It should only have single (atomic) valued attributes/columns. ii) Values stored in a column should be of the same domain. iii) All the columns in a table should have unique names. iv) And the order in which data is stored, does not matter. So ___ Gil for Enginccring Stentstelational Datat Re base Desi Database Mans Consider followint a SS [psssteueee A 1 | | reed BBB 2 | FF r,s cc 5 c ‘alues of phone number for sid 1 and 3, the tiple 4G + As there are mull NF. We can make it in INF. The conversion above table is not in U ises lee — Phone sid wut 1 22229 ; 33333 5 44444 3 55555 3,9 Decomposition using Functional Dependencies Q.42 Explain in brief with suitable example full functional dependency and partial dependency. {EB [SPU : Oct-49, In Sem, Marks 3] Ans. © Definition : A functional dependency A->B in a relation holds if ‘wo tuples having same value of attribute A also have the same Value for attribute B. It is denoted by A->B where A is called determinant and B is called dependent, = ‘A Guide for Engineering Stier Database Management Systems 3-12 Relational Database Design For example - Consider Student table as follows - Roll Name City, 1 AAA Mumbai 2 BBB Puine 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.43 State inference rules of Armstrong's axioms. Ans. The closure set is a set of all functional dependencies implied by a siven set F. It is denoted by F* ‘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, thn X > Y ii) Augmentation : If X — Y, then XZ» YZ forany Z ii) Transitivity : IfX — Y and Y — Z, then X > Z 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 Stentss13___Relation! Datoase Dey stems sew of the following set F of functiong, the clos (ABCD) A> nel Database Nam 2.14 Compute, eintional schema R= dependencles OSA : CDF EB OE genoted by F” and it can be Computed in vans. +The closure of Fi8 following steps | As A> BC is given we get ee By decomposition rule ASBandA>C As as (Refer step 1) A> (given) =D gs emt a) step3: A> CD because A> Cand A->D (From step 1 and Step 2 applying union rule) step: ; CDSE (given) ASE (transitive rule as A->CD, CD->E hence A>E) ‘step § Since A= A, wwe have (reflexive) A ABCDE from the above steps (union) Step Since E+ A, E+ ABCDE (transitive) Step7 Since CD + E, CD — ABCDE (transitive) Step: Since B— D and BC+ CD, BC + ABCDE (augmentative, transitive) Ss Gn for Engineering de® Databa Management Systems 3-18 Relational Database Design step 9 ‘Also, C+ C, D+ D, BD + D ‘Thus any functional dependency with A, E, BC or CD on the left hand side of the arrow is in F Q.15 Give Armstrong's axioms and using it find the closure of following FD set. ‘A->B, AB->C, D->AC, D->E Ans. ‘Step 1 : Consider the rules D > AC and D> E = D> ACE (Union rule) ‘Step 2: Consider AB > C then we get A>CandB>C (decomposition rule) Thus F =(A > C,B>C,D-> ACE} Q.16 Give R = {A,B,C,G\H,I}. The following set F of functional dependencies 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 Hto the set of AG + CG >I, hence add I to the set of AG’. Also add G to the set. Thus (AG) = {A,B,C,G.H,I} = 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 0(A)” ‘A> BC can be decomposed into A > Band A > C. AlsoB>D. Thus A > Dis also true by transitivity rule. Hence add D to (A)” eee ee eee Stepa Retational Database Design atone Management sevens _3-18 ASCASD ® Bywnion nile A> CP. AsCD->E add Et0(A) (A) = {ABCDE} 7 a Cconsider(BY = {B.D}2R henoe it is not a candidate key nes = (ABCD.E} = R. Hence step 3 : Consider (BC) = {B.C.D.EA} itis a candidate key step 4: Consider CD > E,E Hence itis a candidate key > BC,B>D,CD>E. A.B.C.D.E}. => A, hence (CD) = step §: Consider E> A, A Hence (E) = {A-B,C.D.E} is a candidate key. “Thus we get the candidate keys as (A.BC, CD, E} G18 Consider schema R = (A.B,C,G)H.D and the set F of funetional dependencies : {A-> B,A-> C, CG-> H, CG -> I, B-> H). Use (F) Prove (AG)" -> I Ans: sept: ASASB BoH ASH (Cransitivity rule) sep?! CG>H G21 coo (Union rule) Steps: ASC co>1 AG=1 (Pseudo transitive rule) ‘Thus AG -> Lis proved (FY ={A2B,A>C,CG>H,CG>1,B>H,A>H, CG>HILAG>1) SES ‘A Gude for Engineering Suen: atabase Management Systems 3-16 __petationat Database Des 2.19, Here, te (Wo sete of FDs for IAB.C.D.E). Are they cequivalen A> B 2) A->BC AB-> D> AE D-> Ac DE ‘Ans. TWo Sets of FDs are said to be equivalent if Rule 1 : If FD2 > FDI. That means all FDs of FDI can be derived from all the FDs of FD2, Rule 2 : If FDI > FD2. That means all FDs of FD2 can be derived from all the FDs of FDI. Rule 3: Ifboth rule 1 and rule 2 are true then FD1 = FD2. For given two sets step 1: We will first check ifall the FDs of FD1 are present in FD2 A> BC is in FD2, that also means A> Band A->Cby decomposition rule ‘A-> Bis present in FDI. Similarly AB>CisinFD1 | Henee 2 (A) {ABC} (Ay = ABO) (AB) = (A,B,C) ‘AsD-> AE then by decomposition rule, | DSADSE | D>ac ‘As A> B, then by transitivity ieD>A,D>Cby rleD>A, decomposition rule. ASBD>B The D->A,A>BandC 2D) ={AB,CD.E} D>A,D=>B,D>Cby transitivity rule D> Eis given £:(D)" = (A,B,C,D,E} ST eed ie—— eecteme _3217_ Relational Database Design atatose Management We will first check ifall the F i) 2 are present in FDI EDs of FI step? (ay = {ABC} AAC) = {B.C} [3 @y = (ABCDE} ‘Thus from Step 1 and Step 2, FD2 > FDI and FDI > FD2. Hence both the sets are equivalent Consider two sets of functi 02 oot > D.E-> AD. E> AH). Are they equivalent ? We will find the FDs of both F and G and then check for F jonal dependency. E-> H} and G = (A-> CD, Ans. and G > FD2 and G > F. step: ForF ‘Using G functional dependencies - aw {A.C.D} — As A> CDis inG (acy {A,C.D} — AsA-> Cl G (@) = {ACDEH) < AsE>AH, A> CD is inG Using F functional dependencies - (Ay = {ACD} © As A> Cand AC > Dis in F (AQ) = {ACD} © AC>DisinF (© = {A.CDE.H} -AsE> AD, E> Hand A> Cis inF step2: ForG Using F functional dependencies - (A) = {ACD} © AsA> Cand AC-> Dis inF (©) = {ACD.EH) CAsE > AD,E>HisinF Using G functional dependencies - (A) = {ACD} © AsA>CDisinG ©) = (ACDEH) -AsE> AHand A> CDisinG ‘Step 3: From both these steps G2F and F2G Hence F and G are equivalent Ps ‘A Gulde for Engineering Students Database Management Systems 3-48 2.21 Explain the concept of Minimal cover. ‘Ans. 1 Formal definition : A minimal cover for a set F of FDs is a set G of FDs such that 1) Every dependency in G is of the form X > A, where A is a single attribute. 2) The closure F” is equal to the closure G”. 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, then F 4H, Q.22 A relation R(A,C.D.E\H) satisfies the following FDs A -> C, AC -> 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 rule one by one ednsidering 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. Relational Database Design E-> AD, keep it as itis as E is a single attribute at LHS. E>H, keep ‘Step 2: Now we will minimize RHS. as A>C, keep itas is A>D, keep itas E> AD. That means E> A and E > D. ‘As A> Dis also present in the FD, so we get E> A and A > D. Thus E > D is transitive . Hence neglect it. So.we keep E> A only E->H, Keep itas itis.— ent systems __3219__ Relational Database Design Database Man .d 2, we get minimal cover of FD as ‘stop 3: From steps I an ASC ASD EDA ESH Hence the canonical for is AScD EAH 2.23 What Is functional depends the minimal cover algorithm for dependene freee! D.B-> C AE-> B, A-> D, D-> EF} Ans. ‘stop 1: We will make right hand sides atomic AB>D BSC AESB 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>Die{G-(AB>D)} We get (AB)+ = {ABCDEF}. That means we can remove AB > D as it is redundant entry. Hence grammar is BoC AESB ASD DoE DoF jency ? Find the minimal cover using the following functional Database Management Systems 320 Relational Database Desi «For B > C compute (B)+ by consid (r= (AEBDP- AC tp Th —— ‘So we can not remove it — B=c AESB ASD DE 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 Bec AEB A2D DSE D>F + For A-> D, we will compute(A)+ under (G - (A > D)) (A}t = {AEBC). As D is not present in (A)+, hence we can not eliminate A >D. The grammar is BSc AESB ASD D>E DoF © ForD>E, compute (D)+ under (G - (D> E)) (D)+ = {DF}. As E is not present in (D)+, We cannot remove D>E Se eee weDatabase Management Systems 3-21 Relational Database Desi « For D> F, compute (D)+ under (G-(D > F)) (D)+ = {DE}. As F is not present in (D)*. D +> F. Finally the grammar is BoC z AE>B ASD D>E D>F Stop 3 : Remove redundant entries based on RHS B->C,A>D,D->E and D > Fas LHS is atomic. We cannot remove Now we consider AE > B For A : compute E+ with respect to (G - (AEB) U (EB) E+ using (B-4C, E+B, AD, DE, DF) = EBC E+ doesn’t contain A, so A not redundant in AEB For E : compute At with respect to (G - (AEB) U (AB) ‘At using (BC, A>B, AD, DE, D+F} = ABDEFC | ‘A+ contains E, so E is redundant in AEB Hence we consider AE > Bas A> B. Finally minimal closure is {B > CA > B, A > D, D > E, D>F} 7 10. Algorithms 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 anributes of R and together include all attributes of R by storiiig, projections of the instance. ‘+ For example - Consider the following table tabase Management Systems Database Management Sy 3:22 Relational Database Design 4 Employee_Department table as follows - Eid_|Ename | Age| City Salary | Deptia g001| ABC | 29 | Pine | 20000 £002] POR | 30 | Pune | 30009 DeptName D002 | Production 003 | tan | 25 | Mumbai | s000 | boos Sales go0s| XYZ | 24 | sumbsi | 4000 | boos | Marketing £005] STU | 32 | Hyderabad | 25000 | Doos | 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 (Sif |e oor | apc | 29 | Pune | ~a000 coo | an | 30 | me] ~atoo0 ews | ums | as | amtat | smo zoos | xyz) 24 | samba] ano ews | _stu_| 3 | ydentad | as000 ia Za ae oor 01 ines pow E02 Frode o0s es sae ove 00s Maing oos e005 | Homan Rees ‘+ The decomposition is used for eliminating redundancy. ———————— a= Database Management syst Database Management Systems __3-23___ Relational Database Design step 2: Here RIM RD e 25 State and explain the properties associated with second condition gets sa decomposition. ‘Ans. : There are two properties associated with decomposition and step 3: AWRI) 1 Anceey ©. Here the those are - anibutes of RI. Thus the third cong A> NOW (A)* = fap 1) Loss-less join or non loss decomposition : When all information This hows that the given decompoyn ea (SBC) ie found in the original database is preserved after decomposition, we 0.28 What Is dependency presen, ‘ition is @ lossless join, call it as lossless or non loss decomposition. ‘Ans: ation ? «Definition 2) Dependency preservation : This is a property in which the constraints on the original table can be maintained by sit constraints on the original ined by simply Gord cenforeing some constraints on each of the smaller relations. + If decomposition isnot dependeny. 0.26 List the properties of decomposition. Explain lossless Join ! with example, : is lost in the decomposition Preserving, some dependency 5 [SPP May-18, End Sem, Marks 6) 0.29 Suppose we decompo 86 the scheme ‘Ans. : Proparties of Decomposition : Refer Q.25. ABO) and (ADE. Show tat thn dese ABCD Lossless join: The lossless join can be defined using following three A>BC.CD->E, Bop *® functional conditio: i) Union of attributes of RI and R2 must be equal to attribute of R. Each attribute of R must be either in R1 or in R2, Amt(R1) U Att(RQ) = AMR) and R2 (A, D,E). ii) Intersection of atributes of RI and R2 must not be NULL. ee Tet Ant(R1) A At(R2) #0 Ri Common attribute must be a key for at least one relation (Rl or R2) Step 2: The attribu s At(RI) 1. An(R2) > AM(RI) place oq, of and ce tnter ae aA BS Te cael or Am(R1) 1 An(R2) > Au(R2) entries of this row are filed with Bp and Bp. Stme as for R2 have 27 Consider the following relation R(A, B, C, D)and FDs A->BC, atuributes A, D, E, Therefore, we place cy, ty and Gg under these 1s the decomposition of R into R1(A, B, C), R2(A, D). Check If the decomposition Is lossless Join or not ively. The remaining entries of this row are filled with yp 1: Here At(R1) U Att(R2) = At(R) ie RI(A,B,C) U R2(A,D) alteitctioi{e C.D) ie R. Rt | a | o | a | Bo | Be fi ition get irst condition gets satisfied Rw | a | By | Be | % | "1 Guerin Sen “A Gulde for Engincering StadenesDatabase Management Systems ____3-25___ Balationl Dat Det Step 3: i) Considering A + BC we check if the the same value under the columns that FD. Rows RI and R2 has values ot, under colt We need to equate all the corresponding entries for these rows under columns B and C. ‘Since entry under column B is Gy (fOr Ge (for row R2). wo rows of the table have ‘make up the determinant of Siumn A. Therefore, row RI) and column C is, plel|ole RI | o& ae | Bw | Pe rR | o& | % | % | % | Me | he same value ii) Considering CD — E, we check for rows that have t in the columns C and D. Here, rows do not same values, the table remain unchanged and we repeat step 3 by another FD. iii) Considering B > D, we check for rows that have the same value in the columns B here rows have same values dq under the column B, Therefore, we need to equate all the corresponding entries for these rows under column D. Since entry under column Dis dg forrow RI. RI Ro "Now there are no more FDs to consider. Step 4 : Since row R2 has become Og, lg, Oey Cys Oy i.e. R2 has all values. Hence decomposition is lossless. 3.11 Two Normal Form [30 Explain why database normalization is jormalization is required for good tonal database design ? Explain with example requirements of “A Guile for Engineering Students we Management Systems 3 ag ara at Relational Database Design vans: Need of NrMalLaCN Refer og, ‘wo Normal Frm: 4 Fora table t0 bein the Second Normal Form, following condition must be followed 7 " 4) It should be in the Fist Normal form ii It should not have partial functional dependency For example : Consider following table in which every information bout a the Student is maintained ina table such as student isi, student name( name), cours idcid) and course name(ename). Student_Course Ld cid chame 1 AAA 101 c 2 | Bee 102 co 3. | ce 101 c 4 | ppp 103 Java © This table is not in 2NF. For converting above table to 2NF we rust follow the following steps - step 1: The above table is in INF. Step 2: Here sname and sid are associated similarly cfd and ename 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 {sideid} should be essentially a candidate key for above table. Hence to bring the above table to 2NF we must decompose it as follows : a “Gute for Engineering StenRetattonar vuravase Desi, atatase Management Systems _ 3777 atebase Management stems 5.23 tetianal Database Det Student Here candidate key ig « For example : Consider following table Student_details as [_sia_|_sname (sid, cid) follows - | AAA nu (sid, cama sid sname [zipcode | ayname aan 2_| BBB 102 1 AAA miu Pune | Maharashtra Selec eeir 2 BBB | 22222 | swat | Gujarat 4 DDD 103 3 eee 33333 Chennai | Tamilnadu a pep sada Jaipur Rajastan cate ‘cid _[ename| va Here candidate key is 5 EEE 55555 Mumbai_| Maharashtra voi fC cid Here ton | ow here cld- > cname © Super keys: {sid} {sid,sname}, {sid,sname,zipcode}, tor | © {sid.zipcode,cityname}... and so on, 103 _| Java # Candidate keys : (sid) © 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 sultable example. Ans. : ‘© A table is said to be in the third normal form when, ’) Iris in the second normal form(ie. it does not have partial functional dependency). ii) Ie doesn't have transitive dependency. Or in other words * In other words 3NF can be defined as : A table is in 3NF iftt is in 2NF and for each functional dependency Xoy atleast one of the following conditions hold : ') Xisa super key of able, ii) Visa prime attribute o A Gulde for Engineering Students « Non-prime attributes : (sname,zipcode,cityname,state} «The dependencies can be denoted as sid->sname id->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 sname Zipeode 1 AAA nu 2 BBB 22222 3 ccc 33333 4 DDD 4444s 5 EEE 35555Database Management Systems __ 3-29 _ Relational Datatve Desioy [zipcode __ | ry ui [ Pane Maharastra 20279 | Sin Gujarat | 33333 Chennai Tamilnadu | | 44444 Jaipur Rajasthan 55555 ‘Mumby ‘Maharashtra 2.22 Stents Deiat Std, Stone. Zp. C8) Consider above schema, check whether it is in SNF, If not justify and propose the schema in 3NF. 18, In Sem, Marks 8) O& [SPPU: Oct 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. Itis as follows - Student Stud_id Stud_name 9.33 Consider a table having structure student (Roll_no, Branch code, ark sbtaned, Eos, Note following points. 7 ee 1) Composite "primary Branch _code). 7 key for student table is (Roll_no, rollno and bute. 4 Guide for Engineering Sedona > cor sement Systems 3-30 pabsse ing above requirement stat whether the table er ted Is normal form or not ? Why ? If not in third normal for fe the database design for above requirements which ls In prop ee nal form. id n08 th EB [SPPU : Oct-19, In Sem, Marks 7] Clearly the above table is not there in third normal form as fansitive dependencies Ans: sere exists HF guribute depend upon the primary key roll_no and braneh_code and sssociated with exam_name attribute. <>) <>) To convert the above schema to third normal form we need to ent relations — This is because, exam_name total_marks Roll_no Branch_code decompose the schema into dif student_info Roll_no 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. EB (SPU :Dec.-18, End Sem, Marks 5) ‘Ans. : Need for Normalization : Refer Q.9. ANF: Refer 0.11. 2NF: Refer 2.30, NF: Refer @.31,tational Database Desi Database Management Systems _3-31_Rel | 3.13 BCNF 120 enlist thelr differences. Q.35 Explain 3NF and BCNF. Al eer, End Se, Marks 5 ‘Ans.: 3NF : Refer 31. BONF : + Fora table tobe in i) R must be in 3" Normal Form For each functional dependency ( X —* ¥ ), X should be a super key. In simple words if ¥ is a prime attribute then X can not be BCNF, following conditions must be satisfied : non prime attribute. ‘© For example - Consider following table that represents that q student enrollment for the course - Enroliment table sid Course Teacher 1 c Ankita 1 Java Poonam 2 c 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 using these two columns we can find, an be (sid, course), because “4 Gide for Engng Sader | Relational Database Design 'NB dependencies satabase Management Syst Dats stems gy «The above table holds folon 6 (id, course)->Teacher o Teacher->course + The above table is not teacher->course. Note that an because of the dependency words, teacher is a non py attribute and non-prime arn student sid Teacher 1 Ankita 1 Poonam 2 Ankita 3 Supriya . Archana course Teacher ray Ankita 7 Poonam Java Ankita c Supriya cH Archana c Now the table is in BCNFBCNF BCNF stands for Boyce Codd Normal Form, Normal Form, The table is in 3NF if itis in 2NF and for each funetional dependeney X->Y at least following condition hold: (i) X is a superkey, Gi) Y is prime attribute of table, The table is in BCNF if iejg in 3" normal form and for each relation X>Y X should be super key 3NF can be obtained without sacrificing all dependencies. Dependencies may not be preserved in BCNF. Lossless decomposition can be achieved in 3NF, Lossless decomposition hard to obtain in BCNF 3NF can be achieved without loosing any’ information from the old table, For obtaining BCNF we may loose some information from old table. END 1.26 A Guide for Engineering Statens D: ‘atabase Transaction £ i Management 4.4 Introduction to Database taneous, 4 Define the term - transaction, ; Ans. + Definition of Transaction ; A transaction can be group of tasks that form can be defined as 4 single logical unit. For exanp Suppose we want to withdraw ® 100 fio a flee tbe man account then we will 1) Check account balance 2) If sufficient balance is present request for withdeaal 3) Get the money 4) Calculate Balance = Balance - 100 5) Update account with new balance. * The above mentioned five steps denote one transaction, 4.2 Transaction States Q2 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. ES (SPPU: Dec. 17, End Sem, Maks 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. Hot saved to database.patabace Transaction Managem Database Management Systems _ 4.2 Datialas TEES Fig. 0.24 : Transaction states When a transaction executes its fina] 2) Partially committed : partially committed state operation, it is said to be in 3) Failed : A transaction is said to be in a failed state if any of the checks ade by the database recovery system fils. A failed transaction can no longer proceed further. 4) Aborted + Ifa transaction is filed to execute, then the database rear stem will make sure thatthe database isin is previous ent sate. If not, it Brings the database to consistent state by boring o rlling back the transaction. 5) Committed : If a transaction exceutes all its operations success it is said to be committed. This is the last step of @ transaction if it executes without al 4.3. ACID Properties Q3 State and explain In brief the ACID properties. During execution of transaction, a transaction passes through sev states, until it finally commits or Ins. Acld properties 1) Atomictty : . i property states that each transaction must be considered as a single unit and must be completed fully or not completed at all. “A Gilde for Engineering Students a janagement Systems g oennsaction in the database if half complete {Database should be in a state either before the transac om 12 transaction execution oF ansaction execution, It sh ; om. It should not be in a seate “executing”. TT. patavase Me 4 or example ~ In above mentioned wikdewal of mone transaction all the five steps must be completed fully o none of the step is completed. Suppose if transaction gets filed afer sep 3 then the customer will get the money but the balance will not be updated accordingly. The state of database should be either at before ATM withdrawal (ie customer without withdrawn money) or after ATM withdrawal (ie. customer with money and account pdated). 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 itis the only transaction in the system. «No transaction will affect the existence of any other transaction. + For example : If bank manager is checking the account balance of particular customer, then manager should sce 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 nt affect other transaction in this case. Hence it makes all the transactions consistent. ————— 7 Gate for Evsneting Sadeatabase Transaction Manage 1 Systems 4-4 Ds wey Database Managemen! 4 — ‘ease should be strone enough to handle any syste, + The database s a ay set of insert update. then 1 should be able t0 hang, «Ir there i ay 5 ee and commit to # If there is any the consistent state Fos example : In ATM withdrawal example, if the system failure sam customer geting the money then the s¥stem shoulg oe ag to update Database with - Rewibalaa: afer ey ecoer: Frat purpose the sstem as fo sep he log op sr epetion and is fate. So when the system recovery, saat die abe to know wena system has failed and if there san ponding wansaction, then it shouldbe updated to Database pase should be able to recover jx, ilure, the datal ‘Transaction st Q.4 Explain the concept of serial and Non-serlal schedule Ans.: ‘© Serial schedule : The schedule in which the transactions execute one after the other is called serial schedule. It is cor nature, For example : Consider following two transactions TI and 72. Cw D7] R(A) way RB) We) R(A) way R(B) Lt we | A Gul for Engineering Soler se Management Syste yatabase 3 7 = Ml 4:5 Database Tantction Mt ansaction T] execu ransaction T2 ‘A and B execute. The R stands fo for write operation. ‘All the operations of es and then i fon data items A and then B all the operations on data items F Fead operation and W stands Non serial schedule : The sched, » schedule in which ‘operations within the transaction are intermixed. This rm noo tay lead to conflicts in the result of inconsistency in the resultant data For example - Consider following two transactions, Lu jn | pea | | pw || RA) | we) [Ra | | we) | RB) [wes ¢ The above transaction is said to be non serial which result in inconsistency or conflicts in the data, 4.5. Serializability : Conflict 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. "Gide for Enainecrng Sens<6 Database Transaction Menagey, pasa’ : “Database Management Systems $8 ‘Testing for serializablllty i 2 ed for testing the seralizability : To te, gy, «Following method is Following metiey we can draw a graph G™ (VE) wag conflict serializability vertices which represent the number of transactions, # E = Edges for conflicting pais Create a node for each transaction. step 2: Find the conflicting pairs (RW, WR, WW) on the same variable (or data item) by different transactions. Step 3: Draw edge for the given schedule. Consider following cases T, executes write(Q) before T, exceutes read(Q), then draw edge step t 1 from T, to T, T, executes reed(Q) before T, executes write(Q), then draw edge from T, 10 T; T, executes write(Q) before T, executes write(Q), then diay edge from T; to, ‘Step 4: Now, if precedence graph is cyclic then it is a non conflic, serializable schedule and if the precedence graph is acyclic then it ig conflict serializable schedule. Q6 Check whether following schedule is conflict serializable or not. If it is not conflict serializable then find the serializability order. 1 12 13 ‘A Guide for Engineering Stalents, grap drawing one node from each tra there are three transactions, there wi ba * teen os eeion. In ebove pan en me > cent be to nodes sanaip To 3 @ © ® Fig.a.6.1 step 2: The conflicts are found as follows - ™ m 13 RA) — © \_ [r= @ \ ® rey) [Ye ] wa _\ OD way RIA) (WA) Step 3: The precedence graph will be as follows - Tae for Engineering Saderwe Database Management Systems 428 Database Transaction Monagey, Step 4 Sequence is conflict serializable. Hence we can convert this non ser, schedule to serial schedule. For that purpose we Will follow thes. Steps to find the serializable order. Step 5: A serializability order of the transactions can be obtained jy finding @ linear order consistent with the partial order of 4, precedence graph, This process is called topological sorting. Step 6 : Find the vertex which has no incoming edge which is Ty, jp We delete TI node then T3 is a node that has no incoming edge. If ye delete T3, then T2 is a node that has no incoming edge. le ° Thus the nodes can be deleted in a order TI, T3 and 12. Hence the order will be T1-13-T2 Q7 Explain the concept of conflict serializability. Decide whether following schedule is conflict serializable or not. Justify your 1 T2 read (A) verte (A) read (A) write (A) ead (B) uwrite (B) read (B) write (B) USF [SPU : May 18, End Sem, Marks 9] ‘A Guide for Engineering Students As there is mo eyele in the precedence graph the giy,, steP ih for conflicting entries, ” conflicting entries are as follows eceeereiiaien [reagiay———-—" | [write ay} —— |——___ The fread write (ay read (6) write (8) roadie) wey stop 2: Now we will build precedence graph as follows - stop 3: There is no eycle 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 TI. 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 TI and T2 respectively, then schedules SI and $2 are said to be view equivalent schedule if it satisfies following three conditions SS Tr Gade for Engineering StentsDatabase Tran Database Management Systems © If transaction TI reads a data item A from the database ini in schedule 82, then in schedule $2 also, TI must perform initial read of the data item X from the database. This is sa for all the data items. In other words - the intial reads must ye same forall data items, ily the 1 the confictn © If data item A has been updated at last by transaction Tj ig are as shown below - icting operations. These schedule SI, then in schedule S2 also, the data item A must pe C7 > ; " saa updated at last by transaction Ti =e © If transaction Ti reads a data item thet has been updated by the [write (ay ———}—___ | tansaction Tj in schedule S1, then in schedule $2 alg Sead ay ——] transaction Ti must read the same data item that has been temp =o updated by transaction Tj. In other words the Write-Reag ae ee sequence must be same. =e 9 Check whether following schedule Is view serializable or not eas (BY Justify your answer. (Note : TL and T2 are transactions), Ains eae explain the concept of view equivalent schedules and conte : Bae en ‘equivalent schedule considering the example schedule given below aa ee a = The de oh is # The preceden is as follows - wal (A) precedence graph is as fol A=A-50 ©—@ write (A) Fig. 0.9: : Precedence gra read (A) ‘oraph temp: = A*O.1 * As there exists no cycle, the schedule is conflict serializable. The A: = A-temp possible serializability order can be T1-T2 write (A) * Now we check it for view serializability. As we get the read (B) Serializability order as T] ~ T2, we will find the view ‘equivalence B= B+ 50 with the given schedule as serializable schedule. rite (B) * Let S be the given schedule as given in the problem statement. Let read (B) the serializable schedule is S'={T1,12}. These two schedules are B: =B + temp Tepresented as follows. CL [ute wy —_e id > [ser + Dec. 18,19, End Sem, Marks 9} rere 7 A Guide for Engineering Sdens Greaney-= sgement sete se Transaction Mang, ae12 Database rey rabase Management Systems Database Transaction Mana Intermediate Read obtained only ater Tt performs We ‘operation Database Man 7 = «mero Ree faa pocorn schedule S for n_| 2 4 ead (A) 1 Consider schedule S for finding intermediate read operation -—— 1 @ read (A) Ac A250 [arc a= 50 | write (A) ml read (@) read ( p read (A) Are A=temp fee Ars Axtemp faa [write ®) | waite (AY read (A) read (B) a temp: = A*0.1 preB+s0 7 \ | — ALS A-temp read (8) =~ | write (A) Sian en write B) oy ae read (B) B:=B+temp B:= B+ temp « Similarly consider schedule S* for finding intermediate read awrite (B) operation. write (B) 7 a ‘Schedule S Schedule $* =r # Now we will check the equivalence between them using following A=A~50 conditions - mere read 1. Initial Read Hoel pay ‘+ In schedule S initial read on A is in transaction T1. Similarly initial “wrte () Y read on B is in transaction TI. * Similarly in schedule $?, initial read on A is in transaction TI. Similarly initial read on B is in transaction T1. 2. Final Weite * In schedule S final write on A is in transaction T2, Similarly final write on B is in transaction T2, * In schedute S final write on A is in transaction T2, Similarly final Write on B is in transaction T2 read A e temp: =A Intermediate Read operation cbtained only ater Tt Azs Antemp performs Wrte operation write (A) read (8) <= B tester wite SSS ote fe_14 Database Transact ee Hon Man *, the intermediat and Sth ntemeit 0d ope jer T1 performs write operation, "Ni, -d bY performe ss thus all the above ES : schedule is view seraliz—DIe caded Aborts, Recoverable a6 Cas Schedules ‘and Nonrecoverable, hort note on = Cascaded Aborts. ation in which the abort of one trang, # Cascaded Abort is a i foees the bort of another transaction 10 Prevel tig ‘tion from reading invalid. It is also called as a action ft ji ae trans Rollback or Cascading ‘Schedule. 4s Forexample - consider the following schedule 11 T2 T3 Read(A) Write(A) Read(A) Write(A) Read(A) Write(A) Failure + Inabove schedule, transaction T2 depends upon T1, transaction T3 depends upon T2Now failure of transaction T1, causes the transaction T1 to rollback, the rollback of transaction T2 causes TS to rollback. Such rollbacks is call ji lled casca rack or cascading abort, oe fe Management Systems - ve 4-15 Database Transaction Man fe the terms tt Define th Revoverable and non re Recoverable schedul A gch pair of tansactions T, oe iously writen by Ty set commit operation of T, If ina a : schedule, when a transaction performs a dirty read operation from an uncommitted transaction and Po mmits before the transaction from which it has read the value then sacha schedule is Known as an iecoverabe schedule Oe 4.7 Concurrency Control 12 What is concurrency contol? AMS. «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 - 1) 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. fi) 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. rhs an non recoverable sched "coverable schedule is one where, ms Ts and T such that Treads ada item ‘Commit operation of T, appears before Ans: nurecoverable schedule :Datahaee Management Systems __ 4216 Datalase Transaction Mo 0.14 Explain two phase locking protocol: He Ans. ‘+ The two phase locking is a pro eben 0) Growing phase (Locking pas) #1 8 hase in wnigg locks but does not release any logy? He oct in which there ae tN pg transaction may obtain I : ii) Shrinking phase (Unlocking phase) + It is @ phase in is the transation may release the leeks But does not obi new lock. : * Lock Point: The las lock position oF Fest UMIOCK postigg called lock point. «For example- Locka) Lock) Lock) Unlock(a) i Unlock) : UnlocitC) + Consider following transactions Ty, T, Lock-X(A) Lock-S(B) Read(A) Read(B) [aeas0 Unlock-S(B) I Write(A) [ Lock-X(B) | Unlock-X(a) [Be B+100 Lock-S(A) [write Read(A) [_Uatock-xiB) "_Unlock-S(A) ‘A Gule for Engincering Students a tw ons Presede all the untogy 4 In above transactions get lock-unlock-lock-unock seq in two phase locking, 15 What are advanta focking ? Ans. Advantages of two phase eckng (1) It ensures serializability SS and disadvantages of two phase Disadvantages of two phase locking protocol (1) It leads to dealocks. 2) It leads to cascading rollback, .46 What are types of two phase locking? Ans. : 1) Strict two phase locking : The strict 2PL protocol is abasic wwo 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 afier commit operation, then only other itansaction is allowed to read or wri . For example - Consider two transactions_ ‘418 Database Transaction Mang, anager SESE atabase Mat he looks then «rw apo! «tu only er commit opeaion in Ty, We can unlock g | cexclsive lock. This ensures te strict serializability, «thus compared to base two phase Locking protocol the advantg, | ftiet PL protoco ist ensures strict serializability. | 2) Rigorous two phase locking : This is streter two phase locking protocol. Here all locks are to be held until the transaciog Commits, The transactions can be seriealized in the order in whieh they commit. Example - Consider transactions Tt R(A) RB) wo) «If we apply the locks then ™ Lock-S(A) R(A) Lock-X(B) | “A Gude for Engineering Sdess Management Systems 4. a a 19 Database Transaction Menagement We) | ; | Untockcay above transaction uses i ie SES Figorous two phase locking smechanis™- Se eee ae aeeaL EE | 4.9 Time-stamp based Protocol | et | se a transaction, tssu. 147 Suppo" 168 8 read command on data Item Hej to be executed oF not using neetamp based orsjocol of concurrency control, UEP [SPPU :Dec.-17, May-19, End Sem, Marks 9] as. Aa ga: Temecton Tas ret open 5) IFTS(T) < WTSC), then read(X) is rejected. T has to abort and be ejected. ii) If WTS(X) S TS(T), then execute read(X) of T and update RTS(X). case 2 (Write) : Transaction T issues @ write(X) operation i) ITS(T) < RTS(X) or if TST) < WTS(X), then write is rejected ii) If RTS(X) < TST) or WTS(X) $ TS(T), then execute write(X) of T and update WTS(X), Example for 4 (Read operation) () Suppose we have two transactions T, and T, with timestamps 10 sec. and 20 seg. respectively. 20 Sec4-20 Database Trnsacto a | Oggi 20 eC WE BENE 1 It ea 7si7,) i€ read operation on Ty HE Fosec | 20Sec 1% t RO) Woe) : WO), > Pro timestama than the | ee Fig.@t7.4 5) Suppose we have two transactions T and T, with timestamps 10 sec, and 20sec. respectively. [rose | (od, 20 See 1 | {7% | wea) | ROX) RTS(X) and WTS(X) is initially = 0 Then WTS(X) =10 as transaction T, executes, Now if Read operation R(X) occurs on transaction T, at TS(T;) = 20 then | TS(T;) ie, 20 >WTS(X) which is 10, hence we accept read | operation on T. The transaction T will perform read operation ‘nd now RTS will be updated as, psnctting FE “tte RIS 1 Gulde for Engineering Sten , exam ose we have WO transac eaasannose e MIVE (80 Lansactons , and T, wth sinesampe 10 sec. and 20 sec. | WX) RTS(X) and WTS(X) is initially = 0 Then RTS(X) = 10, when transaction T, executes fier that WTS(X) = 20 when transaction T, executes Now if write operation W(X) occurs on transaction T, at TS(T,) = 10 then TS(T,) ie. 10 operation on Ty ‘and now WTS will be updated as, WIS(X) = 20 —_——$$=—<—$—— 4.10 Deadlock Handling 0.18 What is deadlock ? Explain the four conditions for deadlock to occure. 5 Ans. «Definition : Deadlock can be formally defined as - “A system isin deadlock state if there exists a set of transactions such that every transaction in the set is waiting for another transaction in the set.* WTS(X) which is 10, ence we accept yng ‘The transaction Ty will perform write operating + 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 Fesource that cannot be used by more than one process at atime, 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 résource cannot be forcibly {aken from a process. Only the process can release a resouree that is being held by it, ‘ ‘AGuide for Engineering Sle nase Management Systen mS A cond second process is waiting for third process noes Poeess and process is waiting for the fist chain of waiting. 4.19 Explain walt for graph algorithm in deta ans. «In this method a graph s created based onthe transaction and th tock If the ereted graph has a eycle or closed loop, os then there is ‘a deadlock. en # The wait for the graph is maintained by the system for every transaction which is waiting for some data held by the others, The system keeps checking the graph ifthere is any eycle in the graph. © This graph consists of a pair G = (Vv, 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 trnsation T, is no longer holding a data item needed by transaction T,, © For example - Consider following transactions, We will draw a ‘wait for graph for this scenario and check for deadlock. a Ra)_| RA) W(A) RB) Wa) W(B) — ee,4.24 Database 1TANSAEHON Mayne, tabase Management . ec Ful + Wewill we three US fT, has Re re for designing the wait-for graph les for desist operon and ten T2 BOS WHE ope jon and then T, has Read opera, m pute 4: 17 be et Then draws anv edge Ty” 72 e217, has WeHte erst oT, en draw an edge Ty? T ; — then dra 1g T, has Write operation and then T, has WHE opera, Rule Mee T> Tr then draw an edge fe Letus draw waitefor gph “+ s_ Draw vertices fr all the transactions step 1: Draw Fig. 0.19.4 stop 2 We find the Read-Write pair from «wo different transaction ser sng fom tp to bottom, If such as pa is found then we wl agg the edges between coresponding directions. For instance ~ 7 Te RA (Re) = Re) WA) we) Fig. 219.2 Management Systems a 4°25 Database Transaction Management As cyele is detected in the waitfor further process. The deadlock ig scenario. raph there is no need to Present in this transaction L__S12 Recovery Methods 0.20 What Is the purpose of database recovery ? Ans. = «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 availa transaction purpose. ity of the database for + 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. 2.21 Explain the shadow paging technique of database recovery. Ans. + 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. Q21.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 rectory is used by the transaction. Grcoorspoge 3 (8) a) nec vnseng pepe dee Fig. 0.21.1 : Demonstration of shadow paging + During the execution of transaction, the shadow directory is neyey modified. + When & write operation is t0 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 writen 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. ‘A Gulde for Englncering Suden®s Cheek 2 Checkpoints | a.22 What Is checkpoint ? Ans. = « Checkpoint is a mechanism. where al I the 0 removed from the system and stored p. Previous logs are 1 ermanently ina storage disk «Checkpoint declares point before which the DBMS was in consistent state and all the transactions were committed The recovery system reads the logs backwards from the end to the last checkpoint. «Performing a checkpoint consists of the following operations © 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. 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 fils before reaching 0 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. ron sq«For exampl Consider two transactions 71 IT, and T B occurs Ty, th Bead (A, a) | Read (C. 2) aza-10 | om e=20 jas Wate (A, a) | Write (C6) Read (B, 6) b=b+10 Write (B, b) are executed serially with initial values of A = 199 4) Just after write (B, b) b) Just after write (C, ¢) ©) Just after <1),B, 210, A=90 B=210 ‘ ust sust after Write operation, no : Sommit record appears in log. Hence no write operation is performed on database. So database retains nly old values. Hence A = 100 and B = 200 respectively ‘Thus the system comes back to original position and no redo operation take place. 4. The incomplete transaction oT, canbe deleted from log. py dust ater write (©) |) The state of log records is a follows {ote that crash occurs before T; commits. At this point T, is ‘completed successfully, so new values of A and B are written from Jog to database. But as T, is not committed, thee is no redo (T,) 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 : < Ty, A, 90> Crash occurs here © Clearly both T, and T, reached at commit point and then erash ‘occurs. So both redo (T,) and redo (T,) are done and updated 0.Database Mart (2.24 Explain Immediate det Ans. : - i it reaches to its c «sf the transaction ges failed before ik rea! HS commit pin, se sca ROLLBACK Operation needs t0 Be done to bring database to its earlier consistent state. That means the effeg, i operations need to be undone on the databases For that pup. hath Redo and Undo operations are both required during recovery, This tectnique is known as UNDO/ REDO technique «+ For example : Consider two transaction T, and T; as follows fon 7 10 Database Transaction ment Systrs {base modificatio ay Read(A,e) | Read(C,c) a=a-l0 e=c-20 Write(A,a) | Write(C, ¢) Read(B,b) | be10 Write(B, 6) * Here T, and T, are executed serially. Initially A = 100, B = 200 and C=300 ‘© Ifthe crash occurs after i) Just after Write(B, b) ii) Just after Write(C, ¢) iii) Just after on facie, i using the immediate Database modification approach the result of above three scenarios can be elaborated as follows : went Systems ysdoee 4-31 Datebase Transact contents of log and database is as follows ‘Log. » Thee pStart> 1s The recovery scheme uses two recovery techniques - i) 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 (1) : 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 . Hence-T, must be undone. That means old values of A and B are restored. Thus old values of A and B fare taken from log and both the transaction T, and T; are re-executed. b) Just after Write (C, 6) + Here bot operations will occur. th the redo and undose Managemen ) Undo + When sYS'eM comes back from this crash, it Ue iis Ty Str but mo $0 A =90, B=210 and C= 300 oy dust alter + Here id, name are the keys and 1,2, “Ankit”, “Prajita” are the values corresponding to those keys. + Key-value stores help the developer to store schema-less data . They work best for Shopping Cart Contents. ‘+ The DynamoDB, Riak, Redis are some famous examples of key- value store. (2) Document Store © The document store make use, of key-value pair to store and retrieve data. ‘* The document is stored in the form of XML and JSON. ‘© The document stores appear the most natural among NoSQL database types, ‘© It is most commonly used due to flexibility and ability to query on any field. rn tice le SsData ss 5-6 NoSQL Databes, © For example - + MongoDB and CouchDB are two popular document oriented NoSQL database. (@) Graph «The graph database is typically used in the applications where the relationships among the data elements is an important aspect. «© The connections between elements are called links or relationships, In a graph database, connections are first-class elements of the database, stored directly. In relational databases, links are implied, using data to express the relationships. + The graph database has two components - be 1) Node : The entities itself. For example - People, student, 2) Edge : The relationships among the entities. ‘© For example - appears for * Graph base database is mostly used for social networks, logistics, spatial data. The graph databases are - NeodJ, Infinite Graph, OrientDB. ‘A Guide for Engineering Studenes atabase Management Systems ure. «+ In this model number of columns are not fixed for each record databases i # Columns databases can quickly aggregate the value of a given column. © For example - Row ID Columns... 1 Name City Ankita Pune 2 Name City email Kavita Mumbai __| kavital23@amail.com ‘s The column store databases are widely used to manage data warehouses, business intelligence, HBase, Cassandra are examples of column based databases. {6 BASE Properties Q.7 Enlist the BASE properties that NoSQL follows. Ans. : 1) Basically Available : It means the system is guaranteed to be available in the event of failure. 2) Soft State : It means, even without an input the system state may change. 3) Eventual Consistency : The system will become consistent over time.Database Management Systems 5.7 ACID Vs BASE i SOE Data, Delay 2.8 What ie the difference between ACID and BASE properties > Ans. : AcID Ik stands for atomicity consistency isolation and durability 2._| It shows consistency, 3. | Availability is less important. Evolution is difficult 5._| It posses expensive joins | and relationships. 6. | Ithas high maintenance costs, Lit provides vertical scaling. 5.8 Comparative Study 2.8 Give the difference between RDBMS and NoSQL. Ans: ere aa It stands for basic availabilty soft state eventual consisteney, represents weak consisteney Availability of system is more important. Evolution is easy. Itis free from joins and relationships. Ithas low maintenance cost pee eee eee It provides horizontal scaling LK provides horizontal scaling | ‘of RDBMS and NosQl Ld Sr. RDBMS No. NoSQL. 1 | The relational database | system is based on relationships among the tables, It is non-relational database system. It can be used in distributed environment, Itis vertically scalable. Itis horizontally scalable. Se] — thas predefined schema I does not have schema ‘rit | Vit uses Son venga have relaxea se 4. | uses SOL to query he | poems sshema, | database, nik wrsructred query] |— languag database. [ment based, graph pee __ | tastorteyane nan” | 6. | teemphasizes on ACD Properties (Automicity, consistency, isolation and | flows Bewers CAP ‘theorem (Consistency, | e availabilty and partion durability) tlemnee) | 7._| Schema is fixed or rigid. [Schema is namie | Pessimistic, Optimist | 9. | Examples: MySQL, Examples: MangoDB, | Oracle, PostgreSQL BigTable, Reais | Q.10 What is MongoDB ? Enlist the features, Ans. : MongoDB is an open source, document based database. Features of MongoDB 1) This a schema-tess, document based database system. 2) It provides high performance data persistence. 3) It supports multiple storage engines. 4) Ithas a rich query language support. 5) MongoDB provides high availability and redundancy with the help of replication, That means it creates multiple copies of the data and sends these copies to a different server so that iF one server fails, then the data is retrieved from another server. a inane SernNoSQL Data, CRUD operations of MongoDB, a short form of the Create, Reag, ‘These operations are the basic ny database. Database Management Syste (2.11 Explain with example the ‘Ans. : The CRUD operation i Update and Delete operations: tone tat re nrmally performed 002 operations t (1) Create Database «Open the command prompt and type the command mongo fap starting the mongoDB. The > prompt will appear. For cresting database we need to use the “use” command. Syntax = ‘ue Dutabaas|aame For example ‘© To check the currently selected database, use the command db st conmewhonet- nome ~ a» ‘+ We can see the list of databases present in the MongoDB using the ‘command show dbs x con-ne Ft nans =a x * Note that in above listing we can not a see the myst a This is because we have not ieee Tee erted any document to it, A Gull for Engineering Stiens, pees oct é {@) Display Collection (Read Operation) © To check the created collection use the command “show collections” at the command prompt (4) Drop Collection (Delete Operation) * The drop collection command is actually used to remove the collection completely from the database. The drop command removes a collection completely from database. ‘syntax \apicollection name drop0) For example(8) Insert Documents # The document is inserted within the co! analogous to rows in database. Syntax : ‘ab.collaction name inset ((hey.velue) For example waar oat. rd a) (6) Update Documents ‘© For updating the document we have to provide some criteria based on which the document can bé updated. Syntax ‘db collection aime update(evtoria update data)” For example - Suppose the collection “Student details” contain following documents “A Guide for Engineering Staden NoSQL Database, lection. The document jg stems 3 > And we want t0 change the name “CCC 4 ‘command can be issued as ° NoSQL Databases “WWW, then the (CATER tetany ia} i t So Se SaaS Se g : «Thus the document gets update, @.12 How to create an Index in MongoDB ? ans. ‘e. Syntax for creating index is Seas aA © The key determines the field on the basis of which the index is created. After the colon the direction of the key(1 or -1) is used to indicate ascending or descending order. © The MongoDB will generate index names by concatenating the indexed Keys with the direction of each key with underscore as separator. For example if the index is on the field name and the order as I then the index will be created as name_1. © We can also use name option to define custom index name while creating the index. ‘= For example - $idb Stident_ details create! Goo $a gS ((oamail}, (name? Stident's Names"} )Database Management Systems 2.13 Explain the concept of aggregation in MongoDB. Ans. : + Aggregation isan operation used to process the data that resus, computed results, The aggregation groups the data from mujin, documents and operate on grouped data to get the combined regu The MongoDB aggregation is equivalent to count) and wig, group by in sql. MongoDB supports the concept of aggregation framework. The typical pipeline of aggregation framework ig 4. follows - Input Output Grate Soreiip } [Seon Fig. @.13.1 : Aggregation framework 1) SmatchO stage - filters those documents we need to work with, those that fit our needs 2) Sgroup( stage - does the aggregation job 3) SsortQ) stage - sorts the resul require (ascending or descending) 1g documents the way we © The input of the pipeline can be one or several collections. The pipeline then performs successive transformations on the data and the result is obtained. Syntax for aggregate operation —_ ‘db.collection_name.aggregate(aggregate_operation) Q.14 What is map reduce in MongoDB ? Ans. : * Map reduce is a data processing programming model that helps in performing operations on large data sets and produce aggregate results ‘* Map reduce is used for large volume of data, The syntax for map reduce is >db.collection.mapReduce( eo ae fanction() {emit(key,value);}, <~- map function fanction(key,values) {retum red Ate seduce Biocon! = 1 Gal for Entering Sates patos Management Sevens tion, < the fs eata ie RAPE AGES Can ba eee very, documnnt, for: document mit: number i jnto small data sets across multiple MongoDB instances, 1s It is not replication of data, but amessing diferent dat from different machines. ‘+ Sharding allows horizontal scaling of data stored in multiple shards or multiple collections. Logically all the shards work as one collection ‘¢ Sharding works by creating a cluster of MongoDB instances which is made up of three components ‘0 Shard + It is a a mongodb instance that contains the sharded ata, The combination of multiple shards create # complete data set © Router : This is a mongodb instance which, is basically responsible for directing the commands sent by client to appropriate server. + This is mongodb instance which holds the o Config server + : information about various mongodb instances which hold th shard data. ENDpa rent Systems Aldoances in Databases @ It is @ conceptual database 5, information that adds basic mean among the data yystem that include semantic W of the data and relationships tic da 4 The semantic database ‘systems allow easy development of application programs and also it becomes easy to maintain such database system when data is updated. atures a enecingoatboes | .1 Explain the terms - 1. Active database 2. Deductive database, Ans.: 1. Active database ‘+ Active databases are the databases which consists of triggers. The situation and action rules are embedded in the active databases. The active databases are able to react automatically to the situations in the database. The trigger is a technique for specifying certain types of active rules. The commercial databases such as Oracle, DB2, Microsoft SQLServer allows the use of triggers. 2. Deductive database : Deductive database is a database system that can make deductions based on rules and facts stored in the database. Deductive databases use the concept of logic programming for specifying the rules and the facts. Prolog is a popular programming language which is based on the concept of logic programming. Q.2 Write short note on - Semantic database. Ans. * Semantic database management system is a system that stores the meaning of information as facts about objects. * Semantic databases represent the data models in which data is arranged in some logical manner. ee on __ Semantic database systems are exceptionally usable and flexible. ‘They have shorter application design and programming cycle. . It provides user control via an intuitive structure of information. . It empowers the end-users to pose complex, ad-hoc, decision support queries. ‘These are highly efficient database systems. Q.3 Enlist the features of Semi-structured Data models. Ans. L. ‘The semi-structured data can not be stored in the form of rows and columns in databases. ‘The semi structured data does not obey the tabular structure of data ‘models. But it has some structure, ‘Semi-structured data contains tags and elements which is used to group data and describe how data is stored. 4, ‘The entities can be grouped together based on their properties. 5. The entities in the same group may or may not have As the semi-structured data the same attributes(properties). ; does not have well defined structure, it nal programming, can not be programmed easily by the tradi languages.6.3 Nested Data Q4 Give an example of JSON object. A ‘+ ISON object holds the Key value pair. * Each key * The key and value are separated by colon. © Syntax {otsing CD, A>C) Here (AB) is a candidate key because (AB)+ = {ABCD} = {R) Hence {A, B} are prime attributes and {C, D} are non prime attribute. In A->C, the non prime attribute C is dependent upon A which is actually a part of candidate key AB. Hence due to A>C we get partial functional dependency. sD