YT YouTube2Text

YouTube2Text → Transcripts → Relational Database Design (Contd.)-1

Relational Database Design (Contd.)-1 — Transcript

by Data Base Management System - IITKGP · 4,407 words · 817 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:00[Music]
0:15welcome to the
0:17module 17 of database management systems
0:21ah from the last module we are
0:23discussing relational database design so
0:25this is second in the series of ah five
0:28modules which will discuss this
0:32we have already seen ah
0:36basic features of good relational design
0:38we have studied about first normal form
0:40atomic domains and got introduced to
0:42functional dependencies so
0:44we will develop further on that
0:46to see how decompositions into good
0:48design can be done by making use of the
0:51notion of functional dependencies and
0:53we will more formally introduce the
0:56theory of functional dependencies
0:58so that is all that we discuss in this
1:01so decomposition using functional
1:03dependencies is the first thing that we
1:05look at and the first normal form of
1:08relations which
1:10was studied we look at is voice code
1:12normal form so normal forms are ah kind
1:15of set of properties which is satisfied
1:19by a relational schema and if they are
1:21satisfied then we have certain
1:23guarantees in terms of what can or
1:26cannot happen in that relational schema
1:29design
1:30so voice code is a
1:32simplest kind of beyond 1nf is a
1:36simplest kind of normal form and a
1:38relational schema is said to be in voice
1:40code normal form if with respect to a
1:43set of functional dependencies
1:46all functional dependencies in the
1:48closure so in respect of f we compute f
1:51plus which is a closure
1:54and if i have a dependency
1:57alpha determines beta
1:59then naturally
2:01alpha will have to be a subset of r beta
2:03will have to be a subset of r but what
2:05is important is every functional
2:07dependency in the closure set must
2:09either be trivial
2:11that is right hand side is a
2:13super set of the
2:15right hand side is a subset of the left
2:17hand side
2:19or
2:20the
2:21left hand side
2:23set alpha must be super key
2:26so only those kind of ah functional
2:28dependencies are possible no other
2:30functional dependencies are possible if
2:32that is satisfied by the relational
2:34schema are then it is said to be in the
2:37voice code normal form
2:39so
2:40you can if we look at
2:43ins department
2:45schema of the combined relations we saw
2:47last time
2:48then we will know that ah certainly this
2:50is not in voice code normal form because
2:53ah this functional dependency holds
2:56in this schema
2:58where it is neither a
3:02a trivial dependency and nor department
3:05name is a super key
3:07so this is not in bcnf
3:11so if a relational scheme is not in bcnf
3:14then the question naturally is can i
3:16make it into bcnf so then that process
3:18is a process of decomposition so what
3:21you do you
3:22divide the set of attributes into two or
3:25more at
3:26sets of attributes so here ah let us say
3:30that
3:31we have a relational schema which has a
3:33non trivial dependency alpha determines
3:36beta where alpha is not a super key so
3:39with respect to this functional
3:41dependency the relational schema is not
3:43in bcnf then we can decompose r by
3:48two
3:48sets one is alpha union beta take the
3:51union of these two attribute sets
3:54and
3:55remove
3:57beta minus alpha from r take the
4:00difference of beta minus alpha and
4:03remove that from r
4:05the resulting
4:06pair of relations relational schemas
4:09will be in voice code normal form with
4:12respect to this particular functional
4:14dependency
4:16so
4:17let us
4:19see an example so if alpha is department
4:21name
4:22beta is a pair of attribute building and
4:24budget we have department name
4:26functionally determines building budget
4:28so alpha determines beta and we have
4:30already seen that
4:32it does not ah hold
4:34ah it is not satisfied by the ins
4:37department so you replace it by taking
4:40alpha union beta so alpha union beta is
4:43this
4:44ah set of relational ah
4:46this relational schema
4:48and you do r minus ah beta
4:51ah r minus
4:53difference of beta minus alpha beta
4:55minus alpha naturally if this is beta
4:57and alpha then beta minus ah alpha
5:00is
5:01necessarily building budget
5:04because
5:05the department does not occur in beta so
5:07this set is building budget and if i
5:09remove it from r which means that
5:12id name salary and department name are
5:15retained but building and budget gets
5:17removed
5:18so i get another
5:20relational schema which has these four
5:22names and it holds the
5:26ah functional dependency id determining
5:28so now if i look into this schema r one
5:32and this schema r two
5:34there are different dependencies that
5:36hold on r one
5:38and with respect to that dependency r
5:40one is in bcnf because department name
5:42is the super key is a key primary key
5:46and with respect to this dependency r
5:49two is in bcnf because id is the key
5:53so i can see that the original combined
5:56relational schema was not in bcnf with
5:59respect to this functional dependency
6:01but
6:02when i do this decomposition i get two
6:05schemas which are each in
6:08pc and f normal form so this is the
6:10basic process and we will see ah
6:13depending on the normal form and
6:14different notions of functional
6:16dependencies we will see how these
6:19conversions can be done but this is a
6:21basic approach of converting a schema
6:24into a normal form
6:26now
6:28ah
6:29the question is if
6:31the constraints including the functional
6:33dependencies
6:34if we look at then functional
6:36dependencies will have to be checked on
6:37different instance
6:39now in general it is difficult to check
6:42a functional dependency alpha
6:44determining beta
6:46if the attributes alpha
6:49and
6:50the attributes of beta or the attributes
6:52of beta are distributed between multiple
6:54relations because naturally how do i
6:56check if they are true if how do i check
6:59that two tuples which match on alpha is
7:01indeed matching on beta unless i perform
7:04a costly join operation
7:06so there is ah
7:08[Music]
7:10the objective is to be able to come to
7:13designs where
7:15it is sufficient to test only those
7:17dependencies on individual relations
7:20of the decomposition
7:22and with that i must be able to ensure
7:26that all functional dependencies hold
7:28so its a very interesting situation so
7:31we are saying that we will decompose get
7:33into a number of relational schema
7:36every schema will have a number of
7:38dependencies functional dependencies
7:40so and those functional dependencies if
7:44they
7:45involve only the attributes of that
7:48relational schema they can be tested
7:50very easily
7:51and if these functional dependencies
7:53together mean ensure
7:56that all functional dependencies hold
7:58that is
7:59if the closure of this set of functional
8:01dependencies is same as the
8:04closure of the earlier set the original
8:06set
8:07then we say that the decomposition that
8:10we have achieved is dependency
8:13preserving
8:15because
8:16ah i can actually effectively compute
8:20this is dependency preserving because i
8:23can effectively compute whether every
8:26dependency
8:27is
8:28satisfied
8:30by checking on every individual relation
8:34but the unfortunate part of the reality
8:37is that it is not always possible
8:40to achieve a voice code normal form
8:43decomposition
8:45which also preserves the dependencies
8:48so
8:49if there are in some cases will be able
8:51to do like the example we saw
8:53ah just now ah the instructor and
8:55department
8:57but
8:57it is not always possible so we usually
9:01need another weaker form
9:03normal form which is known as a third
9:06normal form
9:07and
9:08we will subsequently look into those
9:11a third normal form
9:14is again a relational schema is there
9:17and
9:18for all
9:21attribute for all dependencies that
9:23belong to the closure of the functional
9:25dependencies this following conditions
9:28must hold
9:30either alpha determines beta is trivial
9:32which is a condition which b c n f at
9:35or alpha is a super key of r which is
9:38also a condition that be c n f hat
9:40or
9:42each attribute in beta minus alpha
9:46that is right hand side difference the
9:48left hand side is contained in a
9:50candidate key for r
9:53its not very obvious as to why we need
9:56that that will unfold slowly this is the
9:58condition we did not have in bcnf
10:01so naturally you can see that based on
10:03the first two condition you can always
10:05say
10:06that if a relational schema is in bcnf
10:09it necessarily is in three n f but not
10:12the review
10:13there could be some schema which is in
10:15three n f because of the third condition
10:18where there exist a functional
10:19dependency so that beta minus alpha
10:22is contained in a candidate key for r
10:25but it is not in the bcnf form
10:28and
10:30also you can you can
10:32ah
10:34note that the attributes of
10:37ah
10:38that are contained in beta minus alpha
10:41must be in some candidate key not
10:43necessarily in the same candidate key if
10:46they exist in some candidate key then
10:48itself the
10:49ah three nf condition will get satisfied
10:53so if a relation is in bcnf it is in
10:55three nf we have already seen that
10:59so third condition minimally relaxes
11:01bcnf to ensure
11:03that we have a dependency preservation
11:06we will see this more later so i am just
11:07introducing the concept of a relaxed
11:11normal form here
11:13so what is the goal of this
11:14normalization
11:16is if ah to
11:18summarize let r be a relational scheme f
11:21is a set of functional dependencies
11:23we need to decide whether the relational
11:26scheme r
11:27is in a good form
11:30which means that
11:32it is it should not have unnecessary
11:35redundancy it should be possible to
11:39acquire information by doing lossless
11:42join
11:43so
11:44in case it is not in good form we can
11:47convert it by decomposition into n
11:50relational schema such that each schema
11:52is in good form
11:54the decomposition has a lossless join so
11:56that i can get back the original
11:58relation from this
12:00and preferably the decomposition should
12:03preserve
12:04the dependencies
12:05so that is what we will target
12:08henceforth so when we do that let us
12:11quickly evaluate as to ah we have seen b
12:14c n f so how good really ah b c n f is
12:19ah
12:21so
12:22if i have something in bcnf i am should
12:24i really be very happy always
12:27so let us look at a relational schema
12:29this is
12:30an
12:31information relating the id of a person
12:34the name of the child and the phone
12:36number
12:37and
12:39naturally the person the instructor may
12:41have more than one phone and may have
12:43multiple children so this is a possible
12:46instance
12:47as you can see though
12:48all of these belong to the same
12:50instructor he has naturally you can see
12:52that two children and there are ah this
12:55is here this is here so
12:58ah this is here this is here so there
13:00are
13:00two different phone numbers so naturally
13:02you have four possible combinations that
13:04you need to look at
13:07so
13:10now there is no non trivial functional
13:12dependency in this relation
13:15so since there is no non trivial
13:17functional dependency this relation
13:18naturally is in bc enough
13:20because that is the existence of non
13:23trivial dependencies what makes a schema
13:27not
13:28conform to the bcnf form so there is no
13:30such
13:32so this is in bcnf form
13:35and
13:36now if you look at
13:38and
13:39but what did we see the key thing that
13:41we saw if we just go back the key thing
13:44that we saw that is
13:45ample
13:46redundancy of data the same data is
13:48entered multiple times so the
13:51consequence of that could be insertion
13:53anomaly if we want to add a phone number
13:56to the same
13:57instructor then we need to add two tuple
14:01because the instructor also has two
14:04children if the instructor three
14:06children will need to add three
14:08and unless this is maintained always
14:10then will have difficulty so the
14:12redundancy consequences anomaly that we
14:15are getting into
14:17so it could be better to decompose this
14:20to say that i i make this orthogonal i
14:23keep the child information with the id
14:26and i keep the phone number information
14:28the id separately so if i
14:31do that then i can decompose it in this
14:33manner and if i decompose that this i
14:36have just shown that if you are dividing
14:39that table in two parts so naturally
14:41these are not required
14:43ah
14:45neither are these required so these are
14:47the entries that i get and you can
14:50convince yourself that you can actually
14:52do a lossless joint to get back the
14:53information so bcnf not not necessarily
14:57give you good designs and
14:59we will see later on that there are
15:01other normal forms which can be used to
15:03improve on the bcnf
15:07now
15:09let us for for formally getting into how
15:12do we
15:13convert decomposer relation into third
15:15normal form and how do we assess that we
15:17need to understand more of the
15:19functional dependencies
15:21so we will consider now a little bit of
15:24formal theory on them and then develop
15:26algorithms that can generate lossless
15:29joint decomposition into bcnf and 3nf
15:33and we will
15:35also create algorithm to test
15:37if
15:38decomposition preserves the dependency
15:42so
15:43just quickly to recap we have already
15:45introduced a closer set of a functional
15:47dependencies it is all dependencies that
15:49are logically implied by it now the
15:51question certainly is how do i given a
15:53set how do i
15:55compute this closure set
15:58so to do this we
16:00make use of
16:02three rules
16:03known by armstrong's axiom named after
16:06the person who first observed them
16:08so the first rule is reflexivity which
16:11says that
16:12if beta is a subset of alpha
16:15then alpha determines beta always alpha
16:18functionally determines beta
16:21so this is basically reflexivity you can
16:23see is a different way of saying
16:26ah specifying about trivial dependencies
16:29next comes the important thing
16:31augmentation which says that if alpha
16:33determines beta then
16:35gamma alpha where gamma is some set of
16:38attributes in r then gamma alpha will
16:40functionally determine gamma beta
16:43which is very easy to see because alpha
16:45determines beta means two tuples who
16:48match on alpha will necessarily match on
16:49beta
16:51now if that happens then whatever is
16:52gamma if two triples match on gamma and
16:55alpha
16:56then certainly they will match on gamma
16:57and beta
16:59because alpha determines beta tells me
17:01that they will match on beta and gamma
17:02is the same set of attributes so
17:04augmentation also is easy
17:07then we have transitivity which we
17:09earlier saw also if alpha determines
17:11beta and beta determines gamma then
17:13obviously alpha determines gamma so
17:15these are the foundational rules
17:17observed
17:18which can be made use to compute the
17:21closure of the set of functional
17:23dependencies
17:24now these rules as i say this is more
17:27for
17:28you know
17:29understanding the theory better is these
17:31rules are sound as well as complete
17:34soundness mean that
17:36if i use this rules repeatedly in a set
17:39of dependencies then it generates
17:42functional dependencies all of which
17:44actually hold so it will never generate
17:46a functional dependency which is not
17:48correct which will not hold
17:50and the second it is complete
17:52which means that if i keep on using
17:55these
17:56rules then all functional dependencies
17:59that can at all hold will eventually get
18:02generated so that is a very strong
18:04result and that is what leads to
18:06ah the
18:08say the following example
18:10so where we are trying to compute the
18:13functional
18:14the closure of the function set of
18:16functional dependencies here so there
18:18are 6 attributes in the set
18:20there are 6 different
18:22functional dependencies
18:24and
18:26we
18:27identify some members of the closure for
18:29example ah we can see that ah a
18:32functionally determines b and b
18:34functionally determines h so
18:36transitivity clearly
18:39show that a will function determine h
18:42very clear so
18:43in the closure that must be there
18:45similarly ah i we can see that ah
18:51a functionally determines c
18:54now if we augment it
18:57with g
18:59if we augment it with g that is put g on
19:01both sides then
19:02a g functionally determine c g
19:05and we know that ah c g functionally
19:08determines i
19:09so if we combine these two
19:12by transitivity then we can get a new
19:15functional dependency which says a z
19:18function determines i
19:20so in this manner you can do the next
19:23one also and you can try to infer
19:25several other functional dependencies
19:27that can be inferred by different
19:31applications of the armstrong's axioms
19:33the three rules in any multiple
19:35different ways
19:38so to get the closure what we need to do
19:40is now very simple
19:42is certainly we will have a repetitive
19:45algorithm to get the closure
19:47the first
19:48the algorithm will start with
19:50the set of functional dependencies that
19:53we have
19:54so the closure must include the given
19:56set of functional dependencies so f plus
19:58must have f so let us start with
20:00initial value of f plus as f
20:03then for every functional dependency is
20:05f plus this is what we keep on repeating
20:07look at the outer loop
20:08every functional dependency that we have
20:10f plus now we will apply reflexivity and
20:13augmentation
20:15and add the resulting functional
20:17dependency in f plus
20:19it is possible that the same functional
20:21dependency gets
20:22generated and added multiple times does
20:24not matter if plus is a set it will
20:27naturally eliminate duplicates
20:30then for each pair of functional
20:32dependencies because
20:34reflexivity and augmentation applies to
20:37one functional dependency only but
20:39transitivity applies to two functional
20:41dependencies so for every pair of
20:43functional dependencies we check whether
20:45they can be combined by transitivity if
20:47they do
20:48then the transitive closure of that the
20:50transitive ah
20:53functional dependency that arise out of
20:55that is also added to f plus
20:58and mind you the more and more
21:00functional dependencies you add
21:02there are more and more opportunities to
21:04apply the armstrong's axiom rules and
21:07newer newer functional dependencies will
21:09continue to get added but eventually you
21:12reach a point where f plus does not
21:15change any further
21:16and when we when
21:18that is achieved we know that the
21:20functional
21:22the closure of the functional
21:23dependencies have been obtained and that
21:25is our final set
21:33we can also observe that ah based on the
21:37rules of ah armstrong the armstrong's
21:40axioms we can also generate lot of
21:43derived rules some of those are shown
21:46here
21:47for example if
21:48a determines if alpha determines beta if
21:51alpha determines beta holds
21:53and if alpha determines gamma that also
21:56holds then alpha determines beta and
21:58gamma together this is called the union
22:00set so if there are two functional
22:02dependencies which are the same
22:04left hand side
22:06set of attributes
22:08then we can take the union of their
22:10right hand side attributes and that
22:12functional dependency will hold
22:14obviously its trivial to prove this
22:18if alpha determines beta gamma then
22:21alpha determines beta holds and alpha
22:24determines gamma holes this is called
22:26decomposition so kind of the other side
22:29of the union which also is trivial
22:30because alpha data means beta gamma says
22:32if two tuples match on alpha they match
22:34on beta as well as gamma attributes so
22:38obviously you take the first part you
22:39get alpha determines beta you take the
22:41second part of the observation you get
22:43alpha determines gamma so that is a
22:45composition rule
22:47the third is interesting its called the
22:49pseudo transitivity which says that
22:51alpha determines beta
22:55if that holds and gamma beta determines
22:58delta if that holds then alpha gamma
23:00will determine delta which is not
23:03difficult to ah
23:04to
23:05get because if this holds then i can
23:09augment gamma on both sides i get beta
23:13gamma
23:14and
23:15then i have given
23:17ah
23:18beta gamma determines delta so if i
23:21combine these two
23:23in terms of transitivity i get
23:27alpha gamma determining delta so this is
23:29called pseudo transitivity because here
23:32you are adding another attribute in the
23:34transitivity so often times it becomes
23:36easier to make use of these additional
23:39rules to quickly get to the closer set
23:44so
23:45given a set of attributes we also
23:47compute
23:49the closure of a set of attributes
23:51this is the second
23:52concept we have
23:54seen how to given the set of functional
23:56dependencies how to compute the closure
23:58of the functional dependencies
24:01now we are given a set of attributes and
24:04we want to define the closure
24:06of the set of function of this set of
24:08attributes under the set of functional
24:11dependencies
24:13and as
24:14the closure of functional dependencies f
24:17is denoted by f plus
24:20the closure of a set of attributes alpha
24:22under f
24:24is denoted by alpha plus
24:27so
24:28this
24:29set of
24:31closure attributes of alpha
24:34is a set of attributes
24:36that are functionally determined by
24:38alpha under f
24:41so all set of attributes
24:44that are functionally determined by
24:47alpha under the set of functional
24:49dependencies
24:51is member of alpha plus
24:55so the following sample
24:57algorithm can compute the closure
25:00naturally initially let us say the
25:02result is the final closure set so
25:05initially we can say that result can be
25:07initialized with alpha because certainly
25:09the whole of alpha would necessarily
25:12belong to alpha plus by the
25:14reflexivity condition
25:17then for each functional dependency
25:21beta determining gamma
25:23we check if beta is a subset of the
25:26result
25:27if beta is a subset of the current
25:30set of attributes that form result
25:32which mean that
25:35alpha
25:36functionally determines beta
25:39it will have to because
25:40result is the set of all attributes that
25:43alpha functionality determines
25:45so if beta is a subset of the result
25:48then necessarily alpha functionally
25:49determines beta alpha functional
25:51determines beta is
25:53is a consequence of this
25:56and we know that this is there beta
25:58functional determines gamma
26:00so combined by transitivity so i know
26:03alpha functionality determines gamma
26:05if function alpha functionally
26:06determines gamma then it must get into
26:08the result and this is exactly what
26:10the statement is saying that take result
26:12and
26:13add alpha ah add gamma the set of
26:16attributes gamma to the result
26:18and how long should you do that
26:20naturally you will do that as long as
26:24over a full iteration of
26:27functional dependencies in f if there is
26:30no change to the result then you know
26:31that all future iterations will have no
26:33change so you reach a fixed point and
26:35you declare that the closure of the set
26:38of attributes have been obtained
26:41now this this closure information is is
26:44very
26:45interesting and we just show
26:47a
26:48an example
26:50here based on the same set of attributes
26:52and same set of functional dependencies
26:54so we are trying to find the closure of
26:56the set of attributes a g so a g plus
26:59initially it will be a g
27:01now
27:02ah since a functionally determines c so
27:06given that
27:08i can say that
27:10c will get included in this set
27:13in the same iteration if i look at a
27:15function determines b
27:17so b will get included this set
27:20so after this ah
27:23first
27:24iterative loop
27:26i will have the result as a b c g
27:29if a b c g is there and i am looking at
27:32the next iteration then c g functionally
27:35determines h so h comes into the set
27:40because c g is is a subset of that
27:43the i comes into the set
27:45because c g functionally term inside
27:49and at this point it ah eventually ends
27:52in this case
27:53in this particular example
27:56you you can see that all attributes have
27:59got included so you can see that it
28:01immediately gives you an another
28:03information as a byproduct of the
28:05closure
28:06that
28:06closure of a g is all attributes which
28:09mean that a g is a
28:10key
28:12it has to be a key because a g
28:13functional determines all attributes now
28:15so what is the meaning of a g plus being
28:18this so if the meaning of this is a g
28:20functionally determines the set of
28:22attribute a b c g h i
28:25right
28:27so we will see that this closure set
28:32has a lot of
28:34valuable information in this so
28:37we can say that a g is a candidate key
28:39and
28:40because this of this
28:43and we can also check whether a g is a
28:45super key or not all that we need to do
28:47is drop
28:48some member from a g we drop g
28:51and check whether a function determines
28:53r which means we check whether
28:56a plus is equal to r or not
28:59we check we drop
29:01a from a g
29:03and check whether g function determines
29:05r which means g plus has to be equal to
29:08r and by that we can easily determine
29:11whether the
29:12ah set of attributes is a key or not
29:16so there are several ways the
29:18attribute closure can be used as we have
29:21just seen
29:22it helps you determine whether something
29:24is a super key we can check for ah
29:28testing functional dependencies because
29:31if we have to check whether a functional
29:32dependency alpha determines beta hold
29:35all that will have to do is to compute
29:38the closure of the set of attributes
29:41alpha that is alpha plus and check
29:43whether beta is a subset of that if it
29:44is then certainly it holds if it is not
29:47then it does not hold
29:50so it is simple and useful test that can
29:53be made use of
29:54so it can also be used in computing the
29:58closure of f
29:59that the for example for every
30:01subset
30:02gamma of r if we find gamma plus that is
30:06a closure of the set of attributes of
30:08gamma
30:09and for then for each
30:12subset of gamma plus we know that there
30:14is a functional dependency gamma
30:17determining s which is just is a same
30:20statement being made in in you know in
30:22different forms and
30:24the closure of attributes is a very nice
30:26concept which
30:28help you play around with this multiple
30:30ways and we will see subsequently many
30:32of the algorithms for normalization how
30:34they make effective use of this closure
30:37set the
30:39notion of both closure of
30:42functional dependencies and in very
30:44practical implementation algorithms the
30:46closure of
30:48attributes
30:49so to summarize this module we have
30:51discussed
30:53issues further issues in the good design
30:55in the context of functional
30:57dependencies and
30:58in the process we have also extended the
31:01theory of functional dependencies and
31:03will continue with this in the next
31:05module to give get more insight into the
31:09algorithms that actually work with the
31:11functional dependencies

About this transcript

This page contains the full transcript of Relational Database Design (Contd.)-1 by Data Base Management System - IITKGP, generated from the public captions YouTube serves with the video. The transcript has 4,407 words across 817 segments, with the original timestamps preserved so you can click any line to jump to that moment in the embedded player.

What you can do with it

Use the transcript to take notes, quote the speaker, build a study guide, generate a summary with ChatGPT or Claude via the YouTube Summary tool, or export it as a timed subtitle file with YouTube to SRT. You can also re-open it in the transcriber to translate the transcript into 100+ languages.

Free YouTube transcript tool

YouTube2Text is a free YouTube transcript generator — no signup, no daily limit. Paste any YouTube link and get the full transcript instantly, with timestamps, click-to-jump, translation to 100+ languages, AI prompts for ChatGPT, Claude, and Gemini, and exports to TXT, SRT, VTT, or Markdown.