Evaluation of Recursive Programs
Manipulação de dados em escala: sistemas e algoritimos
Universidade de Washington
Curso 1 de 4 no Ciência de dados em larga escalaCiência de Dados em Larga Escala Programa de cursos integrados
Data analysis has replaced data acquisition as the bottleneck to evidence-based decision making --- we are drowning in it. Extracting knowledge from large, heterogeneous, and noisy datasets requires not only powerful computing resources, but the programming abstractions to use them effectively. The abstractions that emerged in the last decade blend ideas from parallel databases, distributed systems, and programming languages to create a new class of scalable data analytics platforms that form the foundation for data science at realistic scales. In this course, you will learn the landscape of relevant systems, the principles on which they rely, their tradeoffs, and how to evaluate their utility against your requirements. You will learn how practical systems were derived from the frontier of research in computer science and what systems are coming on the horizon. Cloud computing, SQL and NoSQL databases, MapReduce and the ecosystem it spawned, Spark and its contemporaries, and specialized systems for graphs and arrays will be covered. You will also learn the history and context of data science, the skills, challenges, and methodologies the term implies, and how to structure a data science project. At the end of this course, you will be able to: Learning Goals: 1. Describe common patterns, challenges, and approaches associated with data science projects, and what makes them different from projects in related fields. 2. Identify and use the programming models associated with scalable data manipulation, including relational algebra, mapreduce, and other data flow models. 3. Use database technology adapted for large-scale analytics, including the concepts driving parallel databases, parallel query processing, and in-database analytics 4. Evaluate key-value stores and NoSQL systems, describe their tradeoffs with comparable systems, the details of important examples in the space, and future trends. 5. "Think" in MapReduce to effectively write algorithms for systems including Hadoop and Spark. You will understand their limitations, design details, their relationship to databases, and their associated ecosystem of algorithms, extensions, and languages. write programs in Spark 6. Describe the landscape of specialized Big Data systems for graphs, arrays, and streams
Relational Algebra, Python Programming, Mapreduce, SQL
Good! I like the final (optional) project on running on a large dataset through EC2. The lectures aren't as polished and compact as they could be but certainly a very valuable course.
Comprehensive and clear explanation of theory and interlinks of the up-to-date tools, languages, tendencies. Kudos and thanks to Bill Howe.\n\nHighly recommended.
Graph Analytics
Graph-structured data are increasingly common in data science contexts due to their ubiquity in modeling the communication between entities: people (social networks), computers (Internet communication), cities and countries (transportation networks), or corporations (financial transactions). Learn the common algorithms for extracting information from graph data and how to scale them up.
Graph Query Example: Recursion4:07
Evaluation of Recursive Programs3:52
Recursive Queries in MapReduce4:38
The End-Game Problem3:29
Bill Howe
So let's take a step back and see where we are.
We've talked about Graph Tasks in general, gave an example of constructing these
histograms, talked about structural, traversal and pattern tasks,
gave page rank as an example of both a structural and a traversal task.
And they talk about pattern languages and 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
So that's what I wanna do next.
We're gonna 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 page rank in MapReduce.
So way back towards the beginning of the course, we talked about how to implement
a relational algebra operations in MapReduce at scale.
And we showed the sort of connection between
languages like pig in relational algebra, what databases do or
is obviously relation algebra and what you can implement directly in MapReduce.
So there seems to be this kind of relational algebra DNA in a lot of these
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 feature of working with them.
And so it came up in traversal tasks, and
it came up in pattern languages, in Datalog.
We saw examples of recursive Datalog programs without talking much about
how they would be implemented.
So I wanna cover that a little bit now.
So, given if you have a recursive Datalog program that looks like this, so
you can say this 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.
Now here we have a vertex w.
And, put those in a new relation called A.
Then also, find the 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 data log program,
but what you can think about intuitively what it's doing is traversing this graph
in kind of a breadth-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 could write this in MapReduce.
We could write this in Python.
Find me all edges where the first position has a label equal to 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 might evaluate this recursive program.
That's what the meaning of this program is.
But there's a problem here.
What if there's a cycle in the graph?
Well, in generation one we find Sue, in generation two we find Tom,
in generation three we find Lin, and then in generation five we find Sue again, and
so you just keep going.
So we need one more piece,
which is to remove all the ones we've already found previously.