YT YouTube2Text

YouTube2Text → Transcripts → Formal Relational Query Languages

Formal Relational Query Languages — Transcript

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

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:00[Music]
0:17welcome to module 12
0:19of database management systems
0:23in this module
0:25we will
0:26talk about
0:28the formal
0:29relational query languages
0:33in the last couple of modules we have
0:36discussed about
0:37sql at length
0:39introducing it
0:41dealing with the intermediate level of
0:43sql
0:45features and then
0:47exposing to
0:49some of the advanced features as well
0:53the foundational mathematical model
0:56of
0:57sql the query languages
0:59are to be discussed in this
1:02present
1:03module
1:05so this is what
1:07we had done in the last module
1:10in the current one we will work to
1:13understand the formal query languages
1:16primarily through relational algebra
1:19and then we will also take
1:22a look into some of the calculus
1:25aspects
1:27tuple relational calculus and domain
1:29relational calculus
1:31and we will
1:33show by example the equivalence between
1:37the algebra and the two calculus
1:42so
1:43formal relational query languages
1:46are of three types one is known as
1:50relational algebra
1:52this is procedural in nature
1:56so we specify
1:58what operations need to be done to
2:01achieve the result
2:04and the whole formulation is based on
2:07set algebra
2:10the second
2:11formal
2:13query language is tuple relational
2:15calculus
2:17which is non-procedural and is based on
2:19predicate calculus
2:22the third one the domain relational
2:24calculus is a
2:26minor variant of the tuple relational
2:28calculus is and is also non procedural
2:31and
2:32predicate calculus based
2:35so we will start with the relational
2:37algebra
2:41in the relational algebra
2:43it was created by
2:46edgar f cord
2:48at ibm in nineteen
2:50seventies
2:52so you can see that it is ah quite an
2:54old formulation
2:56it is a procedural language
2:58it has six operators we have taken
3:02a quick view of these earlier in this
3:04module we will look at them at length
3:07the select project union
3:10set difference cartesian product and
3:13rename
3:14we will also look at few derived
3:16operations like
3:18intersection and division which can be
3:21expressed in terms of these basic
3:23operators
3:24and
3:26each one of these operators can take one
3:28or two relations
3:30as input and they produce one relation
3:33as a result
3:36so we start with the select operation
3:38which
3:39you know has a notation sigma
3:42subscript p is a predicate
3:44it is called the selection predicate and
3:46within parenthesis we have a relation r
3:49on which this predicate applies
3:53so it is defined as
3:58a set where
4:01you collect
4:03all the tuples all the rows
4:06designated by t
4:08and
4:09you specify that t belongs to the
4:11relation
4:12so it already exist in that relation
4:16and
4:17it satisfies
4:19the particular selection predicate
4:21so
4:22any tuple that satisfies this predicate
4:25is included in the result
4:27any that does not satisfy is excluded
4:30from the result
4:32p here particularly is a propositional
4:35calculus formula
4:38or expression
4:40where we have different terms that are
4:43connected by conjunction or and
4:47disjunction or or
4:49or negation
4:51or not
4:53and each term by itself could be
4:56something like this it is an attribute
4:58operate an attribute where operators are
5:01different comparison operators one of
5:03the any sex
5:06or a term could be an attribute operator
5:09a constant
5:11so
5:12given that we can write any expression
5:17which is a predicate
5:19and applying that we can select
5:22the tuples from the relation r which
5:26satisfy this predicate
5:33so here we show a simple example
5:37instructor is a relation
5:40department name
5:41is an attribute
5:43within course physics is a constant or
5:46literal
5:47so this selection show
5:50will select all the tuples where the
5:53attribute department name is equal to
5:55physics and all the others will be
5:57eliminated
5:59for reference
6:00i have also
6:02quoted here
6:03the example that we had
6:05shown at the time of
6:07introducing relational algebra so you
6:10can see that here
6:11we have a more
6:13complex propositional term ah
6:16propositional formula where there are
6:18two terms
6:19the a should equal b
6:21and d should be greater than five
6:24so in the selection result both of these
6:28conditions must be satisfied by all the
6:30tuples which feature here
6:33so this is the first
6:35operation that relational algebra has
6:38the select operation
6:41next we move on to the second operation
6:43which is a project operation where
6:46a relation can be projected in terms of
6:50a number of attributes
6:52so pi is the notation
6:54r again is the relation and the
6:56subscripted a 1 a 2 a k
6:59are k attribute names k has to be at
7:02least one
7:03and these attributes will be retained in
7:07the relation
7:09so the result is defined as the relation
7:11of k columns
7:13by erasing all the columns of r which
7:17are not listed amongst this a to k
7:20naturally if you erase some columns it
7:23is possible that two rows
7:25that were distinct
7:27in those columns
7:29but are identical
7:32in a one to a k
7:35feature in the relation
7:37since every relation is a set
7:40no distinct
7:41no
7:43two copies of the same tuple are allowed
7:46so the duplicate rows will be removed
7:49from the result
7:51reminder this is in contrast to what sql
7:54does by default
7:56where duplicates or multi sets are
7:59allowed by default here we are talking
8:01about the formal relational algebra
8:04where it is purely set theoretic so
8:07duplicate rules on projection will be
8:10removed from the result
8:12so we have an example from the
8:14instructor relation we had seen earlier
8:16we are projecting id
8:18name and salary
8:20so we are removing the department name
8:23which also exists in the same relation
8:27and as a reference you can
8:30see
8:30the example that we had seen earlier
8:33while introducing
8:34the
8:35relational algebra where projection is
8:38done from three columns a b c
8:41into two columns a and c and this
8:43results in at least
8:45results in two rows which are identical
8:48and therefore
8:49in the final result
8:51one of those
8:52the duplicate one is removed
8:57moving on the third operation is
9:00quite simple it is set theoretic union
9:03so r union s where r and s are two
9:06relations are set of tuples which either
9:09belong to r
9:10or belongs to s or belongs to both
9:15the condition is you can take union if
9:17both these relations have the same arity
9:20and the order of the attributes must
9:24satisfy that
9:25every corresponding attribute
9:28must have compatible domains so if i
9:31talk about the second column of r
9:34and if we talk about the second column
9:36of s they must be of the same type and
9:40this must hold for all columns that the
9:43union
9:45forms that is all columns of r as well
9:48as s
9:49otherwise
9:50this operation is not defined
9:53so as an example we show that to find
9:56all courses taught in fall 2009
10:01semester this is a
10:04this is a query where we do a
10:08selection
10:10to find all tuples which are
10:12taught
10:13which represent
10:15courses taught in
10:17fall 2009 semester from the section
10:19relation
10:20we do a projection to get the ideas of
10:22those courses only
10:24and the second row
10:27tells you the courses that are taught in
10:30the spring 2010 semester
10:32and we do a union to get courses that
10:35are taught either in fall 2009 semester
10:38or in spring 2010 semester or both
10:43this is how the
10:48union is performed and this is the
10:51earlier example repeated here
10:55set difference is again just simple
10:58difference of sets
11:00r minus s where a tuple belongs to r and
11:04it does not belong to s
11:07so you remove all the tuples belonging
11:10to s that exist in r to get r minus s
11:13again they must have the compatibility
11:16of having the same arity and attribute
11:18corresponding attribute domains must be
11:20compatible
11:22this is an example to show to find all
11:25courses taught in fall two thousand nine
11:28but not in spring two thousand ten so
11:32as opposed to union in the last
11:34slide you do a set difference to get
11:37this result
11:38so this is how you can use set theoretic
11:40operation to
11:42get different relational results this is
11:46also the result from the earlier example
11:50set intersection
11:52can be supported
11:53is supported but it is not a basic
11:56operation
11:57because
11:58as it is defined by
12:00all tuples which belong to both r and s
12:03it can actually be computed by
12:06applying set difference twice
12:09and certainly for set intersection also
12:12the same
12:13assumption about arity and compatibility
12:15of types hold and this is the earlier
12:18example
12:21next is cartesian product where we take
12:23two relations
12:25and
12:27for the cartesian product we make
12:30we juxtapose one relation with the other
12:35so t is a relation from is a tuple from
12:38r
12:40q is a tuple from s and we put them side
12:43by side
12:44to get a
12:46t q
12:47row
12:48in the cartesian product r cross s
12:51which basically mean that you compute
12:55all possible combinations of tuples from
12:58r
12:59and of s
13:02it is assumed that the attributes of r
13:05and s are disjoint
13:07that is the schema of our intersection
13:10schema of s
13:11is null
13:13if the attributes are not disjoint then
13:16we must use renaming which will soon see
13:19and here is an example that we had shown
13:22earlier of r and s computing r crosses
13:27cartesian product is a very useful ah
13:30operation particularly for computing
13:32join as we have seen in sql already
13:37rename operation basically allows you to
13:39rename some expression attribute into
13:42another
13:43so the operator is row
13:46and you have an expression to which you
13:48give
13:49the
13:50name x
13:52and that is how the renaming of
13:54you can have multiple attributes of x as
13:57well
14:00division is a
14:01is another operator in relational
14:03algebra
14:05that ah can be applied between two
14:08relations but it is a derived operation
14:11so it says that
14:13if i have so let me just ah show you by
14:16by a little bit of
14:18sketch that if i have two relations
14:21which
14:22r
14:24which has a set of attributes z
14:27and s which is a set of attribute x such
14:30that
14:31actually
14:33the
14:34set z
14:36is
14:39a superset of x so z
14:42has more attribute the relation r has
14:44more attributes
14:45so
14:46if you take the difference of attributes
14:48between
14:50z and x and call it y
14:53then we are interested what happens on
14:56these remaining set of attributes y
15:01so this is what we have this is
15:04my
15:05x set of attributes this is where x
15:07occurs
15:08this difference is y this whole set is
15:11z
15:13now in this what we want is we want
15:17to
15:18in the output we want
15:20a relation having only the y attribute
15:23such that
15:25for every tuple in that relation
15:28if i consider all the tuples of s
15:32then their cos product must be a part of
15:36r
15:37so
15:38for every tuple here if there are
15:41say
15:42four tuples here a tuple here must have
15:46all these four tuples along with it in
15:49the result
15:50if it does not have any one or more of
15:52them then that tuple will not feature in
15:55the final result
15:59so the result of a division is a
16:01relation t y that include tuple t
16:04if tuples tr
16:06that is the part of the tuple
16:09the tuple that appear in r
16:13and
16:13on that on the y part the difference
16:16part
16:18it matches
16:19so that
16:21you have that t r x
16:24is equal to t s where t s actually exist
16:28in s this must happen for all tuples in
16:31s
16:33so division ah is a very good ah
16:36interesting operator which is often
16:39required for
16:40coding different queries
16:43so it is a derived operation let us take
16:45an example lets say this is
16:49this is the relation r
16:51and this is the relation s and i am
16:52trying to compute r divided by s so what
16:56i want is
16:58over the attributes of this is therefore
17:00x this is x
17:02this attribute y attribute set y
17:06so
17:07all
17:08over x all the values that i have
17:11i must have those values
17:14in the relation r
17:16if i do then the attribute
17:21the particular tuple
17:25matching on the attribute y goes on to
17:27the result
17:29so
17:30alpha goes on to the result because you
17:33have both alpha a
17:35alpha one as well as alpha two
17:39in the set r in the relation r
17:42beta one
17:45is there
17:46and beta two is also there
17:49so beta also goes into the relation
17:51alpha goes in because one is there
17:55two is also there
17:57but gamma will not go in
17:59because i have gamma 1
18:02but i do not have a tuple gamma 2 in r
18:06if i had gamma 2 in r that will go in
18:08the result
18:09so if i can
18:10say it again
18:12the whole of the relation s
18:16must happen
18:18over
18:19the x attributes of r
18:24consider these two together
18:27if that happens
18:28then
18:32the attributes
18:35on y
18:37the tuples would be chosen and that is
18:39how we get
18:41the result
18:42having alpha and beta
18:45let us look at one more example
18:49so this has got r has five attributes
18:51this has ah
18:53x has two
18:55so
18:56this is
18:59this is
19:00two attributes x these are three
19:02attributes y
19:04and what i have to look for is
19:08those tuples in r where
19:11the
19:15values over y would be same
19:18and i should be able to get
19:21the whole table of x
19:23over
19:24whole table of the relation s
19:27over the x attributes
19:28so if we look at here
19:31this is a one b one
19:34a one
19:35b one
19:37here
19:39these are identical
19:41so this particular tuple will
19:44go into the result
19:47if i
19:48look in here
19:53this tuple will go into the result
19:55but if i consider this tuple beta a
19:58gamma
19:59which has
20:01a one over d
20:04but beta a gamma
20:06does not have b one it has b three
20:10so it will not go into the result so if
20:13you conceptually look at that is the
20:15reason this is called a division so you
20:17get ah this here you get this here so
20:19this is like the way we divide that this
20:22is the hole and wherever it goes in
20:25if the tuples that are
20:28identical on the
20:29y set of attributes
20:32we will collect them into the final
20:34result
20:36so this is the division operation which
20:39ah by which we can compute the students
20:41who have taken both a and b courses
20:45with instructor 1 will be found out from
20:47this division operation
20:52so
20:52formally speaking a basic expression in
20:54relational algebra consists either of a
20:57relation in the database which is a
21:00instance or a constant relation which
21:04does not change which is given
21:06and
21:07then we have
21:08six
21:10operations of
21:12union set difference cross product
21:15selection projection and renaming that
21:18can give us all sorts of
21:20different relational algebra formula
21:23and also the derived operations and
21:25whatever we have seen of sql can be
21:28expressed in terms of this relational
21:31algebra formula
21:33now relational algebra is not something
21:36totally unique the same thing can be
21:38done in terms of other formulations also
21:41a second formulation which ah is also
21:44used is known as tuple relational
21:46calculus
21:47which is non procedural relational
21:49algebra was procedural because you are
21:51actually doing the ah explaining what
21:53the operations are you are detailing out
21:55what the operations are
21:57in tuple relational calculus
22:00you just specify
22:02what
22:03the
22:05condition is you are specifying what
22:07this condition is
22:09so those tuples which satisfy this
22:11condition form the relation
22:13so p is a predicate
22:16so whatever t
22:18satisfies the predicate are included
22:21and
22:22if a is an attribute then t a will
22:26denote the value of the tuple on
22:28attribute a a could be a single
22:30attribute it could be a set of
22:32attributes also
22:33and t is a relation that
22:37belongs to r
22:39p is as i said it is a its a predicate
22:42calculus formula so
22:44it could be a set of attributes or
22:46constants this i am just
22:48included
22:49for your help if in case you have
22:53ah become rusted with the predicate
22:55calculus you can refer to them a
22:56predicate calculus is a set of
22:58attributes and constants
23:00it has set of ah comparison operators
23:02the six of them
23:04there are a set of connectives these are
23:06all same as the propositional calculus
23:09ah there is implication which says if x
23:12is true then y is true
23:15if x is false then the whole thing is
23:16true
23:17vacuously
23:19and what makes it primarily pro
23:22predicate calculus is a fact that it has
23:24existential quantifier which says
23:28that
23:29the formula there exist t belongs to r
23:32q t
23:34holds if i can find at least one tuple t
23:36which satisfies q t
23:39similarly there is a universal
23:40quantifier
23:41where
23:42i will say that for all t belongs to r q
23:45t is true if
23:48for all tuples of r
23:50t satisfies q t
23:53so
23:54this
23:55in tuple relational calculus all
23:58conditions all predicates are formula of
24:01this kind
24:02and with that we can represent any
24:07relational set in full
24:10there is a word of caution because
24:13it is possible to write triple
24:15relational calculus expression
24:17that can potentially generate infinite
24:20relations now infinite relations are
24:23naturally not representable for example
24:25if i write simply this that r is a
24:28relation and i write this predicate that
24:31naught of t belongs to r which is
24:33basically complement set of r
24:35now a complement set of r
24:38potentially may be infinite if the
24:40domain is infinite
24:42so
24:43such
24:44expressions triple relational
24:47expressions are not acceptable as a part
24:49of the design
24:51so whenever we want to do this we would
24:54like to guard this
24:56by putting
24:57some additional condition
24:59and
25:00we have to make sure that any expression
25:03that we have in tuple relational
25:05calculus
25:06is a safe expression
25:08in the sense that it does
25:10give me finite number of
25:13tuples in the relation
25:17a third
25:18formalism that
25:20exist
25:22that is used is known as domain
25:23relational calculus
25:25which is also non procedural and
25:28equivalent in power to triple relational
25:30calculus again which is very similar to
25:33triple relational calculus the only
25:34difference being if you just recall
25:36tuple relational calculus we are writing
25:40ah collection of tuples t such that p t
25:44that is the predicate
25:46ah p is satisfied by t here instead of
25:50writing a tuple variable t
25:53we write expand it out in terms of all
25:56its components so we write the values of
25:59the different components of t over
26:02different n attributes and write it as a
26:05n tuple
26:07and so
26:08here instead of having one variable t we
26:11have n variable x one to x n and
26:13therefore the predicate is formed of
26:15this n variables where x one to x n at
26:19represent the different domain values
26:22domain variables
26:23and that leads to the reason for the
26:26name domain relational calculus
26:30now of the three formalisms that we have
26:32seen we will not go into ah direct
26:36mathematical proofs but in the next
26:38couple of slide i just show that
26:40they are equivalent in nature what means
26:43that if i can write an expression in
26:46relational algebra
26:48then it is possible to write an
26:49equivalent expression in triple
26:51relational calculus
26:53and in domain relational calculus and
26:55vice versa so if i can write an
26:58expression in any one of these
26:59formalisms
27:01then there are equivalent expressions in
27:03the other two formalisms as well which
27:06is probably very easy to see between
27:09tuple relational calculus and domain
27:11relational calculus because one is just
27:14representing the whole tuple as a single
27:16variable whereas the other is
27:18representing in terms of n domain
27:21variables so their equivalence is pretty
27:24much very similar except the fact that
27:27your
27:28predicate calculus formula has to change
27:32but it is not so obvious for
27:35the equivalence between relational
27:37algebra and the calculi so we just show
27:40a few
27:41examples of the basic operations for
27:43example say select operation
27:45so i am just not showing the proof i am
27:47just giving you some example cases to
27:50show so relation
27:51r has two attributes a b this is what
27:54you wanted to write in relational
27:55algebra that you want to collect all
27:57tuples where
27:59b is equal to seventeen naturally in
28:01triple relational calculus you can
28:03easily write the first condition is you
28:05are doing it on r so t must belong to r
28:08and your condition is b
28:10should be seventeen so this predicate
28:13will represent the same set
28:16or the same relation as in triple
28:18calculus
28:19in domain calculus there are two
28:21components a and b so you have to say
28:23component
28:24taken together must belong to r and the
28:27component b must be equal to seventeen
28:30so you can see that it is pretty
28:31straight forward to
28:33see the equivalence between a relational
28:36algebra expression involving select and
28:39the corresponding tuple calculus or
28:40domain calculus expressions
28:43this is a through an example but you can
28:45certainly easily generalize this as a
28:48proof
28:50similarly for projection if we do a
28:52projection on a
28:53then all that we are trying to do is we
28:56are trying to create
28:58a new relation where
29:00only
29:01the a attribute exist
29:04so in the tuple
29:06t the a attribute exist
29:09and if i
29:11have projected and got this tuple t
29:15then in my original relation r there
29:17must be some tuple
29:19p
29:20such that
29:22on the attribute a they match they are
29:24same
29:25so its the same thing in relational
29:27algebra we said that keep a and erase
29:29everything else here we are saying that
29:31if we have been able to get a tuple t
29:34which has a value t a
29:37then there must be a triple
29:39p in r
29:40which has the same value over the same
29:42attribute
29:43so this condition
29:45is
29:47equivalent representative of the
29:49projection
29:50and the same thing can be written in
29:52domain calculus you can
29:54go through it
29:56carefully and convince yourself
29:59you can combine these
30:01as in the relational algebra
30:03as well as in ah tuple calculus so here
30:06you apply one relation one operation and
30:08then the other one selection then
30:11projection
30:12here you can combining this this is part
30:14of projection this is also part of
30:17projection but this condition has come
30:19from the selection and get a total
30:21predicate calculus predicate which will
30:24give you the triple calculus expression
30:27for this combined expression of
30:29relational algebra domain calculus will
30:31certainly happen in a similar manner
30:35union certainly is straight forward so
30:37you can ah
30:39do it yourself
30:40set difference is again ah very straight
30:43forward because thats in fact in set
30:45theoretically whatever
30:47operations we have their
30:49relational algebraic definition itself
30:52is a tuple calculus formula you can
30:54expand them out and write in the domain
30:56calculus as well
30:58intersection plays out in the same way
31:00tuples that belong to both r and s
31:04cartesian product
31:06is little bit more involved because all
31:08that you are saying here is
31:10if i have a cartesian product then if
31:12that product has a
31:14tuple t
31:15then there must be a tuple p in the
31:18relation r the left relation there must
31:20be a tuple q in the in s the right
31:22relation
31:24so that the final tuple t matches p on
31:27the a attributes
31:30the b attributes that is attributes of
31:32relation r
31:34and
31:36the components of t matches
31:39the tuple q
31:41in the
31:42attributes of s if all these conditions
31:45happen together then naturally this
31:48tuple t
31:49is a
31:50valid tuple for the cartesian product so
31:52you could take examples and work this
31:54out and convince yourself that these are
31:57really equivalent
32:00we can ah define ah natural join in a
32:02similar way which i leave it as an
32:05exercise for you to convince yourself
32:08that this
32:10relational algebra expression for
32:11natural join indeed has similar
32:14equivalence in tuple and domain calculi
32:18division
32:19we just showed as a derived
32:22operation
32:23we have not showed how
32:26in relational algebra you can
32:28write division using the other
32:30operations i will leave that as an
32:32exercise as well
32:34but here what i show is in tuple
32:36calculus how you can write division
32:39ah using the quantifiers here you can
32:41see that here for the first time we do
32:43need to use the universal quantifier to
32:46make sure that while i divide that the
32:49whole of the table of s must be
32:51available against
32:52the
32:53part of the tuple part of the y
32:55attributes as we said that will be
32:57collected in the result
33:03so to summarize
33:05we have ah discussed
33:07primarily the relational algebra with
33:09some examples
33:11we have introduced the tuple relational
33:13and domain relational calculus
33:16and through a set of examples we have
33:18shown
33:19that we have illustrated that the
33:22algebra and the calculi are equivalent
33:25and
33:26i would
33:27request you to work out more examples to
33:30understand the equivalence or if you are
33:32really enthused please try out proving
33:36their equivalence formally as well
42:23you

About this transcript

This page contains the full transcript of Formal Relational Query Languages by Data Base Management System - IITKGP, generated from the public captions YouTube serves with the video. The transcript has 4,166 words across 843 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.