YT YouTube2Text

YouTube2Text → Transcripts → Relational Database Design/1

Relational Database Design/1 — Transcript

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

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:00[Music]
0:15welcome to
0:16module 16 of database management systems
0:21till ah the last module which closed
0:24with
0:25the third week
0:27ah specifically in the third week we
0:30talked about
0:31certain advanced features of sql
0:34and
0:35the formal query language
0:39ah in terms of relational and algebra
0:42and calculi
0:43then we talked in at depth in terms of
0:47the entity relationship model
0:49the first basic conceptual level
0:52representation of the real world that we
0:55can do in terms of designing a system
0:58now our next task would be to
1:01take it to a more proper complete
1:05relational database design
1:07and
1:08this will have a lot of
1:11theory at different levels that we need
1:14to understand will slowly develop that
1:16and this discussion will span
1:18five modules
1:20that is ah will take the whole week to
1:23complete
1:25so the objective of the current module
1:28the first of the relational design
1:31module is to identify features of good
1:33relational design
1:35ah having done the year model we
1:38have here we do the year model we have
1:40the entity sets relationships we convert
1:42them to schema we have seen how to do
1:44that and immediately we have some design
1:47but the question is is it a good design
1:49so we will discuss about what are the
1:51features of a good design and then we
1:54will introduce the formal definition of
1:57what is first normal form and we will
2:00introduce a very critical concept of
2:03relational database design the
2:05functional dependencies
2:07these are the
2:08ah module outline for that
2:10so to start with the features of good
2:13relational design let us take an example
2:15suppose
2:16ah we have seen
2:18the instructor relation
2:20ah instructor entity set as a relation
2:22you have seen the department relation
2:24now let us consider that if these two
2:27were not two separate relations if they
2:29were
2:30all kept in a common relation that is
2:32all the attributes are kept in the
2:33common relation so earlier if you recall
2:37that your instructor relation was this
2:39and your department relation was this
2:41much so if we keep everything together
2:44of course ah
2:45we are calling it in depth but
2:47please keep in mind this is not the same
2:50in step that we discussed in terms of
2:52the er model this is just putting these
2:54two together
2:56now the question is if you look into
2:57this data carefully for example if you
2:59look into ah this particular row if you
3:02look into this particular row and if you
3:05look into this particular row
3:07these are rows of instructors who all
3:10belong to computer science
3:14now earlier
3:16we were representing the information of
3:18instructor only in this part
3:21so we just knew that it is computer
3:23science and we represent the information
3:26of department in this part
3:29so given a department name say computer
3:31science we knew where does it
3:34ah
3:35where is it located the building and
3:37what budget it has
3:38now when we are combined we will see
3:40that naturally since computer science is
3:43located in the taylor building we know
3:45and it has a budget of say hundred
3:47thousand so all of these records will
3:49have
3:50this information repeated
3:52so this is not a very good situation
3:55this is not a good situation because
3:57this
3:59kind of situation is typically in in
4:02database
4:03is known as redundancy that is you have
4:06the same data in multiple places
4:10so what is the consequence of redundancy
4:12for example there could be ah different
4:15kinds of anomaly when you have
4:17redundancy what is an anomaly and
4:20anomaly is
4:22the possibility of certain data getting
4:25inconsistent for example lets say
4:27computer science department moves from
4:29taylor building to painter building
4:32now what will have to happen if it moves
4:34to painter building then i will need to
4:36remove this make it a painter
4:38make this value painter
4:40i have to also do this make this painter
4:44i have to also do this make this painter
4:48so
4:49if i have
4:50a change
4:52then i will have to make the change at
4:54multiple entries think about the earlier
4:57situation where we i just had these
4:59three
5:01in my department relation then naturally
5:04computer science had only one row and
5:06therefore ah
5:08this change this update could be done at
5:12only one place so it is not only that it
5:14while doing this in case of this
5:17redundancy i have to do this multiple
5:19times it also has the
5:21difficulty that if i forget to update
5:24any one of them or more of them then i
5:26have inconsistent data
5:28similarly if i if i want to
5:31insert a new value
5:32i will have to
5:34do that for all this redundant
5:36information if i have to delete
5:39say ah
5:40for some reason let us say the
5:42university decides to wind up the
5:44physics department then i have to delete
5:47all this
5:48rows which have physics as an entry and
5:51the consequence of that is the
5:53department is deleted but as a
5:55consequence of that i will delete the
5:56whole
5:57row and therefore i will not only remove
6:00the department but i will also remove
6:03the corresponding instructor who was
6:05enrolled for that department
6:07so
6:08this kind of
6:11redundancy can lead to
6:14different kinds of anomalies in a
6:16database design
6:18on the other hand if you look at ok well
6:20why am i complicating ah the whole
6:22situation we already had a good design
6:25ah in terms of where these animals were
6:27not there department was separate
6:29instructor was separate
6:31in that case the
6:35situation is that to answer some of the
6:37queries i may have to do a very
6:40expensive join operation for example if
6:42i want to know
6:43if ah
6:45einstein wants to know what is the
6:47budget of
6:49his department that cannot be found out
6:52from the earlier instructor database
6:54instructor relation which had only these
6:56fields
6:58so i have to pick up
7:00einstein from here do a join based on
7:03the department name
7:05depth name with the department
7:07ah table
7:09department relation and then only i will
7:11be able to find out that einstein
7:13belongs to physics physics has a
7:16budget of seventy thousand so einstein's
7:19department has a budget seventy thousand
7:22so there is a trade-off between how much
7:24data information you make redundant
7:28and lead to different anomalous
7:31situations and or how much data you
7:33optimize in the representation but
7:38get into the possible situation of
7:40having a higher cost in terms of
7:42answering your queries
7:44so this is ah one of the core design
7:47issues that we will start with
7:49so
7:51ah let us look into some more of these
7:54examples
7:55lets say we look into another ah combine
7:58combination of schema suppose
8:00section is a relation which have
8:03the sections of a course which give the
8:05section id semester year
8:08and say section class is another
8:11relation which tell me for a section id
8:13what is the building and room number
8:15where it is
8:17located so if we have this
8:20kind of
8:22relations combined
8:24into a common relation
8:27then i have all of these
8:30coming from the section
8:32and
8:33this and these coming from the section
8:36class
8:37but we can see that there is no
8:40repetition or
8:41ah redundant information in this case so
8:44it is not that that combining schemas is
8:48necessarily always bad in terms of
8:50repetition or in terms of redundancy so
8:53different situations will have to be
8:54assessed
8:56so
8:59if we want to look at the other side
9:00that if we if we just
9:03as i said that if we make the schema
9:05smaller so that we avoid redundancy
9:09and then what we see that well um
9:13from the combined
9:14ins depth
9:17relationship that we saw so if let me
9:20just ah
9:21show you once more so this is if we look
9:23at the ins depth
9:25then
9:26in this
9:27we can
9:29we know that
9:31from the earlier
9:33information about the department
9:34relationship that
9:36department name
9:38is a
9:39key is a primary key
9:41of
9:42the relation which has department
9:46name building and budget
9:49what is the consequence of being a
9:50primary key if it is a primary key then
9:53no two records can match on the
9:55department name
9:59and be different in terms of the
10:01building and the budget if two records
10:03are there which have the same department
10:05name they must have they must be
10:06identical so they are distinguishable
10:08completely by that
10:10so let us see what is the consequence of
10:12this
10:13and
10:14so we are saying that we write it as a
10:16rule that if there is a schema
10:18department name building budget then
10:20department name would be a candidate key
10:23and we
10:24write this observation that if
10:28two records match on the department name
10:30they must match on the building and
10:32budget
10:33and very loosely will come to the formal
10:35definition very loosely we call this the
10:38functional dependency we say that the
10:41building and budget is functionally
10:43dependent on the department name
10:45and that is a situation
10:47that is a situation where
10:50we can
10:52split
10:53this inch depth
10:55and
10:56create a smaller
10:58relationship because department name is
11:01not a candidate key
11:03in the ins depth department it does not
11:07decide the
11:09records of instep uniquely
11:11so
11:12it is ah since it does not so it when
11:16the values of this
11:18key
11:20this
11:21attribute department name is
11:24duplicated or triplicated the values of
11:27the building and budget are repeated and
11:30we have the redundancy
11:32so
11:33this is a situation very common
11:34situation which is indicative of the
11:37fact that we needed decomposition into
11:41smaller
11:43but ah at the same time
11:45we can also observe i mean let us take a
11:47different different example if we are
11:49thinking that decomposition is the
11:51panacea of
11:52ah solving this kind of redundancy and
11:56related problems then let us
11:59try to see a different relationship
12:01employ
12:02which has id name street city salary and
12:05we want to make it smaller
12:08and and want to make two relations
12:12id and name and name cities
12:15street salary so if we do that
12:19then how do we get the
12:22say salary for a particular id
12:25will naturally have to join these two
12:28naturally join these two ah these two
12:31relations
12:32in terms of the common attribute name we
12:34have seen that in the query
12:36now the question is when i do this join
12:38do i get back the
12:40original information or i gave i lose
12:42some information look at an example so
12:45here is an example of the combined
12:48instance
12:50and i have two different ids but
12:53incidentally
12:54the names are same
12:56incident the names of these two distinct
12:59employees are same
13:00so when i decompose i get this
13:05relation which shows idn name i get this
13:08relation which against the name shows
13:10this
13:11but when i try to join them by natural
13:13join
13:14i not only get the combination of
13:17this with this which is what i need
13:20but i also get this combination
13:23so if i say
13:24this is
13:26what i get
13:28as well in terms of natural join this is
13:30what i get
13:32as well in terms of the natural join
13:34which are really not there
13:37in the original relation so you can see
13:38that
13:39in the natural join i get four
13:42records i get four rows whereas in the
13:44original one i had only two rows so i
13:47get some entries which are actually
13:50erroneous
13:52these are not there in the database
13:54so this is when this happens we say that
13:56we have loss of information and such
13:59joints are said to be
14:01lossy joints so while we decompose we
14:04need to make sure that our joints are
14:06lossless in nature otherwise that is not
14:09a good design
14:11so you can
14:13see this is again a hypothetical example
14:16which shows three
14:18attributes a relation having three
14:21attributes you have decomposed it did
14:22two relations
14:24having two attributes each and we have
14:26shown an instance and in this case it
14:28shows that the
14:30when i take the joint
14:32when i take the joint the original
14:35information
14:36i am sorry wait
14:40when i take the joint
14:42the original information is completely
14:44retrieved i get back the same table and
14:47when that happens i say that the join is
14:50lossless
14:51so what we need to
14:53understand is
14:55ah on one side there is a need to
14:59decompose relations into smaller
15:01relations to reduce redundancy
15:04and while we do that we will also have
15:06to
15:08keep this in mind that the smaller ah
15:11relations have must be composable
15:14through certain natural join procedure
15:17to the original relation and i must get
15:20back that original relation otherwise i
15:22have a lossy joint which is not
15:23acceptable and also the decomposition
15:26will have the costs of
15:29ah doing natural join every time i want
15:31to answer those queries
15:36ah
15:37the next that we look at is
15:41the way the relationships are
15:43categorized as first normal form
15:46ah we consider that
15:48the domains of attributes
15:52are atomic if they are indivisible
15:55so
15:56anything that is a number string and so
15:58on is considered to be atomic
16:01and we say a relational schema is in its
16:03first normal form
16:05if the domains of all attributes are
16:07atomic
16:08and all attributes are single value
16:11there is no multivalued attribute if
16:13these conditions satisfy then we will
16:15say that every rel that relational
16:17schema is in its first normal form
16:20so we will we will slowly understand the
16:22the the purpose of ah defining such
16:25normal forms but let us initially
16:27understand the definition
16:29so
16:29we have ah
16:31if we have
16:33attributes which are composite in nature
16:35naturally my relationship my relational
16:38schema is not in first normal form if we
16:40have attributes which are ah multiple
16:43valued it is not so
16:45so ah if we say that
16:49we have possible values are like this
16:52then if we just treat them as strings
16:54then the corresponding relational schema
16:56is
16:57in first normal form but if we say that
17:00from the string
17:01we can extract the first two characters
17:03which is cs which tells me what is the
17:05department the next four characters
17:07gives me a number the serial number ah
17:10of the of the particular student in the
17:12role
17:14then i am not actually using an atomic
17:18domain ah because my domain needs to be
17:20interpreted separately than just being a
17:23value so these are not parts of what can
17:26be a first normal form
17:28so i have given some examples of ah what
17:32is not and what is first normal form so
17:34this is an example where at the
17:36telephone number
17:37ah field exist and there can be multiple
17:39telephone numbers so this is not in
17:41first normal form because the telephone
17:44number itself is composite because it
17:46has different components and also you
17:48can have multiple telephone numbers so
17:50this is this relation is not in the
17:53first normal form
17:54ah what you can do you can
17:57separate out these phone numbers into
17:59two different attributes telephone
18:00number one and two
18:02even ah then um
18:05it is not exactly in first normal form
18:08because ah
18:09you do not know in which order they
18:11should be handled you if you have to
18:13search for a telephone number then you
18:15have to search multiple attributes which
18:16are conceptually same and then it then
18:19the question is why only two attributes
18:21cannot anybody have three phone numbers
18:23seven phone numbers and so on so this is
18:25really not a good option
18:28so
18:29the other way could be that for every
18:31telephone number you introduce a
18:33separate row once you do that you
18:35already know you have redundancy and you
18:37have possibilities of varied kinds of
18:39anomalies that could happen
18:41so one way it could be achieved is we
18:44follow the principle that we had seen in
18:47the er modeling that
18:50this multivalued dependency can be
18:53represented in terms of a separate
18:55relation where against the customer id
18:58we just keep the telephone numbers we
18:59can keep multiple of them
19:01and we take that out from the customer
19:04name so a one to many relationship
19:07between the parent and the child ah
19:09between the customer name and telephone
19:12number every customer may have more than
19:14one ah telephone number is possible and
19:17that makes it a one n f ah relation one
19:21ah first normal form relation and we
19:24will later on see that it also is ah two
19:27n f and three n f but that is a future
19:29story
19:31now finally we ah come to
19:33the core of
19:35what
19:36the mathematical formulation
19:39which dictates much of the database
19:42relational database design
19:44is known as functional dependencies i
19:46just talked about a little bit of that
19:48while talking about department name
19:51building and budget now i
19:54to decide whether a particular relation
19:56is good
19:58or rather a particular relational scheme
20:00is good
20:02we need to check against certain
20:05measures
20:06and
20:07if it is not good we need to decompose
20:09it into a set of relations such that
20:12these conditions satisfy that every each
20:15one of these
20:16ah r one r two r and so i mean
20:19if you have
20:20ah you know got rusted then its
20:23basically r i is a set of attributes
20:26because its a relational schema the
20:28relational schema is a set of attributes
20:30so
20:31ah and naturally r will be the union of
20:35all of these r i the total set of
20:37attributes so
20:38instead of keeping all the information
20:40into one relation in one table we are
20:43basically decomposing it into n
20:45different
20:46schemas
20:47and
20:48so what we need to guarantee is each one
20:50of these relation r one r two r n is in
20:53good form
20:54and
20:55how do i get back the original relation
20:58original relation that was represented
21:00by all the attributes in r is to take a
21:02lossless join is to take a join and that
21:05this decomposition must give me a
21:07lossless join
21:09so
21:10to ensure that we make use of
21:13two key ideas more foundationally
21:16functional dependencies and then multi
21:18valued dependencies
21:20a functional dependency is a constraint
21:22on the
21:23set of legal relation so
21:26ah mind you it is a constraint on the
21:29schema
21:30and once it that constraint is is
21:32defined
21:33it ah must hold for all relations that
21:37the schema satisfy
21:39so
21:41here we need that the
21:42value of certain set of attributes
21:44uniquely determine the value of another
21:47set of attributes
21:48so i know the value of
21:50three attributes i should be able to
21:52say that values of the other four
21:55attributes would be fixed
21:58so
21:59you can you have already seen this
22:01notion in terms of ah key or super key
22:05ah you have seen that
22:07similar type of concept exist where we
22:10said
22:10a
22:11key is a set of attributes so that if
22:14the values of two rows are identical
22:17over these set of attributes then
22:19the
22:20two tuples the two rows must be totally
22:23identical so key is something which ah
22:26does a similar thing as a functional
22:28dependency but is more specific
22:31functional dependence is a
22:32generalization
22:34so let us formally define that let r be
22:37a relational schema which means that it
22:39is a set of attributes and let us say
22:41alpha and beta are two subsets of r
22:45then we say write this and note this
22:48notation
22:50alpha is a set of attributes
22:53beta is another set of attributes both
22:55are subset of the same r
22:57and we say alpha functionally determines
23:00beta
23:01that is if i know
23:03the
23:04value of a tuple
23:07over the attributes of alpha
23:10then the values
23:11of that tuple over the attributes of
23:14beta would be fixed
23:16or in other words i say that if i have
23:19two tuples t one and t2
23:22and their
23:24values over the set of alpha attributes
23:27are same
23:28then necessarily
23:30the values over the set of beta
23:32attributes must be same
23:34and mind you this is this is something
23:36which is a design constraint
23:38this is it is not just an incidental
23:41property it is not just the fact that a
23:44particular instance of a schema
23:47satisfies this but when you say this is
23:50a functional dependency we need all
23:52possible
23:53past present and future instances of the
23:56schema must satisfy this
23:59so
24:03consider this if you if you take a
24:06relation
24:08a schema with an instance as given here
24:10between two attributes a and b
24:12then we can say at least given this
24:15instance not we still do not know what
24:17happens in the whole schema for all
24:20instances but on this instance we can
24:22say that a functionality determines b
24:24does not hold because between the first
24:27and the second record the value of a is
24:29same one but the value of b are
24:31different four and five
24:32but we can certainly say that on this
24:35instant at least b functionally
24:37determines a holes
24:39because
24:40whenever the value
24:42if we take any two tuples the value over
24:45b does not at all match if that does not
24:48match then naturally there is no
24:49question of what happens to the
24:51value of the tuple over the set of
24:54attributes a so we will say that b
24:57functional determining a
24:59holds in this instance
25:02so given this definition of functional
25:04dependency now we can have a formal
25:06definition of what is a super key a
25:09super key is naturally a
25:12subset of attributes which functionally
25:14determines the whole set
25:17and a candidate key is a super key which
25:20is minimal so which means that
25:23a
25:23k is a candidate key if the two
25:26conditions have to satisfy this
25:27condition say that it is a super key
25:29that it functionally determines all the
25:30attributes
25:31and
25:32the other condition says minimality that
25:35there is no subset alpha of k
25:38such that alpha functionally determines
25:40r if there exists a subset alpha of k
25:43the proper subset alpha of k
25:45so that alpha functionally determines r
25:47then k would not be a candidate key
25:50we will have to check for alpha so these
25:53two what we had stated earlier in
25:55qualitative terms are now mathematically
25:58established
25:59so we can say that the different
26:01functional dependencies for example in
26:04the instep
26:06combined relationship relation if we
26:08look at then we know that department
26:10name functionally determines building
26:13id
26:14functionally determines building but
26:19so these are functional dependencies
26:20that must hold but certainly you would
26:22not expect ah department name to
26:24functionally determine saturday that
26:26would be too much right so
26:28ah functional dependencies are facts
26:31about the real world that we try to
26:34understand from the real world and then
26:36represent in terms of ah the functional
26:39dependency formulation in the database
26:43so
26:46we can use functional dependencies to
26:48test relations if they are
26:50valid under the set of functional
26:52dependencies so there could be multiple
26:54functional dependencies in the set
26:56and if a relation
27:00we are using small r here just to remind
27:02you that a relation means that a
27:04particular instance
27:05is legal under a set of functional
27:07dependencies we will say that r
27:09satisfies that
27:12and
27:13if we specify if we have that
27:17it holds
27:19f
27:20will be satisfied by all possible
27:23instances of a relational schema capital
27:26r then you say f holds on r
27:29so a relation satisfies a functional
27:31set of functional dependencies and a
27:36relational schema for a relational
27:38schema the functional depend set of
27:40functional dependencies holds on that
27:41schema which means that for all possible
27:44past present and future
27:46instances relations that
27:49the relations will satisfy the
27:51functional dependencies
27:58so we have ah
28:00for example id we know id functionally
28:03determines name that if the id is
28:05distinct then the name has to be
28:07distinct
28:08but
28:08we may find that instance where name
28:10functionally determines id so we can say
28:13that it names functionality determines
28:16id is satisfied by a particular instance
28:18where it so happens that there is no two
28:22ah rows where the name is identical
28:25but
28:27we cannot
28:28may not be able to infer that
28:30as the this dependency holding on the
28:33relational scheme as a whole because
28:36tomorrow we can get another entry
28:38so that ah the two rows might match on
28:42the name but could still be distinct
28:44entries not matching on i d
28:46so that is how this will ah have to be
28:48looked at
28:49ah in specificity we say that a
28:52functional dependency is trivial if the
28:55left hand side
28:57is a super set of the right hand side so
29:01if i have a bigger set of attributes on
29:03the left hand side id and name then
29:06obviously id and name will functionally
29:07determine id
29:09idn name will functionally determine
29:11name
29:12name will functionally determine name so
29:14if you just think about because in a
29:16functional dependency the left hand side
29:18attributes the tuples have to match on
29:20the left hand side attribute and if they
29:22do then they must match on the right
29:24hand side attribute so if the right hand
29:25side set of attributes is a subset of
29:28the left hand side then obviously the
29:30functional dependency will be vacuously
29:32true and these are called trivial
29:33dependencies
29:35so in the next couple of slides i have
29:37shown a few examples of functional
29:39dependencies of different different
29:41tables here student id functionally
29:44determines semesters which mean that we
29:46are trying to model
29:47that a student
29:50cannot be at the same time in two
29:52semesters
29:53ah then student id and lecture together
29:56functionally determines who is the ta
29:57and so on and you can see for this ah
30:00particular relation student id and
30:02lecture pair also happens to be the
30:04candidate key
30:06ah these are another example so these
30:09are just go through them try to convince
30:11yourself that these functional
30:13dependencies
30:14are
30:15ah very genuinely real world situations
30:17that can be modeled in this way
30:20given a set of functional dependencies
30:22we can actually compute a closure for
30:25example if a functionally determines b
30:28and b functionally determines c
30:30then we can infer that a functionally
30:32determined because if two tuples match
30:34on a
30:35a determines b says that they match on b
30:38now if
30:39b functionally determine c also holds
30:42then if they match on b they match on c
30:44so if they match on a then necessarily
30:47they may have to match on c
30:49so this is called the logical
30:51implication of a
30:53set of functional dependencies and
30:56we will see more of this
30:58later but
30:59if we take all functional dependencies
31:03of a given set f that are logically
31:06implied from this set f we say that is a
31:09closure set
31:10and we represent that by f plus
31:14so f plus necessary is a super set of f
31:17so here in that above example this is
31:20the f and this is a f plus
31:23so will continue more on the theory of
31:25functional dependencies but
31:27let us conclude this module by
31:28summarizing that we have identified the
31:31features of good relational designs
31:34trade-off between decomposition and
31:38lossless
31:39join properties that we need we are
31:41familiarized with the first normal form
31:43and atomic domains and we have
31:45introduced the notion of functional
31:47dependencies on which we will build up
31:49more and try to get
31:52zero in on very concrete strategies for
31:55good designs

About this transcript

This page contains the full transcript of Relational Database Design/1 by Data Base Management System - IITKGP, generated from the public captions YouTube serves with the video. The transcript has 4,571 words across 837 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.