1 00:00:00,012 --> 00:00:09,640 [MUSIC] Okay, so, let's talk about relational databases. 2 00:00:09,640 --> 00:00:12,649 So the history here is that, which I motivated last time, I hope, is that 3 00:00:12,649 --> 00:00:16,015 pre-relational, if your data changed in some significant way, if you needed to 4 00:00:16,015 --> 00:00:20,405 reorganize things in some way, your application broke. 5 00:00:20,405 --> 00:00:24,358 Okay so if you changed the parent child relationships in the hierarchical model 6 00:00:24,358 --> 00:00:28,193 or if you pretty much did anything with the network or file oriented model, you 7 00:00:28,193 --> 00:00:34,085 ended up, your applications had to be rewritten to support that, okay. 8 00:00:34,085 --> 00:00:38,045 And so early relational databases addressed this issue and even though they 9 00:00:38,045 --> 00:00:41,765 were buggy and sort of slow they required only about 5% of the code you had to 10 00:00:41,765 --> 00:00:47,070 write previously and so this was an enormous win, okay. 11 00:00:47,070 --> 00:00:50,669 And so this quote, this sort of motivating us, sort of following on what 12 00:00:50,669 --> 00:00:54,573 the quote I used from Curt Monash in the previous segment is from the original 13 00:00:54,573 --> 00:01:00,148 paper on databases from Ted Codd. So activities of users at terminals and 14 00:01:00,148 --> 00:01:03,268 most application programs should remain unaffected when the internal 15 00:01:03,268 --> 00:01:06,492 representation of data is changed and even, excuse me, when even when some 16 00:01:06,492 --> 00:01:10,820 aspects of the external representation are changed. 17 00:01:10,820 --> 00:01:13,952 And so the reason I want to emphasize is that again this is the key idea of 18 00:01:13,952 --> 00:01:17,300 relational database is not SQL, and not some of the other features that you 19 00:01:17,300 --> 00:01:21,470 associate with, with particular implementation. 20 00:01:21,470 --> 00:01:23,905 It's really this, notion of data independence. 21 00:01:23,905 --> 00:01:27,450 OK, and this was the, right there in the abstract in the original paper. 22 00:01:27,450 --> 00:01:30,887 This is the key idea. And then, and the reason I'm in, hitting 23 00:01:30,887 --> 00:01:35,122 this so hard, is that this idea is still just as important now as it was then. 24 00:01:35,122 --> 00:01:37,326 All right. So I'm going to go through some of the 25 00:01:37,326 --> 00:01:40,318 other key ideas that were that are associated with relational databases, 26 00:01:40,318 --> 00:01:43,380 whether or not they were in the original paper. 27 00:01:43,380 --> 00:01:46,890 So one key idea is that programs that manipulate tabular, that manipulate 28 00:01:46,890 --> 00:01:50,400 tabular data exhibit this algebraic structure that we can use to reason about 29 00:01:50,400 --> 00:01:53,802 them and manipulate the logical model independent of any physical data 30 00:01:53,802 --> 00:01:58,287 representation. So what I mean here is that if you think 31 00:01:58,287 --> 00:02:01,389 in terms of tables, and you think about the operations that tables support, you 32 00:02:01,389 --> 00:02:04,491 can think about how, what your program means, and even how to optimize it, which 33 00:02:04,491 --> 00:02:09,609 we'll show. Regardless of how the bits are actually 34 00:02:09,609 --> 00:02:12,810 organized on disk. And this is, you know, incredibly 35 00:02:12,810 --> 00:02:15,262 powerful. Okay. 36 00:02:15,262 --> 00:02:18,813 So, the key idea here again, is physical data independence, and we'll talk about 37 00:02:18,813 --> 00:02:23,676 what logical data independence means, too, in the, in the next segment. 38 00:02:23,676 --> 00:02:27,186 And so you know the programs that you write to manipulate things no longer have 39 00:02:27,186 --> 00:02:31,476 to sort of manipulate files and sort of chase pointers around. 40 00:02:31,476 --> 00:02:35,094 You can in this case access it through a high level language SQL although again it 41 00:02:35,094 --> 00:02:38,803 doesn't have to be SQL. The point is that your manipulating 42 00:02:38,803 --> 00:02:41,345 logical structures called tables, alright. 43 00:02:41,345 --> 00:02:44,432 So just know the term physical data independence and know that it means that 44 00:02:44,432 --> 00:02:47,568 your programs you write to manipulate data are more robust then they would be 45 00:02:47,568 --> 00:02:52,771 without this relational model, right. So another key idea is that there's this 46 00:02:52,771 --> 00:02:56,875 algebra tables that I mentioned and we'll talk more about these specific operators 47 00:02:56,875 --> 00:03:02,376 in a bit but at a high level you know. One operation on the table is to select 48 00:03:02,376 --> 00:03:07,060 out rows that satisfy some condition. Another is to ignore columns that you're 49 00:03:07,060 --> 00:03:10,739 not interested in. Another one is to, for two tables, for 50 00:03:10,739 --> 00:03:15,155 every record in a, in the first table, find corresponding records in another 51 00:03:15,155 --> 00:03:19,190 table, right? Select, project, and join, and there's 52 00:03:19,190 --> 00:03:22,490 other operations you can define as to aggregation also to set up operations 53 00:03:22,490 --> 00:03:27,380 derived from set theory, union and differentiating cross product and so on. 54 00:03:27,380 --> 00:03:30,613 And so these operations if you write your expression out in terms of these 55 00:03:30,613 --> 00:03:34,129 operations. It's very clear what it means, and it, 56 00:03:34,129 --> 00:03:38,338 it's, it's for software engineering purposes, as it allows the database 57 00:03:38,338 --> 00:03:44,993 designers to focus on just implementing these operations efficiently, okay? 58 00:03:44,993 --> 00:03:47,907 Now, you know, I'm be, if, if I can, if I join a classroom, what I'd ask is, how 59 00:03:47,907 --> 00:03:51,103 many people have heard of the relational algebra and, and also ask how many people 60 00:03:51,103 --> 00:03:55,726 have worked with databases. And typically, the number of people who 61 00:03:55,726 --> 00:03:59,106 have worked with databases is very high and the number of people who have heard 62 00:03:59,106 --> 00:04:02,486 of the relational algebra is somewhat lower and that's one of the things I hope 63 00:04:02,486 --> 00:04:07,150 to fix, in, in this course is to equate the two. 64 00:04:07,150 --> 00:04:09,754 Right, if you, if you, if you understand databases I want you to understand 65 00:04:09,754 --> 00:04:13,065 relational algebra and vice versa I guess comes for free. 66 00:04:13,065 --> 00:04:15,635 Okay. So why do we care about this algebra, why 67 00:04:15,635 --> 00:04:19,028 am I saying algebra? Well you know, what I, when I'm giving a 68 00:04:19,028 --> 00:04:23,124 talk and I'm using the slide, well, I'll ask you, how many people have heard of 69 00:04:23,124 --> 00:04:27,798 algebraic optimization? And typically, very few have, even if 70 00:04:27,798 --> 00:04:32,080 they're computer scientists, unless it's a room full of database people. 71 00:04:32,080 --> 00:04:34,690 But the thing is, that you already understand what this is, right? 72 00:04:34,690 --> 00:04:36,460 You don't have to know databases to know what this is. 73 00:04:36,460 --> 00:04:41,570 This is just something you learned in high school in Algebra class, okay. 74 00:04:41,570 --> 00:04:45,434 So forget tables for a second. Just think about integers. 75 00:04:45,434 --> 00:04:53,825 Well, I've got this expression here. And I want you to evaluate this 76 00:04:53,825 --> 00:04:56,758 expression when I tell you z is equal to 4. 77 00:04:56,758 --> 00:05:01,470 Okay, so one thing you might do is just well, say, well you know, 4 times 2 is 8 78 00:05:01,470 --> 00:05:06,258 and 4 times 3 is 12 and so that's 20 and I add 0 and that doesn't change anything 79 00:05:06,258 --> 00:05:12,870 and then I divide by 1, fine. But if you're clever, you might notice 80 00:05:12,870 --> 00:05:15,570 that, well adding zero to any number doesn't change it at all so I'll just 81 00:05:15,570 --> 00:05:20,566 ignore that altogether. Similarly, dividing, any number by 1, or 82 00:05:20,566 --> 00:05:25,970 any integer by 1, is the same number, so I'll ignore that as well. 83 00:05:27,620 --> 00:05:30,425 And then, if you're really clever, you might notice that there's a 84 00:05:30,425 --> 00:05:33,791 distributivity law, here, that says, when I see this pattern, I can pull out the 85 00:05:33,791 --> 00:05:37,728 multiplication. And, by applying these rules in turn, 86 00:05:37,728 --> 00:05:42,220 including commutativity law, that allows things to re-, reordered. 87 00:05:42,220 --> 00:05:45,470 I can simplify this expression, down to this and this just says well now 2 plus 3 88 00:05:45,470 --> 00:05:50,085 is 5, just multiply 5 times 4 and I get 20 and I've done fewer operations. 89 00:05:50,085 --> 00:05:53,221 I've only done two operations instead of five and I didn't have to do division 90 00:05:53,221 --> 00:05:56,210 which is potentially an expensive operator if you think about a computer 91 00:05:56,210 --> 00:06:00,957 evaluating this. Now do you know, do do computers use this 92 00:06:00,957 --> 00:06:07,930 kind of symbolic reasoning when they evaluate expression over integers? 93 00:06:07,930 --> 00:06:10,336 No, the answer is no. And the reason is, is that this kind of 94 00:06:10,336 --> 00:06:13,372 symbolic reasoning is much, much more expensive than just evaluating the damn 95 00:06:13,372 --> 00:06:17,422 thing, right. So fine. 96 00:06:17,422 --> 00:06:22,102 But if the objects that you are manipulating are not small integers, but 97 00:06:22,102 --> 00:06:27,250 rather terabyte sized tables, then this kind of symbolic reasoning is not only 98 00:06:27,250 --> 00:06:33,766 valuable but it's absolutely critical. If you things in the wrong order, if you 99 00:06:33,766 --> 00:06:36,518 do wasted work, or you do more operations than you need to over massive tables 100 00:06:36,518 --> 00:06:40,340 you're dead in the water and you'll get nothing done. 101 00:06:40,340 --> 00:06:43,390 And so, all databases, all relational databases, rather, do this kind of 102 00:06:43,390 --> 00:06:46,340 algebraic optimization when you write a query. 103 00:06:46,340 --> 00:06:49,050 Right? And so, if you think in terms of SQL, if 104 00:06:49,050 --> 00:06:52,400 you're familiar with SQL, your query gets translated into a relational algebra 105 00:06:52,400 --> 00:06:56,280 expression, in terms of selects and projects and joins. 106 00:06:56,280 --> 00:06:59,910 And then, is manipulated, according to algebraic rewrite rules, just like you 107 00:06:59,910 --> 00:07:04,790 learned in in algebra class, and that's why the term algebra is there. 108 00:07:04,790 --> 00:07:08,877 and they attempt to simplify the expression, I simplify, the reason I 109 00:07:08,877 --> 00:07:13,366 pause is it simplifies is perhaps not the right word, because it, it's not always 110 00:07:13,366 --> 00:07:19,550 true that the shorter the expression, the faster it is. 111 00:07:19,550 --> 00:07:22,770 it's we actually use this notion of cost based optimization which means we'll try 112 00:07:22,770 --> 00:07:26,036 lots of different equivalent expressions, assign each one of them an estimated cost 113 00:07:26,036 --> 00:07:30,890 and choose the one with the lowest cost. And this is something that all relational 114 00:07:30,890 --> 00:07:33,490 databases are doing in one form or another okay. 115 00:07:33,490 --> 00:07:37,900 So fine, so this is this is the magic trick of query processing in relational 116 00:07:37,900 --> 00:07:42,550 databases and this is a really, really great idea. 117 00:07:42,550 --> 00:07:47,368 And the, the reason why this works is because we understand very, formally what 118 00:07:47,368 --> 00:07:52,540 these operations are and what they mean. Okay. 119 00:07:52,540 --> 00:07:55,548 And so when you, when you relax this formal model, and start allowing anybody 120 00:07:55,548 --> 00:07:59,040 to write any kind of code they want over the data. 121 00:07:59,040 --> 00:08:02,200 You lose the ability to do this kind of algebraic optimization. 122 00:08:02,200 --> 00:08:05,440 And you leave it up to the programmer to write the best possible algorithm. 123 00:08:05,440 --> 00:08:08,292 And what I'm hinting at here is well, we'll talk about it more later but when 124 00:08:08,292 --> 00:08:11,466 you think about writing large-scale data processing pipelines in something like 125 00:08:11,466 --> 00:08:14,502 MapReduce and if you haven't heard of MapReduce, don't worry, we'll talk about 126 00:08:14,502 --> 00:08:19,060 it. You're leaving all the work up to the 127 00:08:19,060 --> 00:08:23,592 programmer to not only write the logic but also to do the optimization. 128 00:08:23,592 --> 00:08:28,700 And this, you can take, you can impose a penalty. 129 00:08:28,700 --> 00:08:32,660 Okay, one final comment about this is the term algebra is not just kind of trying 130 00:08:32,660 --> 00:08:38,380 to connote you know, algebra from high school, it literally is the same thing. 131 00:08:38,380 --> 00:08:42,475 So when you hear the word algebra, what you should be thinking of is this notion 132 00:08:42,475 --> 00:08:46,696 of algebraic closure, and what I mean by that is every operation that applies to a 133 00:08:46,696 --> 00:08:52,250 table also returns a table. And so I can chain these operations 134 00:08:52,250 --> 00:08:57,012 together to always get tables, alright. Now that's the exact same idea that's 135 00:08:57,012 --> 00:09:02,297 going on when you talk about operations over integers or, or real numbers. 136 00:09:02,297 --> 00:09:06,457 And you might sort of quibble and say, well if I divide an integer by some other 137 00:09:06,457 --> 00:09:10,820 integer, I may get a real number and that's true. 138 00:09:10,820 --> 00:09:13,970 But there's notions of multi-sorted algebras with different types involved. 139 00:09:13,970 --> 00:09:17,628 But the point is that this notion of closure, you can't escape the system by 140 00:09:17,628 --> 00:09:22,705 applying operations, is, always true when you hear the term algebra. 141 00:09:22,705 --> 00:09:27,334 So we're not making things up. Fine, so here's some relational algebra 142 00:09:27,334 --> 00:09:29,794 expressions that if you squint hard enough, you can see kind of look like 143 00:09:29,794 --> 00:09:32,746 similar expressions over integers, except instead of addition and multiplication, 144 00:09:32,746 --> 00:09:37,682 we have things like joins and selects. And so what this says, no I haven't shown 145 00:09:37,682 --> 00:09:41,084 you the query, I don't expect you to initially see this, but what this says is 146 00:09:41,084 --> 00:09:46,047 select certain values from a relation R. And here, I'm going to select other 147 00:09:46,047 --> 00:09:49,428 values, from the same relation R, that's okay, I can have two different, eh, you 148 00:09:49,428 --> 00:09:52,662 know, the relation R can appear in two different places in the same expression, 149 00:09:52,662 --> 00:09:57,586 no problem. And, then join them together, then 150 00:09:57,586 --> 00:10:04,175 select, still, other values from the relation R, and join this one. 151 00:10:04,175 --> 00:10:10,511 And one way of evaluating this plan is to perform this join first and then this 152 00:10:10,511 --> 00:10:17,596 join second and, indicated by these parentheses, right? 153 00:10:17,596 --> 00:10:21,064 another way to evaluate this expression is to perform this join first and then 154 00:10:21,064 --> 00:10:24,528 form this join second indicated by the parenthesis. 155 00:10:24,528 --> 00:10:28,599 Still another expression is to take the full cross product of all three 156 00:10:28,599 --> 00:10:33,600 relations, which I haven't told you what cross product is. 157 00:10:33,600 --> 00:10:35,833 This is actually a pretty bad one to do. If you do know what a cross product is, 158 00:10:35,833 --> 00:10:37,945 it generates an enormous amount of data, and you would never actually want to 159 00:10:37,945 --> 00:10:40,579 evaluate this plan. But you could, and it's provably 160 00:10:40,579 --> 00:10:44,159 equivalent to these other plans, so you know that it returns the same answer. 161 00:10:45,380 --> 00:10:47,960 And now all we have to do is figure out which one of these is, is likely to be 162 00:10:47,960 --> 00:10:52,420 the cheapest one. And then we'll choose that one to run. 163 00:10:52,420 --> 00:10:55,752 And this, this is the kind of reasoning that all databases do internally whenever 164 00:10:55,752 --> 00:10:57,380 you write a query.