0:01
This is the second of two videos about the relational algebra.
0:04
In the first video, we learned
0:06
about the select and project operators in various types of joins.
0:10
This video will cover set operators,
0:12
union difference and intersection, the
0:14
renaming operator, and different
0:16
notations for expressions of relational algebra.
0:20
Just as a reminder, we apply
0:21
a relational algebra query or
0:23
expression to a set
0:25
of relations and we get
0:26
as a result of that expression
0:28
a relation as our answer.
0:30
For our examples, we're using
0:31
an imaginary database about college admissions.
0:34
We have a relation of colleges,
0:36
a relation of students, and a
0:37
relation with information about students applying to colleges.
0:41
We'll keep at the bottom of
0:42
the video these three depictions of
0:44
those relations with a few
0:46
abbreviations used so that names aren't too long.
0:49
Let's move ahead to our first operator.
0:52
The first of three set operators
0:54
is the union operator, and it's
0:55
a standard set union that
0:57
you learned about in elementary school.
1:00
Let's suppose, for example, that we
1:01
want a list of the
1:02
college and student names in our database.
1:04
So we just want those as list.
1:05
For example, we might want
1:07
Stanford and Susan
1:10
and Cornell and Mary
1:15
and John and so on.
1:17
Now you might think
1:19
we can generate this list by
1:20
using one of the operators we've
1:22
already learned for combining information
1:23
from multiple relations, such as
1:25
the cross-product operator or the natural join operator.
1:29
The problem with those operators
1:30
is that they kind of combine information
1:32
from multiple relations horizontally.
1:34
They might take a tuple T1
1:36
from one relation and tuple T2
1:38
from the other and kind of match them.
1:40
But that's not what we want to do here.
1:41
We want to combine the information vertically to create our list.
1:45
And to do that we're going to use is the union operator.
1:48
So in order to get a list
1:49
of the college names and the
1:50
student names, we'll project the college name from the college relation.
1:55
That gives us a list of college names.
1:57
We'll similarly project the student
1:59
name from the student relation,
2:02
and we've got those two lists
2:03
and we'll just apply the union
2:04
operator between them and that will give us our result.
2:07
Now, technically, in relational algebra
2:10
in order to union two lists
2:11
they have to have the same schema,
2:13
that means that same attribute name
2:14
and these don't, but we'll correct that later.
2:17
For now, you get the basic idea of the union operator.
2:20
Our next set operator is
2:22
the difference operator, and this one can be extremely useful.
2:25
As an example, let's suppose
2:26
we want to find the IDs
2:28
of students who didn't apply to any colleges.
2:30
It sounds like a complicated query, but
2:32
we'll actually write it in a very simple fashion.
2:35
We'll start by projecting the student
2:37
ID from the student relation
2:39
itself and that will
2:40
give us all of this student IDs.
2:42
Then lets project the student
2:44
ID from the apply relation
2:47
and that gives us the IDs
2:48
of all students who have applied somewhere.
2:51
All we need to do is
2:52
take the difference operator, written
2:54
with the minus sign, and that gives us the result of our query.
2:57
It will take all IDs of
2:58
the students and then subtract
3:00
the ones who have applied somewhere.
3:03
Suppose instead that we
3:05
wanted the names of the students
3:06
who didn't apply anywhere, not just their IDs.
3:09
So that's a little bit more complicated.
3:11
You might think, "Oh, just add
3:12
student name to the projection
3:14
list here," but if we
3:15
do that, then we're trying to
3:17
subtract a set that has
3:18
just IDs from a set that has the pair of ID names.
3:20
And we can't have
3:22
the student name here because the
3:23
student name isn't part of the apply relation.
3:26
So there is a nice trick, however, that's going to do what we want.
3:29
Let me erase these here.
3:31
What we're going to do is
3:32
we're going to take this whole
3:34
expression here which gives us
3:35
the student IDs who didn't apply anywhere and watch this.
3:38
Pretty clever.
3:39
We're gonna do a natural join
3:42
with the student relation.
3:43
And now, that's called a join back.
3:45
So we've taken the IDs,
3:47
a certain select set of IDs
3:48
and we've joined them back to the student relation.
3:51
That's going to give us a
3:52
schema that's the student relation
3:54
itself, and then we're just
3:55
going to add to that a
3:57
projection of the student name.
3:59
And that will give us our desired answer.
4:03
The last of the three set operators is the intersection operator.
4:07
So let's suppose we want
4:08
to find names that are both
4:09
a college name and a student name.
4:11
So perhaps, Washington is the name of a student and a college.
4:15
To find those, we're going to
4:16
do something similar to what we've done in the previous examples.
4:19
Let's start by getting the college names.
4:24
Then let's get the student names,
4:29
and then what we're going to do
4:30
is just perform an intersection of
4:32
those two expressions and that will give us the result that we want.
4:36
Now like our previous example,
4:37
technically speaking, the two
4:39
expressions on the two sides
4:41
of the intersection ought to have
4:42
the same schema and again, I'll
4:43
show you just a little bit
4:44
later, how we take care of that.
4:47
Now, it turns out
4:49
that intersection actually doesn't add
4:51
any expressive power to our
4:53
language and I'm going
4:54
to show that actually in two different ways.
4:56
The first way is that
4:57
if we have two expressions, let's
4:59
say E1 and E2 and
5:02
we perform their intersection, that
5:04
is exactly equivalent to
5:06
writing E1 minus, using the
5:08
difference operator, E1 minus E2.
5:12
Now if you're not
5:14
convinced of that immediately, let's go
5:15
back to Venn diagrams, again
5:17
a concept you probably learned early in your schooling.
5:19
So let's make a picture of two circles.
5:23
And let's say that the first
5:24
circle Circle represents the result of
5:26
expression E1 and the
5:28
second rear circle represents the
5:29
result of expression E2.
5:32
Now if we
5:33
take the entire circle E1.
5:36
Let's shade that in purple.
5:39
And then we take the
5:41
result, so that's E1 here,
5:43
and then we take E1, the
5:45
result of the expression E1
5:46
minus E2 here, we'll write
5:48
that in green, so that's everything
5:50
in E1 that's not in
5:51
E2, that's this. Okay?
5:55
And if we take the purple minus
5:57
the green you will see
5:59
that we actually do get the intersection here.
6:02
So that's a simple property
6:04
of set Operations but what
6:05
that's telling us is that
6:07
this intersection operator here isn't
6:08
giving us more expressive power because
6:10
any expression that we can
6:11
write in this fashion, we can equivalently
6:14
right with the difference operator in this fashion.
6:17
Let me show you a completely
6:18
different way in which intersection
6:20
doesn't add any expressive power.
6:22
So, let's go back to
6:23
E1 intersect E2 and as
6:27
a reminder for this to be
6:28
completely correct these have to
6:30
have the same schema as equal between the two.
6:34
E1 intersect E2 turns out
6:35
to be exactly the
6:37
same as E1 natural join
6:40
E2 in this particular case
6:42
because the schema is the same.
6:45
Remember what natural join does.
6:46
Natural join says that you
6:48
match up all columns that
6:50
are equal and you eliminate duplicate values of columns.
6:52
So I'll just let you work
6:53
out for yourself that this
6:55
is indeed an equivalence and
6:57
a second reason that the
6:59
intersection doesn't add any expressive power.
7:01
Nevertheless, the intersection can be
7:03
very useful to use in queries.