[MUSIC] Okay, last time we talked about 
algebraic optimization and I argued that 
all three of these expressions without 
going into a lot of detail. 
But I argued that all these three of 
these were equivalent and they differed 
only in the order in which things were 
evaluated. 
Here you evaluate this join first and 
this join second. 
And in this expression you evaluate this 
join first and this join second. 
And here you, sort of, find all possible 
combinations of two bulls and then filter 
that. 
And so if you don't understand exactly 
what's going on in these expressions 
that's okay. 
You're not going to know that yet. 
We'll talk about it in fact, in this 
segment, I think. 
but the idea, the take away here is that 
there's three equivalent expressions and 
we don't know necessarily which ones, 
which one is the fastest one to you, to 
evaluate. 
But the database can figure this out and 
does, every time you write a query. 
And that's this notion of algebraic 
optimization. 
Now, we don't you know, even if you are 
familiar with databases, you may or may 
not be familiar with the relational 
algebra. 
which should be strange, because I've 
argued that it's you know, the hallmark 
of databases and totally fundamental. 
So why don't we think about programming 
databases in terms of writing relational 
algebraic expressions? 
Well, another good idea, another key idea 
that's associated with relational 
databases is this notion of declarative 
languages. 
And what we mean by declarative languages 
is that you specify the answer that you 
want but you do not specify anything 
about how to get it. 
And so a relational algebra expression 
actually does specify an order, as I 
showed on this slide, here's three 
different expressions that's indicating 
exactly which order to do every 
operation. 
That means that some, you know, if you 
write, if you write an expression like 
this you're instructing the computer, 
look do it in this particular order. 
Okay? 
And so these declarative languages say, 
look we're just going to describe the 
properties that must be true of the 
result. 
And we're going to let the database 
figure out the right order in which to do 
this. 
And so here is a quick example. 
So imagine you have two tables. 
One is order with three columns, order, 
date and account and another table with 
item with two columns order and part. 
And the semantics here is that this 
column indicates which order that item 
should be associated with. 
Okay. 
And so if you want to say find all orders 
from today along with the items ordered, 
then you might write this query, and if 
you've seen SQL plenty of times before, 
bear with me. 
And if you haven't, then pay attention. 
So, select star, give me all possible 
columns from the table order and all 
possible columns from the table item. 
But I only want record such that this 
condition is true. 
Where the order column from the order 
table matches the order column from the 
item table, right. 
And further, I only want orders from 
today, where order dot date equals today. 
So this is just conditions expressed over 
the results, without any kind of idea of, 
of what, of, of how to actually get this 
answer. 
So what automatically happens is that 
this query is translated into a 
relational algebra expression along the 
lines of what we've already seen. 
Now here I have sort of just done a 
cartoon where you can say scan the item 
table, scan the order table, select the 
record such that date equals today and 
then perform the join. 
Find all the records in order they 
correspond to the that have, for each 
record in order find the corresponding 
records and item that match on, on on 
order. 
Okay? 
So, this is happening every time you run 
a query, again. 
So the SQL is the what, not the how. 
Give you another example, there's three 
columns, product, purchase and customer. 
In this the underlining here we haven't 
talked about, but this is the indicating 
what makes the table, what makes this 
record unique. 
And so here, the PID makes the product 
unique, the CID makes the customer unique 
and the combination of pid and cid makes 
the purchase unique. 
Okay. 
And so here is another sequel query. 
We say select distinct product name. 
Why do I know it's the product name, 
because I see an x here and I see an x 
here. 
And the customer name and I knows it's 
the customer name because I see a z here 
and I see a z here. 
This is an alias for the, for the 
relation customer. 
From these three tables where the product 
ID in the product table matches the 
product ID in the purchase table. 
And the customer ID in the purchase table 
matches the customer ID in the customer 
table. 
And that's a typo looks like, that should 
be z. 
So, maybe change that on your own slides. 
Let me see if I can fix it now z. 
That's the ID. 
And then we want, we, but now we want 
only the, the products for which the 
price is greater than 100, and we only 
want the customers whose city is Seattle. 
Alright, so what does this say in 
English? 
Well find the, combinations of products 
and customers, unique combinations of 
products and customers where the 
customer's in Seattle and they paid for a 
product worth more than a 100. 
Okay. 
So it's clear what we want, but it's 
unclear how to get it, it gets kind of a 
complicated query. 
Okay. 
So translating this into relational 
algebra, we have this. 
So at the bottom we have product and the 
purchase and now we do this join. 
Where we say for every product, find me 
the corresponding records and purchase. 
Then we do another join for every record 
in, the, in the, result of this join find 
me the corresponding records and 
customer, right. 
Now filter out all those records such 
that where, where price is not greater 
than 100, we only want the ones where 
price is greater than 100. 
And we only want the ones where city 
equals Seattle. 
And then we want to, in this case, 
project down onto these two columns. 
What I mean by project is get rid of all 
the other columns except for the two 
we're interested in. 
Okay? 
And finally, take, take the final answer. 
So, the two points here is that the 
execution order is now clearly specified. 
But there are a lot of physical details, 
are still left open. 
You know this is a very high level 
indication of what's going on. 
Order of operations is clear but that's 
about it. 
We don't know how we're going to do the 
join, exactly, and there's multiple ways 
you can do it. 
I've indicated that you know, we're 
going to take for every rec, every record 
and product we're going to look up a 
corresponding record of purchase. 
But we haven't said precisely what that 
means. 
Okay. 
I give a I'm going to give a example of 
this in a second. 
So another example here, here we only 
have a single relation called R and it's 
got three columns, subject, predicate, 
and object. 
And you see this kind of schema when you 
hear about, when you work with RDF data, 
the Resource Description Framework. 
An RDF is a language and formalism and 
software stack for managing what is 
called linked data and here sort of 
everything is it's a set of all facts. 
Any kind of fact you can come up with 
beginning code in RDF you can say you 
know, the instructor of this course is 
Bill Howe. 
Right? 
So, here the subject might be this 
course, the predicate is has instructor 
and the object is Bill Howe. 
Okay. 
And so this is a people use this 
formalism as a very general way of 
encoding an information from any source. 
And we we may, we might touch on this 
much later in the course. 
Okay, they used kind of a complicated 
query. 
But what it says is I'm going to have 
three instances of the same relation. 
And I'm going to join them all up. 
And I'm going to look for a sequence of 
tubules such that we have a person who 
knows another person who holds the 
account of a company who has an account 
homepage of a particular value. 
Alright, so you are looking for the 
sequence of where this edge is knows, and 
this edge is holdsaccount. 
And this edge is accountHomepage. 
Right? 
So find me all possible combinations in 
this table where I've got, you know if I 
nail, "A, B", all instantiations of A, B, 
C, and D such that this pattern matches, 
Okay. 
And the joins are specified by these 
conditions. 
The object of the first relation must be 
equal to the subject of the second 
relation and the object of the second 
relation must be the subject of the third 
relation. 
Okay. 
So we're looking for patterns in the 
graph that look like this. 
And in relational algebra, you see this, 
this, this query gets translated into 
this form. 
There's a selection to find predicate 
equals knows. 
There's a selection to find predicate 
equals holds accounts. 
And there's a selection to find predicate 
equals account homepage. 
And then you join. 
And then a sequence of joins. 
And finally, a projection just to pull, 
pull out the, the final answer that we're 
interested in. 
In other words, the select clause. 
Okay. 
So, perhaps a complicated example, but I 
think the takeaways here. 
I, I wanted to mention RDF. 
because we might come up, come across it 
again. 
And I also want to demonstrate that you 
can access the same relation more than 
one time in a single query. 
And then I wanted to give another example 
of translating even complicated queries 
into relational algebra expressions. 
Okay.