[MUSIC]. 
So let's take a step back and see where 
we are. 
We talked about graph tasks in general, 
give an example of constructing these 
histograms, talked about structural, 
traversal, and pattern tasks. 
Gave page rank as an example of 
structural and of, both a structural and 
a traversal task. 
And then talk about pattern languages in 
SPARQL and SQL and Datalog. 
Gave a few more detailed examples of 
Datalog motivated by what's been going on 
in the news in June 2013. 
Related to the Prism system, but what we 
haven't talked about is how to implement 
much of this, especially at scale. 
So that's what I want to do next. 
We're going to stick with Datalog for a 
moment and think about how to actually 
implement those kinds of queries in 
MapReduce. 
And then talk about how to implement 
PageRank in MapReduce. 
So we're back towards the beginning of 
the course, we talked about how to 
implement a relational algebra operations 
in MapReduce at scale. 
And we showed this sort a connection, you 
know, between languages like pig in the 
relational algebra. 
What databases do or is obviously 
relation algebra and what you can 
implement directly MapReduce. 
So there seems to be this kind of 
relational algebra DNA in a lot of these 
large large scale programming platforms. 
However, all of those cases, we never had 
anything that had to loop, that had to do 
recursion, that had to do iteration. 
And now that we're talking about graphs 
as we sort of pointed out that traversal 
of these graphs is really the salient 
future of working with them. 
And so it can't have been traversal tasks 
and it came up in pattern languages in 
Datalog. 
We saw examples of recursive data log 
programs without talking much about how 
they'll be implemented. 
So I want to cover that a little bit now. 
So, given if you have a recursive Datalog 
program that looks like this. 
So you can say this is an edge relation 
that's just linking an arbitrary vertex x 
with an arbitrary vertex y. 
Every pair of edges is stored in a 
relation called edge and I write this 
program. 
This program says find me all the edges 
connected to the vertex labeled w. 
And here we have a vertex labeled w. 
Input those in a new relation called A. 
Then also, find me additional values of A 
in this manner. 
For every vertex that's already in A, go 
find me an edge that leads out from that 
vertex, and give me a new generation of 
vertices. 
So this is now a recursive Datalog 
program but which you can think about it 
intuitively what is doing is traversing 
this graph in kind of a bad breath first 
way right? 
So first we fire this rule which just 
says out of all the vertices select the 
one with w. 
And we know how to do this, we could 
write this in SQL, I would hope, right? 
We can write this in MapReduce, we can 
write this in Python. 
Finding all edges where the first 
position is, has a labeling of w, and 
call that A0. 
Or find me everything that's connected to 
w call all those collectively A0. 
Next we go to this rule and now we have 
to join All the ones we've already found 
with the edge relation to produce a new 
generation of vertices. 
For each node in A0 find all of its 
neighbors. 
And then in step two we fire this rule 
again, for each node in A1. 
Find the neighbors, and so on. 
So we keep finding more and more, 
vertices in this graph as we go one 
generation away. 
And that's, naively how we would, how we 
might evaluate this recursive program. 
That's what this, that's what the meaning 
of this program is. 
Okay, but there's a problem here. 
What if there's a cycle in the graph? 
Well, at generation one, we find Sue and 
generation two, we find Tom, and 
generation three, we find Lin. 
And in generation five we find Sue again, 
and so we just keep going. 
So we need one more piece, which is to 
remove all the ones we've already found 
previously. 
So let's look at this again, so this is 
called semi-naive evaluation. 
So here's this reachability query that we 
were just looking at. 
Find the everybody that's connected to 
everybody that's in the, in the social 
network of some vertex labeled A, right. 
Everybody is reachable from A. 
So here's how it would work. 
We're going to have these delta 
relations, which are just the new gener, 
just everything found in the new 
generation, right? 
Just like those colored levels were in 
the previous pictorial representation. 
So while we're still finding new 
vertices, were going to keep going. 
If at any, if at any point we don't find 
anything new then we know we're done and 
we can stop and we can return the 
results. 
Okay so while we're finding new things, 
let's call A to Ai the union of all the 
deltas that we found previously. 
The iteration zero, union with iteration 
1, union with iteration 2, and so on. 
And if you're not familiar with this 
notation, this just means. 
Think of it as concatenation in a 
programming language, right? 
Except you're also going to remove 
duplicates, right? 
Then delta Ai is, the previous new 
results joined with the relation R. 
Alright, so this gives me one more 
generation, and I'm expressing this in 
the relational algebra notation of join. 
So that's what we showed pictorially a 
moment ago. 
However now what we also want to do is 
remove any duplicates. 
We want to subtract out anything we found 
in any previous generation at all, and 
this is in order to break cycles. 
If we've already seen that, if we've 
already found Sue, then we don't want to 
find her again, alright? 
And then we increment this calendar so we 
can keep track of everything. 
And then our final result, when we're 
done, is this Ai for whatever i is at the 
end. 
And so I'd claim that, if we're going to 
do this in MapReduce, which is what we're 
trying to build up to, then this line is 
the important line. 
This line is actually pretty easy in map 
reduce because of an implementation 
detail. 
A union of a bunch of different data 
sets, if they're known to be disjoint, is 
actually literally just concatenation of 
the files. 
Which sort of happens implicitly in, in 
MapReduce. 
And I'm not going to go into much more 
detail than that. 
But, I just to say that it to say that 
this line is, can be arranged so that its 
not very expensive. 
Its essentially free, but this line is 
where there's a lot of work going on. 
So lets look at, lets break this down and 
pretend like and show how this is going 
to be implemented in MapReduce. 
Alright, so its actually two different 
MapReduce joins, one to do the join and 
one to do the difference. 
And we saw this in the lecture on pig 
where join was one operation. 
And we didn't show a pig operation 
corresponding to difference but you can 
implement it using grouping. 
Okay, but we did see that generally one 
operation and another operation would 
turn into two MapReduce jobs chained 
together. 
And that's whats going on here, so what 
happens with the join is, we have the 
Delta A from the previous iteration. 
Along with the, the hu, the hu, the very 
large edge relation, right? 
This is billions of edges, perhaps, 
spread across all sorts of computers. 
And we process them all in parallel, 
spray them across the network. 
And per, and implement the reduce phase 
in order to compute the join. 
Then do the difference we find everything 
we just got, everything we just found 
from the join. 
Spread across the network again, along 
with everything that we've ever seen 
before. 
Everything in this Ai, everything in the 
union. 
And make sure, make sure to remove 
duplicates. 
And you implemented both of these things, 
or specified how to implement both of 
these things in the MapReduce assignment. 
You showed how to do a join and you 
showed how to do a, duplicate 
elimination, essentially, which is, which 
is what this is doing. 
Okay, and then the only new piece we 
need, which is where MapReduce gets a 
little bit, 
Becomes a little bit of a poor fit for 
this task is that you need some sort of 
external driver program to control the 
iteration. 
To check and see if there's anything new. 
Okay, so MapReduce can't do loops in and 
of itself, so you have to do something 
outside of the system. 
Alright, so again two big steps. 
Compute the next generation of vertices 
or nodes and remove the ones we have 
already seen. 
Alright, so this is fine and this works, 
but there's some performance issues that 
are pretty significant, and we'll talk 
about that next time.