[MUSIC] Okay, so, let's talk about 
relational databases. 
So the history here is that, which I 
motivated last time, I hope, is that 
pre-relational, if your data changed in 
some significant way, if you needed to 
reorganize things in some way, your 
application broke. 
Okay so if you changed the parent child 
relationships in the hierarchical model 
or if you pretty much did anything with 
the network or file oriented model, you 
ended up, your applications had to be 
rewritten to support that, okay. 
And so early relational databases 
addressed this issue and even though they 
were buggy and sort of slow they required 
only about 5% of the code you had to 
write previously and so this was an 
enormous win, okay. 
And so this quote, this sort of 
motivating us, sort of following on what 
the quote I used from Curt Monash in the 
previous segment is from the original 
paper on databases from Ted Codd. 
So activities of users at terminals and 
most application programs should remain 
unaffected when the internal 
representation of data is changed and 
even, excuse me, when even when some 
aspects of the external representation 
are changed. 
And so the reason I want to emphasize is 
that again this is the key idea of 
relational database is not SQL, and not 
some of the other features that you 
associate with, with particular 
implementation. 
It's really this, notion of data 
independence. 
OK, and this was the, right there in the 
abstract in the original paper. 
This is the key idea. 
And then, and the reason I'm in, hitting 
this so hard, is that this idea is still 
just as important now as it was then. 
All right. 
So I'm going to go through some of the 
other key ideas that were that are 
associated with relational databases, 
whether or not they were in the original 
paper. 
So one key idea is that programs that 
manipulate tabular, that manipulate 
tabular data exhibit this algebraic 
structure that we can use to reason about 
them and manipulate the logical model 
independent of any physical data 
representation. 
So what I mean here is that if you think 
in terms of tables, and you think about 
the operations that tables support, you 
can think about how, what your program 
means, and even how to optimize it, which 
we'll show. 
Regardless of how the bits are actually 
organized on disk. 
And this is, you know, incredibly 
powerful. 
Okay. 
So, the key idea here again, is physical 
data independence, and we'll talk about 
what logical data independence means, 
too, in the, in the next segment. 
And so you know the programs that you 
write to manipulate things no longer have 
to sort of manipulate files and sort of 
chase pointers around. 
You can in this case access it through a 
high level language SQL although again it 
doesn't have to be SQL. 
The point is that your manipulating 
logical structures called tables, 
alright. 
So just know the term physical data 
independence and know that it means that 
your programs you write to manipulate 
data are more robust then they would be 
without this relational model, right. 
So another key idea is that there's this 
algebra tables that I mentioned and we'll 
talk more about these specific operators 
in a bit but at a high level you know. 
One operation on the table is to select 
out rows that satisfy some condition. 
Another is to ignore columns that you're 
not interested in. 
Another one is to, for two tables, for 
every record in a, in the first table, 
find corresponding records in another 
table, right? 
Select, project, and join, and there's 
other operations you can define as to 
aggregation also to set up operations 
derived from set theory, union and 
differentiating cross product and so on. 
And so these operations if you write your 
expression out in terms of these 
operations. 
It's very clear what it means, and it, 
it's, it's for software engineering 
purposes, as it allows the database 
designers to focus on just implementing 
these operations efficiently, okay? 
Now, you know, I'm be, if, if I can, if I 
join a classroom, what I'd ask is, how 
many people have heard of the relational 
algebra and, and also ask how many people 
have worked with databases. 
And typically, the number of people who 
have worked with databases is very high 
and the number of people who have heard 
of the relational algebra is somewhat 
lower and that's one of the things I hope 
to fix, in, in this course is to equate 
the two. 
Right, if you, if you, if you understand 
databases I want you to understand 
relational algebra and vice versa I guess 
comes for free. 
Okay. 
So why do we care about this algebra, why 
am I saying algebra? 
Well you know, what I, when I'm giving a 
talk and I'm using the slide, well, I'll 
ask you, how many people have heard of 
algebraic optimization? 
And typically, very few have, even if 
they're computer scientists, unless it's 
a room full of database people. 
But the thing is, that you already 
understand what this is, right? 
You don't have to know databases to know 
what this is. 
This is just something you learned in 
high school in Algebra class, okay. 
So forget tables for a second. 
Just think about integers. 
Well, I've got this expression here. 
And I want you to evaluate this 
expression when I tell you z is equal to 
4. 
Okay, so one thing you might do is just 
well, say, well you know, 4 times 2 is 8 
and 4 times 3 is 12 and so that's 20 and 
I add 0 and that doesn't change anything 
and then I divide by 1, fine. 
But if you're clever, you might notice 
that, well adding zero to any number 
doesn't change it at all so I'll just 
ignore that altogether. 
Similarly, dividing, any number by 1, or 
any integer by 1, is the same number, so 
I'll ignore that as well. 
And then, if you're really clever, you 
might notice that there's a 
distributivity law, here, that says, when 
I see this pattern, I can pull out the 
multiplication. 
And, by applying these rules in turn, 
including commutativity law, that allows 
things to re-, reordered. 
I can simplify this expression, down to 
this and this just says well now 2 plus 3 
is 5, just multiply 5 times 4 and I get 
20 and I've done fewer operations. 
I've only done two operations instead of 
five and I didn't have to do division 
which is potentially an expensive 
operator if you think about a computer 
evaluating this. 
Now do you know, do do computers use this 
kind of symbolic reasoning when they 
evaluate expression over integers? 
No, the answer is no. 
And the reason is, is that this kind of 
symbolic reasoning is much, much more 
expensive than just evaluating the damn 
thing, right. 
So fine. 
But if the objects that you are 
manipulating are not small integers, but 
rather terabyte sized tables, then this 
kind of symbolic reasoning is not only 
valuable but it's absolutely critical. 
If you things in the wrong order, if you 
do wasted work, or you do more operations 
than you need to over massive tables 
you're dead in the water and you'll get 
nothing done. 
And so, all databases, all relational 
databases, rather, do this kind of 
algebraic optimization when you write a 
query. 
Right? 
And so, if you think in terms of SQL, if 
you're familiar with SQL, your query gets 
translated into a relational algebra 
expression, in terms of selects and 
projects and joins. 
And then, is manipulated, according to 
algebraic rewrite rules, just like you 
learned in in algebra class, and that's 
why the term algebra is there. 
and they attempt to simplify the 
expression, I simplify, the reason I 
pause is it simplifies is perhaps not the 
right word, because it, it's not always 
true that the shorter the expression, the 
faster it is. 
it's we actually use this notion of cost 
based optimization which means we'll try 
lots of different equivalent expressions, 
assign each one of them an estimated cost 
and choose the one with the lowest cost. 
And this is something that all relational 
databases are doing in one form or 
another okay. 
So fine, so this is this is the magic 
trick of query processing in relational 
databases and this is a really, really 
great idea. 
And the, the reason why this works is 
because we understand very, formally what 
these operations are and what they mean. 
Okay. 
And so when you, when you relax this 
formal model, and start allowing anybody 
to write any kind of code they want over 
the data. 
You lose the ability to do this kind of 
algebraic optimization. 
And you leave it up to the programmer to 
write the best possible algorithm. 
And what I'm hinting at here is well, 
we'll talk about it more later but when 
you think about writing large-scale data 
processing pipelines in something like 
MapReduce and if you haven't heard of 
MapReduce, don't worry, we'll talk about 
it. 
You're leaving all the work up to the 
programmer to not only write the logic 
but also to do the optimization. 
And this, you can take, you can impose a 
penalty. 
Okay, one final comment about this is the 
term algebra is not just kind of trying 
to connote you know, algebra from high 
school, it literally is the same thing. 
So when you hear the word algebra, what 
you should be thinking of is this notion 
of algebraic closure, and what I mean by 
that is every operation that applies to a 
table also returns a table. 
And so I can chain these operations 
together to always get tables, alright. 
Now that's the exact same idea that's 
going on when you talk about operations 
over integers or, or real numbers. 
And you might sort of quibble and say, 
well if I divide an integer by some other 
integer, I may get a real number and 
that's true. 
But there's notions of multi-sorted 
algebras with different types involved. 
But the point is that this notion of 
closure, you can't escape the system by 
applying operations, is, always true when 
you hear the term algebra. 
So we're not making things up. 
Fine, so here's some relational algebra 
expressions that if you squint hard 
enough, you can see kind of look like 
similar expressions over integers, except 
instead of addition and multiplication, 
we have things like joins and selects. 
And so what this says, no I haven't shown 
you the query, I don't expect you to 
initially see this, but what this says is 
select certain values from a relation R. 
And here, I'm going to select other 
values, from the same relation R, that's 
okay, I can have two different, eh, you 
know, the relation R can appear in two 
different places in the same expression, 
no problem. 
And, then join them together, then 
select, still, other values from the 
relation R, and join this one. 
And one way of evaluating this plan is to 
perform this join first and then this 
join second and, indicated by these 
parentheses, right? 
another way to evaluate this expression 
is to perform this join first and then 
form this join second indicated by the 
parenthesis. 
Still another expression is to take the 
full cross product of all three 
relations, which I haven't told you what 
cross product is. 
This is actually a pretty bad one to do. 
If you do know what a cross product is, 
it generates an enormous amount of data, 
and you would never actually want to 
evaluate this plan. 
But you could, and it's provably 
equivalent to these other plans, so you 
know that it returns the same answer. 
And now all we have to do is figure out 
which one of these is, is likely to be 
the cheapest one. 
And then we'll choose that one to run. 
And this, this is the kind of reasoning 
that all databases do internally whenever 
you write a query.