ble to work with it and writing all these specialized algorithms ourselves to traverse large and larger datasets becomes the bottleneck. And so a database can organize these algorithms and expose them through convenient mechanisms. We talk a lot about complexity hiding interfaces, right? Databases provide a complexity hiding interface for large scale data. And I think the fourth one is flexibility, which is, you might have written some software to access your set of files in a particular way, but as soon as you have to access it in some way you didn't anticipate, right?  And so what databases try to do is anticipate a broad set of different ways of accessing the data and working with the data and support all of them. Okay, and so I'm talking pretty abstractly here fairly deliberately because all of these things are certainly true of relational databases, which we'll talk about, but I think they ought to be true of anything that sort of earns the term database and they're certainly true of other systems as well. And so we wanna try to keep these things in mind when we think about no SQL systems and key value stores and graph databases and so on. Okay, so it's not just relational databases. This is broader than just relational databases. All right, and so I think in general, when you're looking at these different systems and thinking about the data storage layer, which is sort of where we're starting here in this conversation about data science and this course about data science, is how is the data physically organized on disk? You know, what kind of queries, what kinds of operations are gonna be efficiently supported by some particular organization and what kinds are not, right? So one immediate question, well, and this third bullet at least, or immediate question, is it hard to update the data or add new data? That's one quick way to split all the different operations you can do on the data. One quick one is the reads versus the writes. And in many cases, you'll find that what's convenient, you know, the organization that makes sense to read the data efficiently is not the same one that makes it efficient to write the data. And that trade-off is at the heart of a lot of the system design challenges in databases and other large-scale systems. Okay, but there's other kinds of operations as well as we discussed.  Do you wanna look up by some other field and so on? And we'll talk about this in future segments. Okay, and then what happens if I encounter new queries that I didn't anticipate? What do I need to completely reorganize the data? Do I need to write a bunch of new code? You know, how hard is this? And so this, these are the evaluation criteria you're gonna use when you're thinking about choosing a platform for your data science task. Okay, or these are some of the questions and they're perhaps not all of them, right?  All right. So last time we talked about data models and used them to motivate databases and define the term database in a broad sense. And now I wanna build on that to talk specifically about relational databases, okay? So last time we talked about these questions you could use to reason about different ways of organizing data and evaluate them with respect to your requirements. And I wanna talk about these questions and apply them to examples of different kinds of databases you saw in the past that end up motivating the relational model. And in particular, the reason I wanna go through this sort of historical view of things is that you see some of these same designs being proposed in terms of NoSQL systems and some of the same issues come up, both benefits and pros and cons are still there. So it's good to have a historical perspective on them when you're evaluating these modern systems that are becoming popular, okay? So the questions we talked about were, how is data physically organized on disk? You can ask this about a system. What kind of queries are efficiently supported? How do you update things? And so on. All right, so one example is what I'll call a network database, although arguably this is just sort of pre-databases where you just had files. And if you go back to our questions, you might ask, well, how is it physically organized on disk? Well, if you're using sort of parts and orders model here, you would have a order record and it would have an address associated with this order record that would physically point to the first part associated with that order. And that part would point to the next one and so on. Another field in the record would point to the customer that made that order, okay? So going back, what kind of queries are efficiently supported? Well, if I wanna find all the parts associated with an order, I can do that pretty efficiently. I have an access to, I have a given order and I just walk down this chain to gather up all the parts, okay? What kind of queries are not efficient, supported efficiently, is I wanna find all the orders that involve a particular part, although all the orders that involve this washer. Well, now I have to scan every order to look for them. Okay, there are some ways around that by putting back pointers and so on. Another problem with this file oriented, you know, sort of proto database model is that whenever I wanna make a change to the data, right? If I wanna have an extra field added to support the billing customer as opposed to the shipping customer. Well, I've just added a new field. I've extended the length of this record. That means that everything else below that record needs to be moved. More importantly, all the programs that navigate this structure now need to be aware of this other field. They all need to be rewritten to accommodate this extra piece of data, okay? Moreover, if you wanna support different access methods as we talked about, if I wanna look, say, by part and find all the orders, I end up having to make a complete second copy of the database. And now when I update, when I make a change to one copy, I need to make a change to all copies. And you can imagine how the space of possible copies might grow, might get pretty big. Okay, so a partial solution to this problem was this notion of hierarchical databases characterized by perhaps IBM's IMS system, which actually still exists and still has customers. And so here, the idea was to order, organize data in terms of segments. But still the logical model had this hierarchical flavor that we saw in the network model as well. So here I've switched, I've made the top level access the customer instead of order. And so logically what you have is that an order is only located underneath the customer and a part is only located underneath an order. However, given that they're in separate segments, I can make a change to one segment without having to break all the code that accesses other segments. The downside that still exists here though is that the programmer, the application developer still needs to understand this hierarchy in order to find anything. They have to actually know exactly how things are organized. For example, that orders appear under customers. So you still have to anticipate what kind of access methods your customers are gonna want and design for those. Updates here are a little bit easier given that I can add an order to one segment stored elsewhere without affecting all the other structures. And I can even add a field and I can only make changes to the orders as opposed to changing everything. Moreover, the software layers on top of this were able to sort of insulate from those kind of changes with some reliability. So this new field would only be passed back to the client when they actually needed that new field. So there's some measure of what I'll call data independence and we'll talk about that a little bit more in a few minutes. Okay, so moving towards relational databases, though one view of what a relational database really is is here I'm quoting Kurt Monash who's an analyst for the database industry. And he says, you know, relational database management systems were invented to let you use one set of data in multiple ways, including ways that were unforeseen at the time the database was built and at the time the first applications were written. And so I wanna emphasize here is that this is the key idea of relational databases, not SQL and not some of the other things you may associate with particular implementations. It's really just about organizing the data in such a way to support unforeseen access methods, querying in ways that you didn't anticipate when you organized it, insulating applications from changes. So what is a relational database? Well, at the simplest level, everything is a relation which is anonymous with a table. Everything's rows and columns and this probably doesn't need to be made explicitly but let me do so. Every row in the table has exactly the same columns, has the same number of columns but they also have the same types. So if a column is an integer in one row then it needs to be an integer in all the rows. And then a consequence of this model of everything being a table means that you don't have pointers anymore. You don't have physical addresses. All you have is tables. And so relationships between different data items are implicit. So instead of having the, so here we switched the domain to one of courses and students. So this table is a student takes, we'll say takes, a student takes course and this is a student record. Well, instead of having a physical pointer from the course record back to the student, we just have a shared ID. The only relationship between these two data items is the fact that they both have the same value in a particular column. And so this is, intuitively, this sounds really bad for performance right off the bat. If I wanna go look up all the students' names associated with a particular course, once I have my course, I need to go look up in this table all the values that match as opposed to just navigating directly to them which you could do with the hierarchical method. But if I wanna go the other direction, it's the exact same process. I look up the name, if I wanna find all the courses that a student has taken, right, I can do so the same way. I do have to do the lookups which maybe is a cost and performance, but the mechanism by which I look things up is the same in both cases. Okay. Moreover, everything is stored only once which is a feature that the hierarchical databases were able to achieve as well in most cases. Okay. But the network databases were not. We don't have multiple copies of things lying around. All right. So the philosophy here is being cute about this. The quote from the 19th century is that God made the integers and all else is the work as man. Well, you know, Cod made the relations which is a reference to Edgar Cod who wrote the first relational database paper and went on to win the turning award for his work which is sort of the Nobel Prize in computer science. Cod made relations and all else's work as man. So everything is a table is the number one thing to remember about the relational data model. Everything is a relation. All right. So let's actually break here and I'll pick up with this slide next time. 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 need 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, 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 is sort of motivating, sort of following on what the quote I used from Kurt 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 has changed and even when some aspects of the external representation are changed. And so the reason I want to emphasize this is that, again, this is the key idea of relational databases, not SQL and not some of the other features that you associate with particular implementations. It's really this notion of data independence. Okay. 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 hitting this so hard is that this idea is still just as important now as it was then. All right, so I want 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 a tabular, the 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 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 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 next segment. So 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 you're manipulating logical structures called tables. So just know the term physical data independence and know that it means that your programs you write to manipulate data are more robust than they would be without this relational model. So another key idea is that there's this algebra of tables that I mentioned. And we'll talk more about these are specific operators in a bit, but at a high level, 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 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, all sorts of set up operations derived from set theory, union and difference in 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's for software engineering purposes, it allows the database designers to focus on just implementing these operations efficiently. Okay. Now, if I could, if I had you on the classroom, what I'd ask is how many people have heard of the relational algebra and also asked how many people have worked with databases? And typically the number of people who've 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 this course is to equate the two, right? 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, when I'm giving a talk and describing using the slide, well, I'll also ask is 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 four. Okay. So one thing you might do is just well, say, well, you know, four times two is eight and four times three is 12. And so that's 20. And I add zero and that doesn't change anything. And then I divide by one. 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 one, or any integer by one 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 commutivity law that allows things to be reordered, I can simplify this expression down to this.  And I've done few 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're thinking about a computer evaluating this. Now, do computers use this kind of symbolic reasoning when they evaluate expressions over integers? No, the answer is no. And the reason 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're manipulating are not small integers, but rather terabyte size tables, then this kind of symbolic reasoning is not only valuable, but it's absolutely critical. If you do 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 algebra class. And that's why the term algebra is there. And they attempt to simplify the expression. Simplify, the reason I pause is it simplifies perhaps not the right word because it's not always true that the shorter the expression, the faster it is. We actually use this notion of cost-based optimization, which means we'll try lots of different kinds of 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 the magic trick of query processing in relational databases, and this is a really, really great idea. And the reason why this works is because we understand very formally what these operations are and what they mean. Okay, and so 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, 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 can impose a penalty. Okay, one final comment about this is, the term algebra is not just kind of trying to connote algebra from high school, it literally is the same thing. And 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, right? Now, that's the exact same idea that's going on when you talk about operations over integers 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, okay? 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, 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 gonna select other values from the same relation R, that's okay. I can have two different, 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 parentheses. 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 wanna 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 likely to be the cheapest one, and then we'll choose that one to run. And this is the kind of reasoning that all databases do internally whenever you write a query. Okay, so where are we now? So we've given an overview of data science itself, and one of the things we talked about was that there's this important aspect of, you know, data munging or manipulation, cleaning, restructuring, and so on that is perhaps, you know, ill-defined, but is kind of what keeps people up at night when they're working on data science problems. Okay, then we also gave an overview of relational databases, kind of a history of relational databases and why they came into being in the first place. And, you know, we found that the original problem being addressed was this one of physical data independence that, you know, when aspects of the data changed, all the applications broke. And so you wanted to insulate applications from certain kinds of changes. Okay, and one of the tricks here, the secret sauce of relational databases is this algebra of tables that allows you to reason about manipulation tasks, reason about data manipulation tasks, independently of the grubby details of the physical representation. Okay, so this idea will come up over and over and over again, even outside of the context of, say, you know, Oracle and Microsoft SQL Server and IBM DB2 and so on. You know, you don't have to be talking about a commercial flagship relational database system to make use of this relational algebra. Okay, and we'll see that. And so I wanna spend some time in this segment and probably the next few segments on understanding the relational algebra. And so, you know, at times this may look like more of a theoretical exercise, but I promise you it's not, right? There's an entire database course offered, say, here at the University of Washington and everywhere else that I think is a great idea to take. We're taking out segments of that that are demonstrably practical in a data science setting. Okay, so I'll also mention that many of the slides in the next segment or two came from the Introduction to Data Management course developed by Dan Ciccio and Magda Velzinska and is taught here at the University of Washington. Okay, so the relational algebra operators that we hinted at but maybe not listed out explicitly are these, include the set operations that are lifted to support relations and we'll see examples of that. And then the big three are selection, projection, and join. Right, and we'll talk about the meaning of those. And then there's these extended relational algebra operators that have to do with manipulating duplicates of tuples. And on the next slide, I'm gonna explain where duplicates come up and why it's important to make a different distinction between working when they're in the presence of duplicates and when there aren't duplicates. Okay, and these include just an operator to eliminate duplicates altogether. There's a group by operation that you may be familiar with if you work with SQL and this operator appears here and then you can sort and so forth. These are extended in some, these are also extended in the sense that I shouldn't have said just duplicates. It's also sorting, for example, doesn't deal with duplicates. It's extensions of relational algebra off of, you know, away from the pure set-based, set theory-based model. So for example, a set of objects doesn't have any kind of order applied to it. And yet we were allowed to sort things in SQL. Okay, and it's a practical, you know, it's something that's practical for applications to be able to define what kind of order the tuples come back in. But it's not part of the formalism. It was added in afterward. And so that's this extension between the pure relational algebra and the extended relational algebra. This is probably as close to the theoretical underpinnings that I'm going to care to get. The difference between these two comes up a lot when you're trying to prove properties about the formalism, right? Because the extended relational algebra is much more difficult to prove things about if you can at all. But as a practical matter, the difference between these two classes of operators is not particularly important. Okay. So the takeaway here is that there's a big set of, a meet, you know, a rich set of operators. But if someone says the relational algebra to you, the first thing you should think of is set operations plus selection projection and join. Okay. All right. So this notion of sets versus bags, the duplicate question. Well, so first of all, what is a set?  And so right up here, you know, A is repeated, is not repeated at all in a set, but it may be repeated in a bag. And whether that's legal or illegal is what gives you the semantics of a set versus a bag. So you can define the relational algebra in terms of these two different semantics. You can define it in terms of set or you can define it in terms of bag. And this notion of an extended relational algebra comes from the need to sort of work with bags as well as other things like sorting, as I mentioned. Okay. And so the rule of thumb here, I'm really gonna mention this. The rule of thumb here is that every paper you read, if you end up reading some of the papers if you talk about this course or beyond, will, you know, unless it's set explicitly, we'll assume set semantics. Okay. So be prepared for that. While every implementation, you know, every commercial database will assume bag semantics and we'll sort of see where that comes up in the language. Okay. So I just wanted to put that out there up front that, you know, I may play fast and loose with the difference between sets versus bags, but it can be important in practice. Okay. So one lifted set operation, you can define the union of two sets in the standard way. The union of two relations is natural given that a relation is a set of tuples. And in relational algebra notation, I would write it like this and I can also write it in SQL with the union keyword. And here's where set and bag will come up. If I want to, by unqualified, union does indeed remove duplicates, in which case the answer is of the, the union of this relation with A1B1 as a tuple and A2B1 and A1B1 and A3B4 is these three tuples. The duplicate of A1B1 didn't get passed through. To express this in bag semantics, to make sure we do include duplicates, you can say union all and that would include all four tuples. Okay. You can define the difference operation the same way, or in the same way in the sense that you're lifting it from the set, from the natural definition of over sets that find every set, every tuple in this set and remove any tuples that also appear in this set. And we see A1B1 as we saw before also appears in R1 and so you take, you get rid of it and all you're left with is this tuple. So why isn't this one in there? Well, if it doesn't, if A3B4 doesn't appear in R1, we know it's not in the set. All we want is everything that's in R1, removing things that also appear in R2, okay. All right, so what about intersection? That's another set operation that we could lift up. You can indeed define intersection, but you don't necessarily need to have it as a fundamental operator because you can re-express it in terms of difference. So if I want the intersection of R1 and R2, I can take everything in R1 that is not in R2 and then I can take everything in R1 that is not in that result. So if you think about this for a second, this expression returns everything that is only in R1. And then this expression overall removes everything that is only in R1, leaving things that are both in R1 and R2. And so that's what the intersection is, okay. And we'll touch on this later, but you can also express intersection in terms of join, which that operator haven't defined yet. Okay, the selection operator is how we take tuples that satisfy a certain condition. And so we write it with sigma and we put C to express the condition. This notation, honestly, we won't necessarily use too much throughout this course, but I think it's good to be familiar with it when it does come up. I'm more interested in recognizing the sort of English translation of these, select, union, join, and so on. The Greek notation is perhaps less important. Okay, so if we want to find where the salary is greater than 4,000 over an employee or where the name is equal to Smith, that's an instance of a selection operator. And the, let's see, it says the condition C can involve equals, you know, less than greater than equal to and so on, but it can be more than this, right? It can be any sort of Boolean expression. And in fact, as we'll see in maybe a segment or two, it can be sort of any arbitrary function that returns a Boolean value. So it doesn't have to initially just be a less than b or a equals b. It could be some complicated function. Okay, but let's say in between some complicated function that's user defined and a simple condition like this where you just say salary equals 4,000, or sorry, salary greater than 4,000, you can have arbitrary Boolean expressions. So you could have conjunctions. You could say where salary is greater than 4,000 and S name equals Smith. And of course you can say or and you can say not. All these are legal. Okay, so as an example, if we want to have a selection where salary is greater than 4,000 of an employee, which, excuse me, which one passed this test? Well, I've been saying 4,000 this whole time and that's 40,000, excuse me. These numbers look for a moment. So John has a salary less than 40,000 and so he can be removed from the set. And so the result of this expression is this table. We have tables in and tables out. The result of this expression is this table saying three columns and only two tuples in it. Okay, I guess sometimes I gesture here. I'm not sure you can see it when I light up. Maybe you can. Okay, a project operator eliminates columns and this is another one where you have to be sort of careful about set versus bag. So when you see a projection in the set semantics, you're going to remove all columns that aren't explicitly listed, but you're also gonna remove all duplicates that might remain. So if I project away all columns except for the last name, then you might think I get Bob Smith and John Smith and I get rid of first name. I'm left with two tuples or one tuple, right? Well, in set semantics, everything must be a set and so duplicates get removed automatically. In bag semantics, they'll both be there. And if you write this query in SQL and the commercial database, what you'll get back is two tuples, both Smiths. So you'll get duplicates. And then you can explicitly ask them to be removed with a different keyword called distinct. And we'll see an example of this. All right, so fine. So as an example here is project social security number and names. We only want two columns out of all the original columns that might appear in the employee table. All right, and so here's an example of the set semantics versus bag semantics. Here's the original table with three columns. And we project onto name and salary. And so that means we get rid of SSN. Well, now we have three instances of a guy named John and with three salaries. And the bag semantics would be okay without the set semantics would remove one instance of this duplicate. And so the question here is which one's more efficient? Well, removing duplicates is expensive. So just leaving them in place is more efficient. In fact, that's really the motivation as to why, one of the key motivations, why commercial databases assume bag semantics is that on every single query where you want to choose which columns you have, having an extra step to remove duplicates is sort of wasteful. In typical applications, you may not care. Or you may sort of know by domain semantics that the remaining columns are unique anyway. So you can tolerate duplicates. And so forcibly removing them just to be pure with respect to the underlying semantics of the formalism was not particularly necessary. So an operator that you won't hear much about but I do want to mention for a couple of reasons. One is that it's useful as a reasoning tool when you're thinking about manipulating tables. And then the other one is it actually is coming up more and more often in sort of analytics applications and data science applications. It didn't come up very often in traditional relational database applications. And that's this notion of cross product. And so a cross product here is for every tuple in R1, for every combination of tuples in R1 and R2 produce a tuple in the output. And so the size of this thing is the size of R1 multiplied by the size of R2 equals, here I'll just do it this way. Oops, do you think? All right, okay. So fine. So an example of where you might see this and sort of give you a flavor of why this is coming up more and more often is that you often want to find all pairs of objects that have some similarity condition. And while in any particular instance of this problem there might be tricks to do this more efficiently, the brute force method of just generate all possible pairs and then apply some function to determine their similarity is often used in practice. So for example, if you want to compare two images for similarity, you have two faces and you're trying to see if they're the same face and you've got a piece of code that can do this.  Well, generating all possible pairs and applying the function is always a reasonable way to do this, okay? So these kinds of operations are coming up more and more often. And I'm pausing because I was wondering whether to sort of mention briefly some of the techniques you can do to get around this, but I don't think it's gonna come through very well without a little bit more visual aid. So let me skip that for now. Okay. All right, so what does the cross product look like? Well, imagine you had a table employee with these two columns and a table dependent with these two columns. And we do a, whoops, there we do a cross product of employee with dependent. That's all possible combinations of employees with all possible combinations of dependent. So we know there's going to be four tuples in the output. And you can check to see that John is here twice, once for every instance in dependent and so on. So now let's talk about join and I probably maybe should have put a slide in here just about join in general first. So really we're talking about join. The most common instance of join that you're gonna run into. And in fact, if we don't qualify it, this is what we mean is what I'll call equa-join. And so equa-join is a join with an equality condition right here. Okay, so what does join do? Join says, for every record in R1, find me a corresponding record in R2 that satisfies some condition. And in general, especially for those of you familiar with databases, you're going to be thinking about in terms of equa-join. This would be for every course in student, if find me student IDs that appear in particular courses. Okay. So joins on primary key and foreign key, if you don't mind the jargon, are instances of equa-joins. They need not be, is one point I wanna make. So we're not talking too much about schemas in this course. I'm more interested in teaching about the relational algebra and showing how it comes up rather than teaching about how to design a database in the first place. And the reason for that is that, you often don't have the luxury, I made this point before, we don't have the luxury of a engineered schema. You don't have time to build one, you don't have, there isn't one handed to you in the first place. There perhaps isn't even much need for one in that you're going to get your answer to a couple of questions and then you might sort of move on to something else. So there's not really a way to amortize the cost of developing the schema in the first place and so on. So, if you've worked with databases, most of the joins you're doing are going to be along these predefined relationships that are called foreign keys, but those need not exist in order to apply a join. And then I'll point out just a sort of syntactic note, you can write this two different ways in SQL. You'll sometimes see select star from R1 join R2 on some join condition. And other times you'll just say, select star from R1 comma R2 where this condition is met. Now, if I literally translated this into a brain dead relational algebra plan, and we'll talk about sort of how to do this a little bit more mechanically in a bit, this is actually sort of saying, well, hey, look, first build the cross product of R1 and R2, right? And then filter that cross product such that this condition is met, okay? And this one is saying, no, no, no, don't do that. Actually, use the join operator rather than generating the cross product. But the optimizer, the databases are not that stupid, right? They're smart enough to figure out that even in this case, the right way to do this is to express a join. And so in practice, there's no difference between these two different ways of spelling the same query, okay? And in fact, to a first approximation, two equivalent queries, different syntax, but same semantics in SQL, there's not gonna be any difference between them. The optimizer doesn't care how you write your SQL. It's going to optimize the thing anyway. It's gonna turn it into a relational algebra plan and manipulate that plan to guess the best way to evaluate that query, okay? And so I say to a first approximation because there are such things as query hints and other ways you can sort of tell the optimizer how you'd like the query to be evaluated. We're not gonna talk about that because they're rarely important. And the other thing, it's not impossible to have two different queries that do the same thing that the optimizer can't figure out are actually equivalent. And so it's not impossible to get two different plans, but typically that won't be the case. And in this example, that doesn't matter at all, okay? Join versus in the where clause. I'll tend to write queries this way even when they come up, okay? Fine, so that's the most common and the simplest instance of this join operator. In fact, I think I did as a disservice here by doing this on left and right. This is actually kind of a nice example. This is the SQL equivalent of writing join and this is the relational, sort of the SQL equivalent of writing cross product followed by a selection, right? They're the same. In fact, the only reason why in the algebra, you know, remember the algebra has a formalism, you know, maybe you don't care so much about deriving new operators as long as you can express the thing, you know, it doesn't matter. There's so much work and there's so many good algorithms for implementing join that it sort of deserves its place as a specific operation. We don't wanna have to write cross product followed by a select when we're actually sort of talking about the efficient join algorithms, okay? So more generally, you can have what we'll call a theta join. And this is essentially just a join, but the condition here can be anything you want, okay? Rather than just an equality condition. This could be greater than or less than or arbitrary functions and so on, okay? And so this all pair similarity test that I talked about before is an example of a theta join. And we'll see a more detailed example in a second. And so just to point out that equa join itself is a special case of theta join where theta is just the equality condition. All right, so there's some examples of theta joins just to sort of demonstrate that these come up pretty often in practice more than you might be familiar with. And again, especially speaking to the people who are familiar, who have experience with databases, these are not going to be a long, foreign key relationships quite as often, right? Okay, so if you wanna say find all hospitals within five miles of a school, well, this doesn't immediately seem like a relational algebra query or a SQL query, but it kind of is, right? It's just a join where the join condition is this distance function over the location of the hospital and the location of the school. Okay, and then I did a projection here to sort of project out the name of the hospital because the English version of this seemed to suggest that we just want the name of the hospital and that's it. Okay, and so in SQL, this might look like this where you say, look, give me all combinations of hospitals and schools and then filter on the ones where the location of the hospital is less than five miles away from the location of the school. And here I'm kind of assuming that there exists some distance function that knows how to compute this. And we'll talk at the end about how new functions that are not part of the language or not part of relational algebra can be registered in the system and that's this notion of user-defined functions. But trust me for right now that these things can exist. Okay, and in fact, they don't even have to be user-defined. There's many functions that are already available in databases for manipulating, say, for example, strings. And in fact, even for geographic information, there actually are distance functions available in those commercial databases. Okay, so you'll see this structure. The takeaway here is that, I want you to still think join, right? Just because you don't see a quality condition doesn't mean there's not a join going on. It's just the same kind of join as everything else. And then the other thing, the other takeaway is just to know the term theta join in case that comes up, okay? Usually when anybody's talking about a theta join, what they mean is, you know, difficult joins, right? Arbitrary joins, the general case of joins. All right. So another example that's maybe you might just sort of be able to think about coming up in practice in your own work is, well, you know, find all the user clicks made within five seconds of some page load. And this is sort of much like the distance argument before, but now we can think about it in terms of time, which is just a one-dimensional, the one-dimensional district metric is easier to define. So we say, find the click time minus the load time of the page, right? So C dot click and P dot load and take that absolute value and see where that's less than five. And so this might be when you're trying to find people who find what they're looking for quickly, right? This is a metric that web analytics people might use frequently, right? If people sort of stare at a page for a long time, maybe if it's an article that might be good, it means they're reading the article. If it's a navigation page, it may be bad, it means they don't find what they're looking for quickly. You might also hear about band joins or range joins. And this is things like find me, there might be an interval of time, start time and end time in one table. And you're trying to find tuples from another table that fall within that interval. And we'll actually see an example of that. There's another join to recognize that it exists is this notion of an outer join. And here, what you're saying is you want all the tuples from the left, R1, R2, we'll write it like this with this sort of missing leg here. You'll want all the tuples from the left side if you've written it this way. And if the tuple on the right-hand side matches, great. You put it out and it's just like a regular join. But if there is no match, you still include the R1 tuple and you pad out the other columns with null as needed. Okay. So any value you don't have, make it a null. All right. And so the variants here that aren't particularly important is left outer join, right outer join. So, oops, geez. Left outer join, right outer join and sort of full outer join, which is a little bit hard to write because it looks like a cross product. The right outer join you really sort of never need because you can always just reorder the operations. Full outer join means that you want everything from both tuples padded out with null. And these are sort of ugly to reason about formally, but they come up pretty often in practice because especially for users, when they're, well, I'd say especially for users, as opposed to applications. You know, if you're writing a query by hand, basically, many times people find it surprising that records in their table disappear because they joined it with another table, right? But that can happen because you've said you only want pairs of tuples where some condition matches and so you might have no matches and things disappear. And so outer join comes up as a useful way to match more with the SQL programmers expecting, especially with novices, okay? And so an example of this, we have two tables here, anonymous patient and an anonymous job, we could do an outer join. Now, what columns did we join on here? Well, it doesn't specify, we sort of omitted it here, although technically we should write that, you know, right there in the subscript of the join operator, but we didn't, but of course you can probably figure it out. Well, so you look at the columns that they have in common, right? This has an age column and this has a zip column and this has an age column and this has a zip column. And so it's actually on both of those columns, right? For every tuple in P, find me a corresponding tuple in anonymous job J. Oops, there's an extra in there. Where age equals 54 and zip equals 98125, okay? So if we had just done a join, then this tuple would be removed from the output because it has no corresponding tuple on this side. There is no 3398120. But because we did an outer join, we do include the tuple and we've had it over the null here, okay? And we write this in SQL, I wish I had included this, we write this in SQL, let me back up a couple of steps here and I'll show you. So just like we have join here, you can actually write outer join explicitly, outer if you wanted to. I'm not gonna leave that in the slide because it'll be confusing since it's out of context, but up, and in fact you can say left outer join I guess to match our example. Okay, put in the slides. The database that you'll be using in the assignment is SQLite, which has some nice properties for a single user case. The entire database is stored as a single file and you can pass it around and so on. So it's a good tool to sort of having your toolbox. There's one of the reasons why I selected it for the assignments, but it actually has some limitations and one of which is it can't express certain kinds of outer joins. Okay, in particular full outer join. Okay, so now I wanna talk about how to interpret or get some examples of how to interpret SQL statements sort of in terms of relational algebra. We're not gonna actually write out the plans, but I wanna give you some experience staring at what may seem sort of complicated and kind of teasing out what's actually going on here. And so for people that have spent a lot of time around databases and SQL, these may or may not seem particularly complicated, but if you're just starting out, they probably do. So in this first example, what do we see here? Well, what you wanna look for when you're sort of staring at something that may seem sort of hairy is, look for the from clause here. And so in this case, it's a little funny, right? Because we see, oops, we see that the from clause does not have a table mentioned, it has a nested query within it. And we remember that that's perfectly fine because of this closure property of the underlying algebra. We know that any relational algebra expression and therefore any SQL statement you can return a table and it operates on tables. So if you can operate on table, if you're operating on tables and you know you return a table, then you can sort of chain these operations together and you have this nice closure property. So we know that we're allowed to query derived results just like we're allowed to query base tables. Okay, and so in this case, we're doing a derived result. Now, well, so let's go down to the other from clause. Well, here we see another nested query, another layer of nesting, again, perfectly fine. And one more layer down, we see this table here. And so where this data came from was a sensor that was mounted underneath a oceanographic research vessel that was collecting measurements of a variety of different variables. Here are a few of them are mentioned, fluorescence, oxygen, nitrates, and there's several more. And then this is latitude and longitude where the ship actually was located at that point in time. And they're also tagged with this timestamp.  And so what this operation is actually doing is aggregating, bending these measurements onto five minute windows. Okay, and so we can see how that's done. So in this inner query, there's some work to, or you call this function to cast the timestamp to a float that's not particularly important. And here we see this trick where we just use a constant value right there in the select clause. And so what that does is sort of a pin to new column with a value five for every record, okay? And I'll say maybe why this was done in this particular case in a moment. And then in the next layer up, we see this kind of hairy expression involving bin size twice. And what it's doing is rounding down the timestamp to the nearest five minute window, okay? So, you know, six minutes in 32 seconds becomes five minutes and 11 minutes in 29 seconds becomes 10 minutes and so on. Okay. And then in both cases, by the way, we see this star here, meaning that all other columns are gonna be passed through. And then finally the outer query we have bin ID, which we computed here. Notice that we've got this renaming operator where we can have this complicated expression and just give it a nice convenient name. So we got that passed through and then we compute the average of these other values, the average latitude and the average longitude within that five minute window as well, okay? So given that we're doing an average, we should expect to see a group by and in fact we do, we're grouping on the bin ID, which would make sense. And then we happen to be sorting by bin ID just to make sure that the record come out in timestamp order because perhaps some application requires it that way. Okay, so why is this sort of overly complicated? Why not just collapse all this into one expression? Well, you could, but it's for the same reason that you might sort of abstract things or refactor things in an imperative language. There's a little bit of software engineering being applied here so that this complicated expression can be reused in multiple places. In this case, it's only being used once, so you could perhaps move it there. But it sort of separates two different blocks of logic. Okay, so in this slide I've color coded the three different blocks of logic, red, blue, and green, so you can see the layers of nesting. But the main thing I want you to take away is that, one is that nesting is perfectly fine and you may see it and not to worry when you see it being used in practice. And second is to kind of convey that as you start to do more and more analysis in SQL, more complicated analysis, there are ways to kind of refactor the complicated queries so they don't necessarily look so complicated. Another thing you could do here that we will talk about in perhaps the next segment is save this result as a view, right? Give it a name and then you could refer to it in the outer query just as a table. Okay, and I'll talk more about that next time. But these are some of the tricks you can play when you're sort of working with in SQL. And in fact, you know, some of the things you may see people do even if you're not playing on doing as much SQL authoring yourself. Okay, fine. So here's another example. Same thing, the first step is to look at the from clause and see what you see. And here we see two tables and there's this keyword inner joins. Now the join is explicit and the join condition here is this where we have some sort of ID and some sort of other ID. By the way, one of the other things I wanna kind of do here is to show that you can kind of analyze the structure of a SQL statement to understand what's going on even if you really have no idea what the data's all about. And in fact, it's kind of helpful to do so. This is something you'll be presented with in a data science context as someone will say, look, we need to predict what the average sales for next month is gonna be. And you say, okay, great, give me the data. And they'll say, well, I don't know, it's in some database over there. And you'll go over there and talk to the DBA or maybe there won't even be a DBA.  And so that means staring at the schema which we haven't done, but it also means staring at certain people at queries, which you may not have written, okay. So having a little bit of a skill of analyzing these complicated queries can be important. Okay, so fine. So this looks ostensibly like the join condition, but if you look at the where clause, I wanna make sort of a point here that the table referred to as X, this hotspot deserts, and the table referred to as W are involved in additional conditions down here. Okay. And so these are actually join conditions as well. Right, even though this one was explicitly listed as an inner join on this particular condition, anything that involves, anything that applies a condition to attributes that are in both tables, right. Any sort of condition of all the attributes from both tables is a join condition. And so this whole thing is actually one sort of complicated join condition. All right. So I went a little bit out of order into a little bit different than the order I wanted to go in, but let me backtrack and come back to that. So hold that thought. Popping back up to the top, this other piece of complicated logic here. Well, this is a particular syntax that's available in SQL called a case statement, and it acts about the same way as a case statement in other languages. So that's not too bad. But in particular, even if you just ignore all this logic, you can just collapse all this down and say, well, look, there's some function that's computing Lynn overlap. And where did I get that name? Well, that's what they name the result of this complicated expression, the length of the overlap. And in fact, I happen to know a little bit about where this query came from when they're working on his genetic sequences. And you may be able to deduce that if you could stare at this. There's SNP region, which stands for single nucleotide polymorphism, and there's strain that may give you a hint, and BP is base pair, and non-coding regions, non-coding positions gives you a bit of a hint if you've done any work in bioinformatics. But if you haven't, that's okay. Point is, length of overlap appears to be the name of this thing. So it's almost like there exists a function, linked overlap that involves these attributes, and we don't even care what's inside it. It's just a function. So that helps us sort of see the underlines implicitly of this query in this case. Okay. Then, back to this other complicated expression. Let me show you a little bit about what's going on here just because I think it's kind of a fun example. If you break these out into these three conditions, and you happen to know something about where this data is coming from, you can see that what this is saying is, well, look, we want the start base pair from the X table to be greater than the start base pair from the W table, and we want the end base pair from the X table to be less than the end base pair from the W. So it's this picture, right? What the blue X interval, right? It's a sequence. The X table is filled with ranges, right? Start and end ranges, intervals, and the blue interval needs to be completely contained within the red interval, you know? Or the red interval needs to be completely contained within the blue interval, or the red interval needs to straddle the X start base pair, which you can do if you stare at this condition. Okay, so they're doing kind of an interval logic right there in SQL. And so the point of maybe looking at this in enough detail to understand what's going on is a couple of things. One is this point about the joint condition is that it's not, you know, even if you don't understand what's going on, you can sort of see the structural details to understand that it's just a joint condition. But also that you can actually do certain kinds of analytics directly in SQL. This is a fairly non-trivial operation to do that many people, especially among people who have either not had good experience with databases or have heard from their friends who have not had good experience with databases, that this would be something that's considered sort of impossible. And it's not impossible, and nor is it really even a bad idea. It's actually kind of a natural thing to do. And so analytics in the database should be a part of your bag of tricks. You know, the first step should not be let's pull everything out of the database and then start using imperative code. Okay, this example alone, I would hope doesn't convince you of that claim I just made of, you know, getting things out of the database is a good idea, but there's gonna be a sequence of arguments that I make probably throughout the quarter here and there. Okay, meanwhile I should put the caveat that this is not, you know, I'm not gonna be pushing databases as the ultimate solution to data science but by any stretch of the imagination. But there is a role for it to play. Okay, all right. And so now with these, you know, we collapsed this into one function. We can also collapse the joint condition into these two things. It must match on this CHR field and then it must have this kind of overlaps condition be true that we saw on the last slide. And so this is just an example of a theta joint where there's some non-trivial function being applied on each pair of tuples. Okay, let me stop there and pick up on user-defined functions next time. Okay, let me add a short addendum about user-defined functions. So we've seen a couple of examples of them and in fact I'll click back here briefly. We pretended that there existed a user-defined function called overlaps and a user-defined function called the length of the overlap. And I wanted to point out at least in this context or especially in this context that you can indeed define these kinds of application-specific operations. Okay, so they're called UDFs and you can, as a user, you can write one of these things. You can register it in the database and then you can call it from within your SQL statements and you can assign it, you can grant permissions for others people to use it as well. Okay, so the database becomes kind of a repository of user-defined functions that can be called from anywhere. And so there's three types to be aware of. One is scalar functions, the other is aggregate and the third is table functions and you can tell what they are by how they're used within the SQL statement. So a scalar function will appear pretty much anywhere any expression can appear. So if you can add two attributes together or you can subtract them or do any kind of arithmetic, you can apply a function. So this can appear in the select clause or can appear in the where clause or can appear in a join condition. It can appear sort of anywhere an attribute can appear. Okay, an aggregate function appears in the select clause only and is always associated with a group by. And so here I've kind of indicated perhaps a common aggregate function that users define when it's not available built in and often this one isn't is concatenate. So if you have a table of identifiers and words and you want to concatenate all the words together to make one long string, that's not always something available built in but it's a very natural thing to wanna do, right? So I've got a set of small strings and I wanna create one long string. Well, concatenation is something that's very easy to do in most programming languages and that's how you would express it in SQL. You would do a group by, right? You say, this example's a bit abstract to maybe go through live by waving my hands a lot but if you've got some grouping attribute which defines a set of related strings, maybe I wanna concatenate them all together. And so you might define a user defined function to do this concatenation built from a string primitive that's just a pin to pin to pin. You know, if you have a function that concatenate two strings you can build a user defined aggregate that concatenate many strings, okay. Fine, and then table functions appear in the from clause and they're arguably the most complicated. So the most common example you'll see here is some kind of a table function that will allow you to define a sequence of, excuse me, a sequence of integers. So sequence from five to 10. If you wanna represent all the integers from five to 10 as a table, you know, one thing to do is actually physically create a table on disk and insert those integers into that table but that's a little bit wasteful, right? Because we sort of know what that sequence should be. We don't actually need to physically store it. Five to 10 may be not so bad. They're trying to store the integers from one to a million. It can get worse. And so a function that knows how to generate these on the fly can be useful. And so you'll see table functions be used in this way. Now, well, I think this will appear on the next slide, actually. So support for these are pretty comprehensive. All databases have them with unfortunately a notable exception being SQLite itself which is the one you're using for the assignments. So I encourage you to go out and look at other databases. In particular, Postgres and Green Plum which is a commercial database that is parallel and based on the Postgres code base has really, really excellent support for user-defined functions. SQL Server and Oracle IBM all also have great support for it but Postgres has a particularly clean interface and was really designed way back when with extensibility in mind. So it was one of the first, originally there was a research project and one of the main goals of the research project was to show that an extensible database was a good idea. Things where you could add your own functions, add your own types, add your own features in various ways. And so in particular, support for manipulating time data, timestamps is quite nice there. Okay, so you can define these user-defined functions in a variety of languages including pure SQL and you may have to sort of scratch your head to think about why that would be a good idea but the short answer is that it's the same reason why defining functions is a good idea in any programming language, right? It's this notion of abstraction, okay? And reuse, okay? And then there's programming language, imperative languages that are extensions of SQL and Microsoft's got one called T-SQL and Oracle's got one called PL-SQL and Postgres has one called PL-PG-SQL that adds things like we'll run a query and save the result in a variable and then reuse that variable later or we can define variables of just primitive types like integers and reuse those. And there's usually also looping constructs and conditionals and every other kind of feature you might have in an imperative language, okay? So these come up and they're useful and if you were a database administrator or you have friends that are database administrators, they're going to be very familiar with these languages. I'm not typically a big fan of using them not because I don't think they're a good idea but because I find them to be overused, I think there's things you can do without having to drop down into writing imperative program that are not always recognized. The other reason I don't like to use them is not for any kind of fundamental reason just because the experience of writing code in these languages is actually kind of painful. They're difficult to debug because they're not great support for debuggers. When things go wrong at runtime, they're sort of hard to figure out what's happening and so on. And so while I complain a lot when I see SQL logic being pushed into the application layer, I complain less when the alternative is to do it in one of these imperative extensions to SQL, okay? So don't put your joins in the application but you can put your loops, okay? So fine. So in Microsoft SQL server, any kind of CLR language from .NET can be used and they're typically in C sharp and so on. Python, there's an R extension to Postgres that I haven't had much of a chance to play with yet but that's kind of exciting because it gets the folks that are interested in using databases with their statistics routines a much more compelling argument of how to do so. Okay. So that's what I wanted to say about that and we'll see examples of user-fine functions come up in a few different places and most importantly, they'll all use the term and so I want you to know that the term comes from databases and what I mean is things, just any kind of code that is not provided by the system itself. All right. Okay, so we talked about algebraic optimization and then we talked about decorative languages on top of the algebra in order to simplify expression and in order to avoid specifying to the computer exactly how to do it, right? We're gonna leave that open and let the database figure that out but we stopped at what I'll call logical optimization and what I wanna talk a little bit about the physical level optimization and what I mean by this is that even after you specify we hinted at this last time but even after you specified the order of operations we haven't yet specified every detail needed in order to actually evaluate the query. Okay. And let me give you an example of that. So here's a simplified version of a query we looked at last time where we say for every order we wanna find all the corresponding items that were part of that order and that's it. Last time we had an extra condition. Oops, I'm actually clinking with the mouse but you can't see that because I'm on the wrong screen. So for every order find the corresponding items that match and the last time we had another predicate down here and this time I've taken that out. And so the algebraic plan that this translates into is very simple. It's just a join of the two tables and that's it. So you think we're done, right? We're gonna join, order an item and we're finished. Well we gotta specify how we're gonna do that join and so let me tell you about a couple of the options here. So one in sort of very high level pseudocode looks like this. We could say for each record I in item and for each record O in order, check to see if those two records agree on the order fields, on the order attributes and if so return it and that's a join result. Okay. You know they match. So fine. Another option is for each record I in item, insert that record into some sort of data structure and here I'm gonna call it a hash table. Now I'm not too concerned about what exactly that is. And then second for each record O in order, go look up the corresponding records in that data structure that we found or that we built and return all the matching pairs. Okay. And if it actually is a hash table that we're talking about, then this look up could be pretty efficient, right? It could be constant time, amortized constant time, right? And so now this one says, well for every record in item, go scan every single record in order. And so we have kind of an in squared complexity going on here and here we say, well for every record an item put into a data structure and then after that for every record in order, go look up those records in the hash table. And if indeed this is constant time amortized, then this is a sort of linear time algorithm. So there's two different ways. So I argue that there's two different ways to implement this join that both of these are valid. Okay. So which one is faster? Well, I've sort of hinted that perhaps option two is faster, but in practice it may or may not be. And so, you know, I would pause here and ask the class to answer the question, since it's over a video, I can't do that. I'll give you a moment to think about that. But I want you to think about why this one or in particular might be faster in some cases than this one, even though it seems like it shouldn't ever be. Okay. And let's see an example maybe in a second. So leaving that question hanging open, I wanna make the point that you have access to this underlying algebra. This isn't something that's purely sort of theoretical, right? This is something that you can use tomorrow if you work with databases at your job. For example, in this particular product, Microsoft SQL server, and in fact in all the products, you're gonna use the same sort of mechanism, but you can explain a query and that will give you access to some form of this algebra that I've been talking about. Okay. So if you take a query and here I've changed the query, I've changed the schema yet again, this table, this Reuters table is one you'll be working with in the homework. I've written a query here and I've explained it and what shows what the SQL Management Studio gives back to me is a little algebraic tree, kind of like the ones I've been drawing here just in PowerPoint. Okay. And so this one says a hash match is gonna be used to implement this join condition. This one's kind of a complicated join condition for a reason I'm not gonna explain right now, but it has two leaves and then they get joined with this thing called a hash match inner join. Okay. And so this is very much like the hash table example I gave on the previous slide, but I want you to take a look at something. So here I've taken the exact same query, but I've added an extra condition where I'm only looking for words equal to parliament. And I probably should explain this schema a little bit. So the Reuters data set gives you term frequencies. You have three columns, doc, ID, or let's just say doc, term, and frequency. How, and the frequency is how often that term appears in that document. Okay. So this is the table you'll be looking at. Right. And so here what I've said is I'm looking for pairs of terms that co-occur in a single document is the previous query I was looking at. And now I've said, well, look, I don't want all pairs of document or all pairs of terms. I only want terms that co-occur with the term parliament. Right. So this lawyer co-occurs with parliament frequently. So I'm looking for all the terms that co-occur in some document with parliament is what this query is expressing. Okay. So now what I want you to notice though, is that when I explain this query, I get a different physical plan. The logical plan looks the same. It's still got scan, scan, and a join, but the algorithm to compute the join has changed. And now it's this nested thing called nested loops. And that nested loops corresponds exactly to this pseudocode here. That's why they call it nested loops, the outer loop and the inner loop. So exactly the same thing. And so it chose to do this nested loops plan, even though we argued that it was an in-squared algorithm and it probably wouldn't be chosen very often. So why was it in this case? So if you think about it, the one of the sides of this join is only dealing with those terms or with the occurrences of the term parliament in a document, which is a very small relation. And so it's a very small relation and this nested loops algorithm could be very, very efficient and faster than dealing with the overhead of actually constructing this hash table or constructing some data structure. Okay. So the main takeaway here, as opposed to the details, is that different physical algorithms are appropriate at different times and that this decorative language and thanks to the decorative languages and thanks to algebraic optimization, the programmer doesn't have to worry about any of that. They don't have to make that choice. Okay, so this is a very, very powerful idea. You just express the query and the database does the rest. All right. So fine. And just to point out, this is not just something you need to SQL server. You can generate these kind of algebraic plans in Postgres by using explain. And in fact, they look kind of nicer and here's these hash joins again. This actually shows you, whoops, excuse me. This shows you where it's building the hash table as the step one and then probing it with the step two and same thing here. And this is another operator that we didn't talk about where you are, say you're going to count all the records that match some, count all the members of some group. I'll put it that way. And so the hash here is on group ID and you can apply your functions to the rest of it. But I shouldn't give such a high level of view of that or without talking about it more. So let me skip that all together. Okay. So fine, so the algebra really does exist. You can look at it directly just by using the keyword explain. And I advise you to do so. If you work with databases, you should be using explain all the time to try to understand what's going on. All right. Another point I'll make is just that this matters. This is not from directly from SQL and in fact, it's not from a commercial database. It's from some research that we do in my group. But the point is the same here. These are actually different physical plans for the exact same query. And in fact, here I'm doing something in parallel. So this is actually number of processors being applied.  They should be sort of going down quite a bit. But the point is that each one of these plans is doing a very different amount of time. Well, these two are kind of the same, but the difference is pretty important. So ignoring these opportunities and sticking with only the plan that the programmer specifies would be a big mistake. Okay. And then another illustration of this that's a little bit hard to stare at, but let me give it a whirl to try to explain what's going on here. This is by some very nice work by Haritza at all at VLW 2010, but there's a whole series of papers on this work. They try to visualize the space of possible query plans. And so what the two axes are here, this is all for a single query, but the parameters to that query are changing. And so this in fact says something about the supplier account balance. And this is a parameter on the sort of extended price and they change the values of these parameters in the query. So imagine the same syntax, the same select star from something, something where some condition equals extended price and some other condition equals account balance. And just by varying those two knobs, you get this really rich tapestry of different plans being selected by the optimizer. So each color in this space represents a different query plan, a different algebraic query plan selected by the optimizer. Okay. And so I think that the takeaway here is just that it's a very complex decision being made by the databases and necessarily so. They actually, these different plans actually matter. They don't show that here, but you can actually show that this choice of plan tends to, the database didn't do a pretty good job of finding the right plan. And that, I argued in the last slide that this can actually matter. The difference in the time can be pretty significant. Okay. So leaving this kind of complexity up to the programmer can be a big source of loss, right? Hiding this complexity is a huge, huge, huge win. 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 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 tuples 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 you will talk about it in like this, in this segment I think. But the idea, the takeaway here is that there's three equivalent expressions and we don't know necessarily which ones, which one is the fastest one to evaluate. But the database can figure this out and does every time you write a query. Okay. And that's this notion of algebraic optimization. Now, we don't, you know, even if you're 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 algebra 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, right? 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 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 gonna let the database figure out the right order in which to do this. And so here's 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 records such that this condition is true, where the order column from the order table matches the order column from the item table. And further, I only want orders from today where order.date equals today. So this is just conditions expressed over the results without any kind of idea 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. Here I've sort of just done a cartoon where you can say scan the item table, scan the order table, select the records such that date equals today, and then perform the join, find all the records in order that correspond to the, that have court, you know, for each record in order, find the corresponding records and item that match on order. Okay. So this is happening every time you run a query again. So the SQL is the what, not the how. Give them another example. Here's three columns, product, purchase, and customer. And there's the underlining here we haven't talked about, but this is the indicating what makes the table, what makes these records 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. So here's another SQL query. We say select distinct product name. Why do I know it's the product name? Cause I see an X here and I see an X here. And the customer name, and I know it's the customer name cause I see a Z here and I see a Z here. This is an alias 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. It's like that should be Z. So maybe change that on your own slides. Yeah, let me see if I can fix it now. Z.CID. And then we want, but now we want only the products for which the price is greater than 100, and we only want the customers whose city is Seattle. All right, so what does this say in English? Well, if I meet combinations of products and customers, unique print combinations of products and customers where the customer is in Seattle and they pay for a product worth more than 100, okay? So it's clear what we want, but it's unclear how to get it. It's kind of a complicated query, okay? So translating this into relational algebra, we have this. So at the bottom we have product and purchase, and now we do this join where we say for every product, find me the corresponding records in purchase, then we do another join for every record in the result of this join. Find me the corresponding records in customer, right? Now filter out all those records such that 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 then finally 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. 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 gonna do the join exactly, and there's multiple ways you can do it. I've indicated that we're gonna take for every record in product, we're gonna look up a corresponding record in purchase, but we haven't said precisely what that means. Okay. I'll give an 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 work with RDF data, the resource description framework. And 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, you can encode in RDF. You can say, the instructor of this course is Bill Howe. So here the subject might be this course, the predicate is has instructor, and the object is Bill Howe. Okay. And so people use this formalism as a very general way of encoding any information from any source. And we might touch on this much later in the course. Okay. So here's kind of a complicated query. But what it says is, I'm gonna have three instances of the same relation, and I'm gonna join each, I'm gonna join them all up. And I'm gonna look for a sequence of tuples 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. All right, so you're looking for this sequence of, where this root edge is knows, and this edge is holds account, and this edge is account homepage. So find the all possible combinations in this table where I've got, you know, find me all A, B, all instantiations of A, B, C and D such that this pattern matches. Okay. And all lines are specified by these conditions. The object of the first relation must be this, it 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 I'm looking for patterns in the graph that look like this. And in relational algebra, you see 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 account, 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 out the final answer that we're interested in, which is a slight clause. Okay, so perhaps a complicated example, but I think the takeaways here, I wanted to mention RDF, because it might 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. Okay, so we talked about physical data independence, and we talked about algebraic optimization. I want to talk about another kind of data independence, which is logical data independence. And so, we argued that physical data independence was this ability to insulate applications and protect applications from changes in the physical organization of the data. All right, so things were rearranged on disk. We don't want to have to rewrite all the code in the application. And this is what databases provide, and relational database in particular do a great job of providing this. But if you go back to Ted Codd's first paper, and even the quote I gave you, he talks about insulating applications from the internal changes to the internal representation, but also insulating applications from changes to some forms of external representation. And what he means by external is things like adding a column to a table. So this isn't an internal shuffling of the bits on the disk. It's actually a logical change to the table. There's more data there than there was before. But if you think about it, if your code doesn't care about that new column, you shouldn't have to rewrite it just because there is a new column. Okay. So the ability to provide this logical data independence is provided by this concept of views. And all relational databases have this concept. And somewhat surprisingly, I find them to be somewhat underused in practice. Right? And well, okay. So if you're using them right now, if you know what they are great, if you're using them even better, if you use databases but have never heard of views, then this is a great time to learn about them. Okay. So what is a view? A view is just a query with a name. So I write a query, I give it a name, and I put it in the database. Now, I can then access that view as if it was a table in the underlying database itself, as if it was a physical table. So why can we do this? Well, I talked about this notion of algebraic closure before. Right? And here, and this is exactly what empowers, what allows us to do this. So we know that every query returns a table, right? We take tables on the input, we do some manipulation of them and we produce tables. So we say that the language is algebraically closed. And so any result of a view will always be something that we can then add other queries on. So we can stack queries on top of queries on top of queries on top of queries. Okay. So why might we wanna do this? So one reason is to protect the underlying data. You can assign permissions to tables. So for example, if you only want a particular user to see data associated with their account, you can write a view that filters everything out except for their account and then grant them access to that view. The most direct benefit of this is that it allows you to expose data according to a logical organization that makes sense for the user. So even things as simple as hiding some join. If you decide to reorganize your data into two tables, requiring that programmers use joins to link them back up again, you can simply write a view that hides that join and let everyone access the result of it. Now, maybe this may sound expensive, but the cool trick here is that because of this algebraic closure, what happens is the user's query gets composed with your query that defines the view and the whole thing gets sent as one big block to the database for evaluation. So the database simply doesn't care whether it came as a view in the user query or whether it came all as one query directly from the programmer. It's gonna optimize it the exact same way. Okay, so there's nothing but a benefit here. Okay. So let's see an example. So given the schema purchase and product, define a view called store price with two columns store and price that has this definition. So select store and select price from purchase and product where the product IDs are equal. This is a little funny because we didn't put pids here. So this is a little bit wrong. So assume that each one of these has a, let's assume that this is PID and assume that this is also PID and then it matches the query down here. Okay. So this result is now like a new table and just like I said a second ago, you've now hidden the join from the users. And so complexities like these column names perhaps, you can insulate your users from and you can name them whatever you want. And so this allows you to put this, this is what this logical data independence means is that even no matter how I wanna logically organize my tables, I can expose a different perspective on the data than I wanna have myself. And so this separates the people who are administering the data from the ones who are actually accessing it. Okay. Logical data independence. Key idea. All right. All right, so how do we use a view? Well, as I've said, all you have to do is reference the view in a query just like it's a table. And so here, if we wanted to find the notion of a high end store and we say, well that's any store that has sold some product to over a thousand dollars. And you know, for each customer, we may wanna find all the high end stores that they visited. Well, being able to directly reference the store price relation that we defined in the previous slide, this view, helped simplify this query, right? And so you can just write a query that directly accesses that view as if it was a table. And okay, so how is this actually evaluated? Well, that's actually, oops, that's actually what's really fantastic about databases is that this query will just be folded together with the view definition and pass to the database where the whole thing is optimized in one go, optimized in one go. So you don't need to worry about the difference between having a stack of five views and all being compiled together or all being folded together as one query. The database doesn't care. It's gonna translate the whole thing into one big query, exchange that for an algebraic expression and then do the normal optimization procedure to come up with the best possible plan. So it's basically like free abstraction, right? It simplifies things for the programmer without any kind of performance cost. Okay, now you can actually get better performance than writing the whole thing by hand. It's equivalent to writing the whole thing by hand. You don't pay a penalty but you can actually do better than that with views in some cases by materializing views. And we're not gonna talk too much about that because it's sort of very specific to databases and we don't see it quite as often in this broader context of data science that we're trying to talk about. But it's a good trick and once you have the mechanism to store views, you can essentially cache the results and that's what we call materialization. Okay, so the last key idea I wanna convey about databases is that of indexes. So while indexes are certainly not unique to databases, databases are perhaps unique as a platform that can make them very easy to apply and deploy and automatically take advantage of. And so databases are especially but not exclusively effective at sort of needle in the haystack problems, looking up individual records or small amounts of records from large data sets. They do other things very well too but this is one thing that they're quite good at. And the reason is that they can apply indexes. This second part is a little bit of context but what I mean here is that if you're trying to write code to do this yourself in say some programming language like Python or C or R, you're going to be a slave to what sizes of data fit into main memory as we said before. Now, you can absolutely be clever and start bringing in one chunk of data at a time into memory, processing it, putting it out to disk and bringing in the next set and so on. But the code will very quickly become very, very complex. This is something that databases already know how to do. And so your query will always finish regardless of database size as long as it fits on disk. It doesn't matter how much memory you have available, it'll eventually finish. It may or may not be that fast but it'll finish. They already know how to take advantage of main memory in this optimal way. And it's not easy, right?  So effective use of the memory hierarchy, effective use of indexes, these are things that databases can do well. It's a great platform for applying these tricks. And so finally, what I mean here is that the indexes are easily built and automatically used by the optimizer. So to create an index, you can write a statement like this. Here I've changed the schema on you once again. But here we're sort of filtering on genetic sequences. And if I create this index, then this query will, this very simple query is looking for all sequences that match a particular value. It will automatically take advantage of that index if it's there. You don't have to tell it to do anything. You write the exact same query, okay? Welcome back. So this time I want to talk about what this term scalable means. We made the point that working with really large data is important aspect of data science. And we've mentioned the word scalability before. We haven't talked about really what that might mean. So a couple of different ways to think about it that I want to talk about here on this slide are here. So operationally, and in the past, one way to think about this was look, it needs to work on data that doesn't fit in main memory on a single machine, okay? So maybe you still only have one machine to work with, but this means that if you need to be able to bring data off of disk in pieces, operate on it, and then maybe write it out in pieces, okay? And so a bundle of algorithms that could work on data in this fashion by bringing in data piece by piece to memory, such that the memory footprint at any given point was small. This is something the database has provided, all right? So you could write a query and you knew for sure that it was gonna finish as long as the data was there on disk, and you had sort of a minimal amount of memory, at least to get started, okay? But, and I might use the term out-of-core processing here. So out-of-core means it uses the disk to operate. So in-core means the entire, everything you're doing fits entirely in main memory, out-of-core means you need to sort of work with the disk appropriately. And so databases were, the database community were specialists at out-of-core processing of large data sets, but increasingly this notion of scalability wasn't really enough, okay? And so you saw this pretty acutely with websites that were coming online in the 2000s where one big server, no matter how big you bought that server, you couldn't bring data off of disk fast enough to meet all the requests. And so you had to start being sure that things were in memory, and the only way to do that is to start adding more machines, okay? And so increasingly, especially, you know, Google especially is sort of known for this, although many of the large media companies do this, is that scalable really kind of means being able to use up to thousands or maybe even more, tens of thousands of cheap computers and apply them all to the same problem. And so we might call this scale out while getting bigger and bigger and bigger main memory and more and more cores perhaps would be scale up, fine. So another way of looking at this that maybe is a little bit more precise is to think about this kind of, in terms of algorithmic complexity that you may or may not be familiar with if you know how much computer science you've taken, but let me give you just a flavor of what's going on here. So in the past, you might call an algorithm scalable if given in-date items, your algorithm does no more than in to the M operations on it, okay? So this may be in M maybe one, in which case it's a linear time algorithm or maybe two, in which case it's a quadratic time algorithm and so on, but this was deemed, you know, tractable, right? And so you'd prove properties about, you would prove that you could find a polynomial time algorithm to solve some problem and it was sort of thought to be scalable or assumed, you know, well, assumed. That was the definition of what scalable was. Things that were non-polynomial that took more than this, for example, exponential, where you might have M to the N, were exponential time algorithms and they grew much, much faster and they didn't scale, okay? But, you know, this isn't a very tight bound on scalability in practice, right? A quadratic time algorithm may be sort of feasible. You start getting into the fourth and so forth that becomes pretty difficult to do for very large data sets, okay? So now you would say that it really can't just be into the M, it's gotta be into the M over K over some, for some pretty large K. So you have to have a lot of K being the number of computers you can apply to the problem and so you have to come up with an algorithm and they can really exploit this properly, okay? And then one more point that I'm gonna make now but we're not gonna return to in this segment but I hope to at the end of the course is that it could be that soon, even this isn't good enough and for in-date items you really should do no more than in log in operations and so the in here means for every data item that comes in over the wire. So this is applicable to sort of streaming applications and the data is coming in so fast that you only get one pass at it. So for every operation I have, I'm allowed to process that data item and then I'm allowed to put it in some sort of an index and that's this log in factor, okay? And so whenever you see log you should think trees. So I'm allowed to take each item, inspect it and work with it and then stick it into some tree data structure but that might be about it. It's just too big to make multiple passes at, okay? And so examples of this might be this large synoptic survey telescope that we heard about if it's taking sort of 30 terabytes a night you can't sort of make too many passes on this data at one time, okay? And so this whole area we think of as streaming data which I guess I have written here but I'll write it again. And we'll come back to some of the techniques for dealing with big data in a streaming context. Okay, so fine. So two different views of what scalable might mean and we're gonna talk in this segment to give you some examples and some intuition for this. Can we make use of lots of computers in this in over K? Okay, all right. So here's a little example problem that's admittedly somewhat oversimplified. So we wanna find all the matching DNA sequences where a set of sequences is a short string consisting of the letters G, A, T and C and you're given a short sequence and you wanna find all the ones that just exactly match that, okay? So finding all the sequences that are exactly equal to this one that you're given. So how much you do this? Well, with this little cartoon imagine that each one of these black lines is a sequence. All right, so this black line corresponds to this sequence and this black line corresponds to this sequence and all the other black lines are other sequences. And, you know, think to yourself for a minute, propose an algorithm to find sequences matching your target sequence, okay? We'll make you know assumptions about the data whatsoever. It's just given to you as a list. One thing you can do is do sort of a linear search. And so we're going to inspect the first item and we're gonna compare it to our target sequence. And if they're equal, great, we found one. And if they're not equal, what do we do? Well, we move on to the next one. So this is not equal and this all happens at time equals zero. And then we move on to the next one. And so at time equals one, we check another sequence and compare it for equality and if it doesn't match, we keep moving on. And so on and so on until we get to time 17 where we find a match. And here I've said contains instead of equal. I guess I changed the meaning here. But so yes, we found a match and we sent it to the output. Okay, so how long does this take? How many operations do we do? Well, we did 40 records. I'm sorry, we are given 40 records in this cartoon and we made 40 comparisons. And so with in records and in comparisons, we say that the algorithm of complexity is order in. Okay, so this is a linear time algorithm for this simple search and retrieval task. So the question is, can we do any better? And if you've had some experience thinking about data structures, taking some data structures classes, you should be thinking, yes, we can. All right, so one way to do this is to sort the sequences. So how does this help? Well, certainly we could still do the linear time algorithm and inspect these guys one at a time. But we can also do something a little bit smarter. What if we start in the middle? So start in the middle and compare our target sequence to the sequence we found here. And they're not equal, but we can see that this one that we found is less than our target sequence. Okay, so we know that the sequence that we're on is to the left of our target sequence. We know the target sequence is to the right. Right, it must be somewhere in this direction. So we've just removed the need to check half of the data, right, 20 records. Okay, so now jump to the middle of this guy and compare again. And now we see that, well, boy, we overshot, this one is greater than this one. Well, once again, let's see, here we've removed half of these guys on the first step, and here we now we've removed half of these guys. And now we know it's in this range. Skipped it a half again. And compared this one and now it's less than, so we're sort of bouncing back and forth around our target. Let's see if I can draw this a little better than I did. Cross those out. Cross those out. Now cross these out. And so we know it's somewhere on this side. And in the next step, we find a match. Okay, and here if we have multiple copies of the same item, we know that they'll appear next to each other so we could just walk through the records gathering up all the ones that match if we needed to. Okay, so how long did this take? Well, here we still have 40 records, but we only made four comparisons. Right, so with in records we made login comparisons. We navigated this sort of implicit binary tree. We did a binary search over the sorted data. Okay, and so this lookup was order login. Now we did have to sort the data ahead of time and if you have to include that then that's an in login operation that we're not gonna necessarily talk about. Once you have that sorted data available to you, it's now, it takes login operations. And so this is perhaps far better scalability. And this is a good trick, and it's such a good trick that it's been baked into many systems, especially I'll argue relational databases. And we made this point before, but I wanna make it again, is that databases are good at these kinds of needle in the haystack problems, right? Distracting small results from big data sets, they can transparently provide this sort of old style of scalability. What I mean by old style scalability is that it fits in main memory as we've said a couple of times. Your query will always finish regardless of the size of your main memory. In addition, you can, it makes an excellent sort of index platform, a platform for building and using and reusing indexes. Okay, so relational databases are good at this old style scalability in the sense of out of core algorithms. And they're also good at this old style scalability in the sense of finding logs, right? Finding logarithmic time algorithms. So indexes are easily built and automatically used when appropriate. And we've talked a little bit about this during relational databases. You can write a single statement, create index, give it a name on a table and a column name and it will sort records according to that column. The actual data on disk may or may not be physically sorted depending on the details of which system you're using and how this is working. And typically in this statement, it would not actually be moving the physical records around but it would build an auxiliary index. But regardless, you get to take advantage of this logarithmic time access pattern. Okay, and so just by writing this one statement in one line of code, you can create the index and take advantage of it. Okay, and then every query that comes afterward that needs to use that, that would benefit from using that index is able to. The optimizer automatically selects the correct index if it's appropriate to use. So this is much easier than you having to sort of rewrite your code by hand in order to either make it out of core, right? Or to take advantage of an index. Okay, so when you're comparing relational databases to say scripts in R or scripts in Python, there's a lot of algorithmic work that's already been done for you that you're getting for free just by turning your problem into a SQL statement. Fine, so you're buying into a lot of code if you can tie one arm behind your back and write it as a SQL statement. It's not just SQL versus, versus a much more expressive language like code. You're actually getting a lot of benefit out of doing though. Okay, so let's look at another task called read trimming. So here we're given the same set of DNA sequences, but instead of searching for one particular sequence, we're going to trim the final few base pairs from each sequence. Okay, so we're gonna trim off a suffix and return the data set where each read is now just a prefix of a former read, okay? So fine, so how do we do this? Oh, and the reason why you need to trim off the suffix is it actually comes up in practice and the reason is that the accuracy of the sequencer drops off fairly abruptly after a certain length of read and trimming off the last several base pairs from every single read is kind of a standard pre-processing operation. Okay, fine, so how do we do this? Well, we can do the same trick that we tried the first time with the search task, meaning that we can process each record in turn one at a time, right? So at time zero, we can trim off the suffix here and just return TACCT and in time one, we can trim off this suffix and so on. And in time 17, there's our old friend that begins with GTA and so on. But here, unlike the search task, there's no index that's really gonna help us, right? We have to touch every single record and manipulate it, right? We have to take a prefix from it and remove the suffix. And so the operation is fundamentally order in, right? There's not gonna be an algorithm that is less than order in, right? You have to at least touch every single record. Okay, but can we do any better? Well, yeah, right? Processing the first task is completely independent from processing the last task, which is completely independent from processing this task, and I keep saying task, processing the record, okay? So while there's no index, we can break this data set into pieces and process each piece independently, okay? So imagine we take our single data set and break it into these chunks and assign each chunk to a different machine or maybe a different processor to be a little bit more general. Now at time zero, we can process one sequence from each chunk all at the same time. And at time one, we process the second sequence from each chunk all at the same time and so on. And so here, how much work did we do? Well, we did the same amount of work. We still processed all 40 records, but how much time did it take? Well, it only took seven, I say cycles here, seven time units to be a little more general because we were given these six workers. And so the complexity here is in over K, right? For every item we can divide, we do on average, or for in items we do in over K, time steps were completed to work, okay? Last time we talked about scalability and we argued that scalability really means working in parallel. And we talked about this specific task, which is, you know, read trimming, okay?  And we sort of showed that this is pretty simple to think about in parallel. You would divide the set of reads into chunks and put them all on separate computers and process them all in parallel here.  And you can apply this function in parallel and you can get out the data set you want, which is a set of trimmed reads, okay? So let's see some more examples. So a new task that was actually needed to be performed at the New York Times in 2008 and they have a couple of blog posts about it that you can read was, you know, simplified version was to convert a bunch of TIF images into a different format. And what was really going on here is that they had digitized images from the newspaper along with some information about the optical character recognition. So some extracted text and they wanted to turn this into a more web-friendly format. And so they had to convert the images to a web-friendly format. And they also had to convert the extracted text into a little package of JavaScript code, okay? So they're gonna get ready to put this stuff on the web. All right, so this is 405,000 images, which was quite a bit, especially at the time, okay? But the schematic looks sort of similar, right? You take a big set of TIF images and you split them into chunks and put them on a bunch of different computers and you have a function F that converts a TIF to a PNG and does the other work too, let's say.  And they're distributed across these machines, fine. So let's look at another example, right? So now we wanna run thousands of little simulations. And what we have are the parameters to each one of those thousands of simulations. And so an example of this at the URL here at the bottom of the slide is from simulating muscle dynamics. And this comes up a lot. You have these Monte Carlo simulations that need to do, they understand sort of phenomenons stochastically by running lots and lots and lots of simulations with different kinds of different inputs and then kind of averaging the results, okay? As opposed to modeling everything precisely. So now you wanna run thousands of simulations. Well, you have a set of inputs of parameters to these simulations and you break them into chunks and put them all on separate machines and apply the function. And here the function is actually running the simulation. And what you get out is the output of the simulation distributed across all the machines. Okay, so there's, you know, a pattern should be emerging here, right? So another example. So imagine each one of these little bars is a document and your task is just to find the most common word in every individual document, okay? Well, same thing, distribute the documents across the K computers and then your function F now in this case opens up a single document, figures out which word is the most common in that document, right? And just produces that word. And so now you have a big distributed list of pairs where, you know, the first part of the pair is the document ID and the second one is the word, okay? So that could be useful, but it's a bit contrived. You know, consider a slightly more general program that computes the word frequency of every word still in a single document, right? So instead of just finding the most common one and producing that, now you're gonna produce an Instagram of the frequencies of every word in the document, okay? So given this input, you produce all of these items, right? A set of items. The only reason I'm making this distinction from the last one is that the last one took a single document and produced a single word. Now we're taking a single document to make it clear that that's allowed, okay? Hope this animation isn't here, but I don't think I'll bother fixing it. So you have millions of documents, you distribute them again, now your function returns a set of word frequency pairs, right? But that's okay. And now we have lots of little lines here, each line representing a single word, let's say. So they're not one to one anymore, but that's no problem. The function just returns a set of things. All right, so fine. So there should be a pattern here, right? We have a function that maps a read to a trim read. We have a function that maps a tiff image to a PNG image. A function that maps a set of parameters to the simulation result, right? It's the simulation itself. We have a function that maps a document to its most common word. And we have a function that maps a document to the histogram of its word frequencies, okay? So, so good. So these kinds of tasks we think we know how to do in parallel, given a big set of objects and a function that knows how to process a single object, you know, you should be able to think about how to parallelize this, right? I'm giving you a brief, but we can abstractly understand how this is done, right? So, let's say that one more time. We have a big set of objects, we have a function that maps a single object to the other computers. The objects among the computers have a function that's in parallel. This is trivial. Okay, so what if we want to compute the word frequency across all documents, not just set a frequency for each document, or set a frequency for a single document, okay? So here, you know, if we have these three documents, now we want to get a single histogram that counts up the number of times the word people appears across all three of them and the number of times the word government appears across all three of them and so on. So, let's go back to our schematic here, the pattern. Well, now we want to compute the word frequency across five million documents and we can still distribute them among K computers, you know, so far, so good. And then for each document, we return a set of word frequency pairs and now I've switched the notation here from F to MAP, since we can consider this a MAP. That's the terminology I used. Okay, but now what do we do? All right, so what we could get out here, what we will get out here is a set of frequencies, but that's not what we want. We want a one big histogram. And to build this one big histogram, we have to make sure that a single computer has access to every occurrence of some particular term. So if the word history appears in some document on this machine and it appears, you know, twice in this document and three times and two times in documents on that machine and so on, we have to sort of group those all up and send them to a single place just so we can count them. Okay, so let's look at this again. So if we distribute the documents across these computers, we map, apply our map function to each document in order to produce a set of word frequency pairs and now we have a big distributed list of these words and sets of word frequencies. And now we wanna get these workers involved in the process and these guys are gonna be the ones who count the occurrences of a particular word. Okay, and so imagine all these little colored red lines are occurrences of words such that all the red lines represent a single word, occurrences of a single word and all the green lines represent a different word and so on. Well, so these guys are gonna get sent to their respective locations. So such that this worker is in charge of handling all the occurrences of the blue word and this worker is in charge of handling all the occurrence of the red word and so on. Okay, so now instead of lines that go, you know, from one to one, we have lines that go from this one computer to a bunch of different computers. Okay, and so on, right? So it's just sort of shuffle the data to spray this data out across the network in order to regroup it now, fine. So now that we have the data grouped the way we want and partitioned the right way, we can apply another function which I'll call the reduce function which in this case it doesn't mean very simple it just counts them and that allows us to produce our final result which is, oh, there are four green words and four red words and three blue words and so on. Okay, so now the schematic looks a little different. We have a sort of a two step process. So we start with some large set of objects distributed over a bunch of machines and then we want to apply some function F to each one of those objects and that was our first step but then the output of those functions are all going to be redistributed across the network and grouped to form groups, okay. And then the second step is to process each one of those groups. So I'll write, instead of F, I'll write map here and I'll write reduce here, okay. And so that's exactly what map reduce does and we'll explain this in more detail next time but the key idea here is that the user, the programmer is going to write these two functions a map function and a reduce function which are serial and what I mean by serial is they're not parallel. You don't have to worry about how to manage, how to program a distributed cluster within each one of these functions. You just write a function map that takes in an object of some kind and returns some other object and I'm not using objects in this sort of object oriented sense here, this is sort of in the mathematical sense, just any sort of input to produce any kind of output, okay. And then the reduce function takes a set of objects which I'll note this way and returns some other kind of object and actually this can be a set of objects as well and in fact this can be a set of objects as well. So maybe I'll switch colors here. This can actually be a set of things and this can actually be a set of things. So for example, we saw a document returning a set of word frequency pairs. But you can think of it, it's honestly important to understand what's going on here. Okay, so this is an interesting hypothesis, right? That perhaps all distributed algorithms can be expressed as sequences of these two step operations, right? A map followed by a reduce and then maybe more map reduce, map reduce, map reduce as needed, okay. And we'll talk about that in more detail next time. So last time we talked about parallel processing as a lead up to map reduce and we ended up with this schematic here in the context of this example where we're counting words across a set of documents which is sort of the canonical example to start thinking about programming and map reduce. And so each one of these vertical black lines represented a document and we split them into smaller sets and send each one of those sets to a separate machine and then we applied our map function to each one of those documents in turn. And so if the map function, if you recall, took a single document and produced a set of pairs and each pair was a word along with a count of the number of occurrences of that word in that document. There are variations on this that you can imagine, okay. Now this word may have appeared in multiple documents, one here, one on this machine, one on this machine and so on. And so now we need to group them all together onto a single machine so that we can count them. And that's exactly what this shuffle phase did. Okay, so here I've written four different tasks processing sort of looking like it's processing a single group at a time. But, you know, no one should think about how many map tasks do we, how are we gonna have and how many reduce tasks are we gonna have? Well the map tasks are one per document. We have to call the map function. How many invocations of the map functions are we gonna be? Well we're gonna call it once per document. How many invocations of the reduce function are we gonna be? Well it's the number of groups that are produced by the output of the map function. In this case it's once per unique word appearing in any document, okay. And so in some sense the number of machines we need to apply to this problem is maybe kind of predictable in the map phase. It corresponds to the size of the input data set which we presume to know. But the number of reducers we're gonna need is maybe not known ahead of time, right. It depends on the size of the map output. Here we might be able to reason about it because we maybe know how many words there are in the English language and we can assume that with a big enough set all of those words will be represented at least once. But in general it's dependent on the output of the map so you don't really know, okay. And so the only point I wanna make is that we made a decision here to draw it as four different machines. But it may be the same six machines use the map phase it may be 1,000 machines and so on. Nothing's stopping you from sending all of the word occurrences to a single machine and having this one machine process the green group then process the red group then process the blue group and so on. Or maybe you would do four at a time because there's four cores in the machine, okay. But that wouldn't be as perhaps as efficient because it would be doing a lot of serial work. At the other extreme you might think, well we're gonna need millions of tasks let's allocate hundreds of thousands of machines to process them so that each machine is doing very little work, okay. And that might make sense but then the trade off is perhaps sort of spinning up all these machines and preparing them to do the work, okay. So there's a decision to make there and we'll come back to that, okay. But let's talk a little more about MapReduce itself. This is, I'm belaboring this for a reason because what I want you to do is start thinking in terms of MapReduce. Every problem you have, think what if the dataset was absolutely enormous, way too big for a machine, how are we gonna split it into pieces? And a very good way of thinking about how to split things into pieces to think about how you'd write a MapReduce program to do whatever it is you're trying to do. And so this is, yet again the same example just drawn in a different way. So here the input is document ID followed by a value and the value here is the entire text of the document and the map function, just to make this clear, produces a set of things, not just one thing. Then they're shuffled to produce this. So this is word one with a count of one, word two with a count of one, word three with a count of one and so on. And then on the other side what we get is word one with a group of all the occurrences, one, one, one, one, one, one, one, one. And then finally the reduce function counts them all up and finds that there's 25 occurrences, okay. So I'm probably, because if this is completely obvious you can always fast forward. I guess one of the beauties of doing this online. Okay. So fine. So what is MapReduce? Well, that's the programming model we just described and there's a paper in 2004 that's on the reading list that describes this. And there's a couple of key motivations for doing this in that paper that I think sometimes get lost when you hear about the popularity of MapReduce today. And we'll talk about those two benefits in a moment. So one thing to realize is that MapReduce refers to the abstraction and it's the name given to it by the authors of this 2004 paper. Hey, Dup is an implementation of MapReduce that came a few years later and was written by some people at Yahoo originally and then became an open source product that is managed by the patchy and has lots of contributors. Okay. So the key idea for MapReduce was really this programming model, which it says here, right? Now, it had a system with it as well, but the programming model being able to express lots of different tasks and have some sort of implementation automatically turn that into a parallel job turned out to be pretty powerful, right? This was an attractive way to write parallel programs. Again, because you didn't actually have to worry about the parallel. All you did was write a serial map function and a serial reduce function and the parallel wasn't happened for free. And so the evidence that this is not so much about the system as it is the programming model is that you see MapReduce implementations appear in other contexts. There's people who have implemented MapReduce over GPUs. There's a little bit of MapReduce on multi-core machines in shared memory. There's people who have implemented MapReduce on high-performance computing platforms on groups of mobile phones and so on. This goes back to one of the motivations for this course where I want to focus on abstractions where possible as opposed to tools. We're talking about MapReduce, the programming model, but we'll spend a little bit less time on the specific implementation at Hadoop, although you will have a chance on an optional assignment to work with Hadoop directly. Okay, so fine. So what is the data model of MapReduce? It's this bag of key value pairs. I mean my bag is a set that might have duplicates in it, and so we've seen that before. The document ID with the value, that's a key value pair. Sometim