Lossless Join Decomposition in DBMS | Non additive join decomposition property in dbms

Video Statistics and Information

Video
Captions Word Cloud
Reddit Comments
Captions
in the previous video we have discussed one property of the composition that is a dependency preserving right and in this video we will discuss the second property of decomposition that has lost less join decomposition this is mandatory property for decomposition it means the decomposition must be lossless the dependency preserving property that is you can say it's not a mandatory property why so because sometimes it is not possible to get dependency preserving bcnf decomposition right but up to third and if it is always possible to get a dependency preserving the composition right that is why somewhere it is written that the dependency preserving properties were optional right but when it comes to property of decomposition then there are two properties of decomposition dependency preserving and lossless during decomposition right I hope you know what is the composition and why we do decomposition basically to do to perform her to perform normalization means to convert a relation into higher normal form right if a relation is in 2nf and you want to convert it in to be CNF then we will decompose that relation into multiple relations right that is decomposition what that is why we need decomposition join means combine to combine something right or to merge and lossless means without any loss simple English meaning is this thing right now the meaning of this complete word is what lossless no enjoying decomposition in the context of database that I will discuss with the help of a proper example what is lossless join decomposition right see suppose I have a relation R right and I have performed decomposition on this relation to convert into higher normal forms suppose I have decomposed it into R 1 and R 2 2 relations only you can decompose it into R 1 R 2 R 3 multiple relations right suppose error hi all decomposed it in into R 1 and R 2 right now if I ask you one question and we have performed our operations and all but sometimes suppose after sometimes we need to combine these two relations right now the question is if I combine these two relation again in simple terms I am saying combined word or you can say if we join these two relation obviously we are going to perform natural join operation here right so if you can join these are these relations then should you get the same relation are yes or no here means after combining after joining these two relation should this resultant relation be equal to this original one definitely yes it is common sense right or you can say that see this is the relation original one parent one and this only we have decomposed this into two sub relations right and after that once you sometimes later when you will join these two then definitely we will get the same relation right exactly same whatever the value of R whatever the digit data in are exactly same data should be present in this are after joining right if this is a case then it is you can say that lossless join be composition so in simple terms what you can say what does this property say that a decomposition of a relation R is said to be lossless if it is feasible to reconstruct the relation R from decomposed sub relations using joints then you can say that that decomposition is lossless I am going to write down the summary of this lecture at last in form of three or four points right and you will also discuss with the help of one or two examples that the decomposition is lossless or not how to find out that the decomposition is lossless join decomposition or not right now suppose I have decomposed in this relation into PO sub relation R 1 and R 2 now you have to check is this decomposition lossless join the composition or not now obviously for that you have to join these two relation you have to combine these two relation right so you must know what is join operation how to perform natural join on relations so let me give you a quick introduction of natural join operation with the help of an example say I am taking a simple example suppose I have these two sub relation r1 and r2 right the data is this one small relation I am taking now what is the result of Cartesian product first of all I am going to tell you Cartesian product because natural join is improved version of Cartesian product then only you can get it better that what is natural join so how to do Cartesian product of carbon in our two simple as what obviously we will do what in our one I have I'm having a B in R why I am having BC so in Cartesian product of r1 and r2 this would be the resultant table right now Cartesian product is what see the first row of this r1 would be combined with each row of r2 right means here we have 1 1 then it will be combined with first row then again we have 1 1 then it will be combined combined with 1 2 then again 1 1 it will be combined with these 3 2 1 right second is again the second will be combined with each row same third row will be combined with each row this is what Cartesian product right so the answer is so this is the Cartesian product of these two means each row of one relation will be combined with each row of other relation right so the resultant here we have what nine rows 3 into 3 right now what is natural join this is improved version of this Cartesian product right now in natural join of these records you will consider only those records in which in which see here the common attribute is B right so we will consider only those records in which are one dot B how one is the name of this relation is equal to R 2 dot B B is what that common attribute in these two so if you have common attribute in the relation then only you can apply natural join I'll also discuss if no common attribute is there then what will be the result of natural journey first of all so now see here this bees of our one this bees of our two right so now our one dot B are two dot B both are same so we will consider this record and see I'm taking like this 1 1 1 1 here also 1 1 will consider this also in this R 1 dot B is 1 R to go to bees to will not consider this one because this condition is not satisfied so this would not be included in natural join this double here 1 1 so definitely you would consider this one here also 1 1 so we will consider this one also everyone to will not consider this 1 2 and we will not consider this 1 2 and not equals will not consider this 1 2 2 it is equal so will consider this one so now the result of natural join would be this one only now see here B and B both how to click it right so no need to write it write down again B you just write down single B so there is a return table how you will write like this the natural join of these two would be this one only 5 records would be there in Cartesian product 9 records would be there now if no common attribute is there suppose here I am having R 1 is a B and R 2 is C B so I'm asking you are one natural join are to what would be the result because there is no common attribute so we cannot apply this condition so the result would be same you just do Cartesian product and that would be the result of natural join as well because there is no common attribute in that case the result of Cartesian product would be same as the result of natural job like if there is no common attribute and if you want to join suppose R 1 R 2 R 3 R 4 multiple table tables are there sub relations are then you want to join these all these so at same time we cannot join all the 4 because the join this one is what binary operation so at first just take two either you can see R 1 R 2 suppose I am taking only 3 or you can take R 2 R 3 or you can take R 1 three suppose I am taking these two so r1 and r2 after joining become suppose r1 are going to after that you can join it with r3 like this you can perform your own operation all the type of these all the variants we will discuss one by one later in all the examples right so I hope you got how to perform natural join right now check this decomposition is lossless join decomposition or not I have decomposed this into r1 and r2 so R 1 is having will these require r2 is having these records right now perform r1 natural join our two if after joining these two you get the same table as are exactly same records only four tuples exactly same tuples then you can say that it is lossless in Joran otherwise not right now see what you will get so here the common attribute is B so just apply this condition right so here we are not going to combine this row with each row of the r2 we will combine this with the row far too in which this B value is same as of r1 see here B value is 1 so can you combine this with this first one yes because here also B value is 1 so though 1 record would would be I am NOT going to run it right down b2 times because that would be duplicate only one time you we're going to write 1 1 and 1 can you combine this with this yes because here also be 1 here also be 1 right so 1 1 2 can you combine this row with this third one no because here B value is 1 here is 2 can you combine with this one no okay now the next one can you combine this with the first one yes this with second one yes because 1 + 1 B value sing so to motor purrs now can you combine this with this no can you combine this with this no now this 1 3 2 now come can you combine this one with this row know the value is 1 here B value is 2 not same so we can combine this with only this record so 3 2 1 and we can combine this one this this only so four three two I hope you got that we will get this result only right now see in the original one I have one one one yes we got this one - one two - one - yes we got this one three two one yes you got this one and four three - yes you or this one right but these two records are extra records now please don't say that this is lossless why because we got everything whatever is there in our we got everything and even we got something extra so it is not loss see it is we have gained something right no the extra is very dangerous when you are dealing with the composition right we are not going to accept any extra record yeah extra is good in real life because I don't you'll be happy if someone will give you something extra but in this case it is very dangerous so this is not lossless you must get exactly same relation as the original one no less records no extra records right so this property ensures that you will get exactly the same relation as the original one right right after joining the decomposed relations no extra topple no less step right and maybe suppose I am taking this the composition r1 and r2 here I'm having a B here I'm having only B although this decomposition is logically not possible but suppose you have given something like this and you are asked that tell me it is lossless or not definitely by looking at this only you can see it is lossless why so because here I have I'm having C but here I'm not having any attribute C right so C the one first property is what the union of attributes of the decomposed relations must be equal to that reviewed of the original relation right if suppose I am having to have decomposed a relation into r1 and r2 so you can say that attribute of r1 Union r2 of our two must be equal to attribute oh ah definitely right so if we have BC then it's fine ABC Union is ABC and attribute of RS also ABC right second property you can say suppose there is no common attribute then I have already discussed the result of the natural join would be same as the result of Cartesian product right and in Cartesian product we are obviously we are getting extra apples I have already discussed here right so in that case also it is lossy it is not lossless so there must be common attributes between the decomposed relations right suppose I have decomposed into two sub relations so you can say attribute of r1 intersection attribute of R 2 intersection should not be fine it means there must be some common attribute at least one common attribute if you do intersection of a B & B C you will get what B and that is not fine if you will get intersection of like this CD suppose I am having one more attribute C sorry B a B and C D is r1 and r2 having any common attribute no right so definitely by looking at this only you can say it is lossy it is not lossless no need to check that do the natural join and all because definitely after natural join you will get something extra in in the resultant table but here see this property satisfied this property is also satisfied in this case but still it is not lossless so there is one more third property also that is very important C Union is ABC find common attribute is they are fine but still it is lossless why so because here see this B is having duplicate values right because of this because of this one this is having duplicate value so it will be combined with one in two rows it is also having duplicate it will be combined with two rows here it's fine it will be combined only this row and this row so one important property is what the common attribute must be a super key or you can say candidate Li if the common attribute is super key of either r1 or r2 or you can say if the common attribute is super key of at least one sub relation then definitely that would be lossless join be composition right I am having two sub relation so common attribute is B if B is super key or at least one subrogation either r1 or r2 or maybe both if being super Q of R 1 then also it would be lost less if being super clear car 2 then also it would be lost as if we super key of r1 and r2 both then also it would be lossless right so let us take this type of example now let us take this decomposition r1 is having a B and r2 is having a C right first of all see the union of these one attribute of these 1 ABC union of attribute of these subrogation is ABC is equal to U is equal to the attribute of okay do you have any common attribute yes I have common attribute right now check this is lossless or not now first of all check using natural join I'm going to do natural join are ones natural join are two so the common attribute is a so we are going to join based on this a see see the first row can you combine this row with this first one check the value of a here also and here also nearest definitely I can combine with this a right so the answer is 1 1 1 1 2 per second can you combine this with this here value of a is 2 here value of phase 1 no value is not same can you combine this with us no with this no ok second one can you combine this with this no when you combine this with this record yes so the next Apple is 2 1 2 right can you combine this couple of this one with this one no because value phase not saying value phase not so you're not saying this you can combine only with this and I guess now we are going to this you can combine only with this so next record is 3 2 1 4 3 2 this is the resultant natural join table now you can see it is exactly same as the original one so this is what lossless this decomposition is lossless but this was not lossless right see now here you can say is what you can see directly you can see here is what super cool you can see candidate right using a candidate key of either relation I am NOT saying that the common attribute is candidate key for the original relation no just forget it right just check the common attribute is super key or candidate key of either of either this relation or this relation it should be candidate key for at least one sub relation now how to check that is candidate key first of all check is candidate key for r1 or not see if a is candidate key of any relation then definitely using that we can derive all that the beauty of that relation now can we drive be using a here because I am having only two attributed definitely using a I can drive a that is for sure trivial functional dependency here you have to check can you drive this one is this functional dependency possible in this relation have to check that already we have discussed one of the previous video you can check out that video in the side button yes this dependency exists here in this r1 so here you can see a is candidate for this relation so no need to check for this one fortunately is candidate key for this whole so you can check it right here in this case a is candidate key for both the relation but if a is candidate key for the first one so no need to check for second one that will be lossless join decomposition right so here in short you can say that three property must be satisfied to be lossless join decomposition first of--first to I have already discussed let me write down again so here you can say if a relation R is decomposed into two sub relation R 1 and R 2 then this decomposition is lossless if these properties are satisfied attribute of R 1 union attribute of R 2 equal to a degree 2 5 right intersection of attributes of the sub relation should not be Phi right third property is what if I have told you if the common attribute is super pure candidate key for either this relation of this relation so how we are going to write down in two technical terms right so you can say common attribute is what obviously intersection of this one and this one so attribute of R 1 intersection a tribute o fire to right must drive must derive all the attributes of either this relation or this relation so all the attributes of either R one attribute Arbonne or intersection can derive all the attributes of this all to see this is or either this or this if one of this these properties is satisfied C 1 is this one one is this one and at least one of these two property then you can say that the decomposition is lossless now suppose the data is not given only relation is given and functional dependencies are given in that case how to find out that that thus this decomposition is lossless join decomposition or not so that we'll discuss in next video in this video see I have discussed in detailed manner just to clear out your basics that what does this lossless joined decomposition write in next video we'll discuss few more example of this type and simple trick how quickly you can find out that if in gate exam or net exam this type of question is given dependencies or you can say that this type of data is given and you can say this decomposition is given then how quickly you can identify that this is lossless or not right so that thing we'll discuss in next video so now I will see in the next video to the nobody care
Info
Channel: Jenny's lectures CS/IT NET&JRF
Views: 52,133
Rating: 4.9506173 out of 5
Keywords: data structure tutorials, operating system, data structure and algorithms, lossless join decomposition in dbms with example, non additive join decomposition property, how to check decomposition is lossless and dependency preserving, lossy and lossless join decomposition in dbms, jayanti khatri lamba, jenny's lectures cs/it NET&JRF, jenny data structure, jenny lamba, ugc net computer science, gate cs lectures, computer science youtube channels, dbms tutorials for beginners
Id: zb8ESEf36Zc
Channel Id: undefined
Length: 21min 57sec (1317 seconds)
Published: Fri Jan 10 2020
Related Videos
Note
Please note that this website is currently a work in progress! Lots of interesting data and statistics to come.