1 00:00:06,440 --> 00:00:10,656 [MUSIC] Okay, last time we talked about algebraic optimization and I argued that 2 00:00:10,656 --> 00:00:15,613 all three of these expressions without going into a lot of detail. 3 00:00:15,613 --> 00:00:18,574 But I argued that all these three of these were equivalent and they differed 4 00:00:18,574 --> 00:00:21,580 only in the order in which things were evaluated. 5 00:00:21,580 --> 00:00:24,890 Here you evaluate this join first and this join second. 6 00:00:24,890 --> 00:00:28,610 And in this expression you evaluate this join first and this join second. 7 00:00:28,610 --> 00:00:32,758 And here you, sort of, find all possible combinations of two bulls and then filter 8 00:00:32,758 --> 00:00:35,413 that. And so if you don't understand exactly 9 00:00:35,413 --> 00:00:37,900 what's going on in these expressions that's okay. 10 00:00:37,900 --> 00:00:40,477 You're not going to know that yet. We'll talk about it in fact, in this 11 00:00:40,477 --> 00:00:43,250 segment, I think. but the idea, the take away here is that 12 00:00:43,250 --> 00:00:46,587 there's three equivalent expressions and we don't know necessarily which ones, 13 00:00:46,587 --> 00:00:50,080 which one is the fastest one to you, to evaluate. 14 00:00:50,080 --> 00:00:53,153 But the database can figure this out and does, every time you write a query. 15 00:00:53,153 --> 00:00:55,385 And that's this notion of algebraic optimization. 16 00:00:55,385 --> 00:00:59,289 Now, we don't you know, even if you are familiar with databases, you may or may 17 00:00:59,289 --> 00:01:03,044 not be familiar with the relational algebra. 18 00:01:03,044 --> 00:01:06,444 which should be strange, because I've argued that it's you know, the hallmark 19 00:01:06,444 --> 00:01:11,668 of databases and totally fundamental. So why don't we think about programming 20 00:01:11,668 --> 00:01:16,890 databases in terms of writing relational algebraic expressions? 21 00:01:16,890 --> 00:01:20,205 Well, another good idea, another key idea that's associated with relational 22 00:01:20,205 --> 00:01:24,020 databases is this notion of declarative languages. 23 00:01:24,020 --> 00:01:27,638 And what we mean by declarative languages is that you specify the answer that you 24 00:01:27,638 --> 00:01:31,552 want but you do not specify anything about how to get it. 25 00:01:31,552 --> 00:01:35,899 And so a relational algebra expression actually does specify an order, as I 26 00:01:35,899 --> 00:01:40,384 showed on this slide, here's three different expressions that's indicating 27 00:01:40,384 --> 00:01:45,490 exactly which order to do every operation. 28 00:01:45,490 --> 00:01:48,640 That means that some, you know, if you write, if you write an expression like 29 00:01:48,640 --> 00:01:53,170 this you're instructing the computer, look do it in this particular order. 30 00:01:53,170 --> 00:01:54,878 Okay? And so these declarative languages say, 31 00:01:54,878 --> 00:01:57,398 look we're just going to describe the properties that must be true of the 32 00:01:57,398 --> 00:01:59,727 result. And we're going to let the database 33 00:01:59,727 --> 00:02:02,910 figure out the right order in which to do this. 34 00:02:02,910 --> 00:02:06,536 And so here is a quick example. So imagine you have two tables. 35 00:02:06,536 --> 00:02:10,298 One is order with three columns, order, date and account and another table with 36 00:02:10,298 --> 00:02:15,176 item with two columns order and part. And the semantics here is that this 37 00:02:15,176 --> 00:02:19,845 column indicates which order that item should be associated with. 38 00:02:19,845 --> 00:02:24,445 Okay. And so if you want to say find all orders 39 00:02:24,445 --> 00:02:28,735 from today along with the items ordered, then you might write this query, and if 40 00:02:28,735 --> 00:02:33,790 you've seen SQL plenty of times before, bear with me. 41 00:02:33,790 --> 00:02:38,910 And if you haven't, then pay attention. So, select star, give me all possible 42 00:02:38,910 --> 00:02:46,710 columns from the table order and all possible columns from the table item. 43 00:02:49,420 --> 00:02:51,850 But I only want record such that this condition is true. 44 00:02:51,850 --> 00:02:57,098 Where the order column from the order table matches the order column from the 45 00:02:57,098 --> 00:03:01,620 item table, right. And further, I only want orders from 46 00:03:01,620 --> 00:03:06,690 today, where order dot date equals today. So this is just conditions expressed over 47 00:03:06,690 --> 00:03:10,866 the results, without any kind of idea of, of what, of, of how to actually get this 48 00:03:10,866 --> 00:03:14,760 answer. So what automatically happens is that 49 00:03:14,760 --> 00:03:17,505 this query is translated into a relational algebra expression along the 50 00:03:17,505 --> 00:03:21,963 lines of what we've already seen. Now here I have sort of just done a 51 00:03:21,963 --> 00:03:25,798 cartoon where you can say scan the item table, scan the order table, select the 52 00:03:25,798 --> 00:03:30,960 record such that date equals today and then perform the join. 53 00:03:30,960 --> 00:03:34,618 Find all the records in order they correspond to the that have, for each 54 00:03:34,618 --> 00:03:38,524 record in order find the corresponding records and item that match on, on on 55 00:03:38,524 --> 00:03:41,124 order. Okay? 56 00:03:41,124 --> 00:03:45,700 So, this is happening every time you run a query, again. 57 00:03:47,810 --> 00:03:52,372 So the SQL is the what, not the how. Give you another example, there's three 58 00:03:52,372 --> 00:03:58,052 columns, product, purchase and customer. In this the underlining here we haven't 59 00:03:58,052 --> 00:04:01,757 talked about, but this is the indicating what makes the table, what makes this 60 00:04:01,757 --> 00:04:06,256 record unique. And so here, the PID makes the product 61 00:04:06,256 --> 00:04:10,064 unique, the CID makes the customer unique and the combination of pid and cid makes 62 00:04:10,064 --> 00:04:13,124 the purchase unique. Okay. 63 00:04:13,124 --> 00:04:17,540 And so here is another sequel query. We say select distinct product name. 64 00:04:17,540 --> 00:04:21,409 Why do I know it's the product name, because I see an x here and I see an x 65 00:04:21,409 --> 00:04:25,467 here. And the customer name and I knows it's 66 00:04:25,467 --> 00:04:28,540 the customer name because I see a z here and I see a z here. 67 00:04:28,540 --> 00:04:32,800 This is an alias for the, for the relation customer. 68 00:04:33,830 --> 00:04:38,950 From these three tables where the product ID in the product table matches the 69 00:04:38,950 --> 00:04:45,523 product ID in the purchase table. And the customer ID in the purchase table 70 00:04:45,523 --> 00:04:50,240 matches the customer ID in the customer table. 71 00:04:50,240 --> 00:04:53,082 And that's a typo looks like, that should be z. 72 00:04:53,082 --> 00:05:01,752 So, maybe change that on your own slides. Let me see if I can fix it now z. 73 00:05:01,752 --> 00:05:06,885 That's the ID. And then we want, we, but now we want 74 00:05:06,885 --> 00:05:12,192 only the, the products for which the price is greater than 100, and we only 75 00:05:12,192 --> 00:05:19,850 want the customers whose city is Seattle. Alright, so what does this say in 76 00:05:19,850 --> 00:05:23,094 English? Well find the, combinations of products 77 00:05:23,094 --> 00:05:26,937 and customers, unique combinations of products and customers where the 78 00:05:26,937 --> 00:05:32,875 customer's in Seattle and they paid for a product worth more than a 100. 79 00:05:32,875 --> 00:05:35,765 Okay. So it's clear what we want, but it's 80 00:05:35,765 --> 00:05:41,532 unclear how to get it, it gets kind of a complicated query. 81 00:05:41,532 --> 00:05:45,700 Okay. So translating this into relational 82 00:05:45,700 --> 00:05:50,942 algebra, we have this. So at the bottom we have product and the 83 00:05:50,942 --> 00:05:55,920 purchase and now we do this join. Where we say for every product, find me 84 00:05:55,920 --> 00:06:00,780 the corresponding records and purchase. Then we do another join for every record 85 00:06:00,780 --> 00:06:04,440 in, the, in the, result of this join find me the corresponding records and 86 00:06:04,440 --> 00:06:08,679 customer, right. Now filter out all those records such 87 00:06:08,679 --> 00:06:12,337 that where, where price is not greater than 100, we only want the ones where 88 00:06:12,337 --> 00:06:16,897 price is greater than 100. And we only want the ones where city 89 00:06:16,897 --> 00:06:20,698 equals Seattle. And then we want to, in this case, 90 00:06:20,698 --> 00:06:26,601 project down onto these two columns. What I mean by project is get rid of all 91 00:06:26,601 --> 00:06:30,103 the other columns except for the two we're interested in. 92 00:06:30,103 --> 00:06:32,012 Okay? And finally, take, take the final answer. 93 00:06:32,012 --> 00:06:36,270 So, the two points here is that the execution order is now clearly specified. 94 00:06:36,270 --> 00:06:39,250 But there are a lot of physical details, are still left open. 95 00:06:39,250 --> 00:06:42,080 You know this is a very high level indication of what's going on. 96 00:06:42,080 --> 00:06:44,060 Order of operations is clear but that's about it. 97 00:06:44,060 --> 00:06:46,812 We don't know how we're going to do the join, exactly, and there's multiple ways 98 00:06:46,812 --> 00:06:49,080 you can do it. I've indicated that you know, we're 99 00:06:49,080 --> 00:06:51,145 going to take for every rec, every record and product we're going to look up a 100 00:06:51,145 --> 00:06:56,216 corresponding record of purchase. But we haven't said precisely what that 101 00:06:56,216 --> 00:06:58,540 means. Okay. 102 00:06:58,540 --> 00:06:59,880 I give a I'm going to give a example of this in a second. 103 00:07:01,590 --> 00:07:05,238 So another example here, here we only have a single relation called R and it's 104 00:07:05,238 --> 00:07:09,630 got three columns, subject, predicate, and object. 105 00:07:09,630 --> 00:07:15,155 And you see this kind of schema when you hear about, when you work with RDF data, 106 00:07:15,155 --> 00:07:22,105 the Resource Description Framework. An RDF is a language and formalism and 107 00:07:22,105 --> 00:07:26,825 software stack for managing what is called linked data and here sort of 108 00:07:26,825 --> 00:07:33,410 everything is it's a set of all facts. Any kind of fact you can come up with 109 00:07:33,410 --> 00:07:37,130 beginning code in RDF you can say you know, the instructor of this course is 110 00:07:37,130 --> 00:07:39,740 Bill Howe. Right? 111 00:07:39,740 --> 00:07:44,514 So, here the subject might be this course, the predicate is has instructor 112 00:07:44,514 --> 00:07:48,180 and the object is Bill Howe. Okay. 113 00:07:48,180 --> 00:07:51,943 And so this is a people use this formalism as a very general way of 114 00:07:51,943 --> 00:07:58,386 encoding an information from any source. And we we may, we might touch on this 115 00:07:58,386 --> 00:08:03,030 much later in the course. Okay, they used kind of a complicated 116 00:08:03,030 --> 00:08:05,501 query. But what it says is I'm going to have 117 00:08:05,501 --> 00:08:10,380 three instances of the same relation. And I'm going to join them all up. 118 00:08:10,380 --> 00:08:17,760 And I'm going to look for a sequence of tubules such that we have a person who 119 00:08:17,760 --> 00:08:25,263 knows another person who holds the account of a company who has an account 120 00:08:25,263 --> 00:08:39,990 homepage of a particular value. Alright, so you are looking for the 121 00:08:39,990 --> 00:08:58,695 sequence of where this edge is knows, and this edge is holdsaccount. 122 00:08:58,695 --> 00:09:07,769 And this edge is accountHomepage. Right? 123 00:09:07,769 --> 00:09:13,749 So find me all possible combinations in this table where I've got, you know if I 124 00:09:13,749 --> 00:09:19,913 nail, "A, B", all instantiations of A, B, C, and D such that this pattern matches, 125 00:09:19,913 --> 00:09:24,560 Okay. And the joins are specified by these 126 00:09:24,560 --> 00:09:27,315 conditions. The object of the first relation must be 127 00:09:27,315 --> 00:09:30,855 equal to the subject of the second relation and the object of the second 128 00:09:30,855 --> 00:09:35,337 relation must be the subject of the third relation. 129 00:09:35,337 --> 00:09:37,440 Okay. So we're looking for patterns in the 130 00:09:37,440 --> 00:09:42,526 graph that look like this. And in relational algebra, you see this, 131 00:09:42,526 --> 00:09:47,950 this, this query gets translated into this form. 132 00:09:47,950 --> 00:09:50,739 There's a selection to find predicate equals knows. 133 00:09:50,739 --> 00:09:54,020 There's a selection to find predicate equals holds accounts. 134 00:09:54,020 --> 00:09:58,270 And there's a selection to find predicate equals account homepage. 135 00:09:58,270 --> 00:10:01,270 And then you join. And then a sequence of joins. 136 00:10:01,270 --> 00:10:04,017 And finally, a projection just to pull, pull out the, the final answer that we're 137 00:10:04,017 --> 00:10:06,948 interested in. In other words, the select clause. 138 00:10:06,948 --> 00:10:09,884 Okay. So, perhaps a complicated example, but I 139 00:10:09,884 --> 00:10:12,957 think the takeaways here. I, I wanted to mention RDF. 140 00:10:12,957 --> 00:10:16,220 because we might come up, come across it again. 141 00:10:16,220 --> 00:10:19,101 And I also want to demonstrate that you can access the same relation more than 142 00:10:19,101 --> 00:10:23,342 one time in a single query. And then I wanted to give another example 143 00:10:23,342 --> 00:10:27,055 of translating even complicated queries into relational algebra expressions. 144 00:10:27,055 --> 00:10:30,531 Okay.