1 23:59:59,500 --> 00:00:05,582 [MUSIC]. 2 00:00:05,582 --> 00:00:09,426 So these graph pattern search problems were in the news in June 2013 pretty 3 00:00:09,426 --> 00:00:14,600 heavily associated with this PRISM system being developed by the NSA. 4 00:00:14,600 --> 00:00:17,939 And so an article in Business week described the kinds of tasks that they're 5 00:00:17,939 --> 00:00:21,270 interested in doing. And by the way the technologies that 6 00:00:21,270 --> 00:00:24,014 they're using this are things you heard about, or as far, as far as we 7 00:00:24,014 --> 00:00:27,302 understand. So the system Accumulo, I mentioned the 8 00:00:27,302 --> 00:00:30,340 new, new SQL lectures, was actually developed by the NSA and then released 9 00:00:30,340 --> 00:00:33,910 open source and then commercialized after that. 10 00:00:33,910 --> 00:00:36,610 And that's kind of the underlying platform, and then the kinds of 11 00:00:36,610 --> 00:00:40,060 applications they want to do using this Accumulo system and other systems are of 12 00:00:40,060 --> 00:00:44,440 the type we've been describing, in terms of pattern search. 13 00:00:44,440 --> 00:00:47,656 So let me give you an example of that. So in this Business Week article, they 14 00:00:47,656 --> 00:00:50,677 talk about, you know, in October a foreign national named so-and-so 15 00:00:50,677 --> 00:00:56,410 purchased a one-way plane ticket from Cairo to Miami where he rented a condo. 16 00:00:56,410 --> 00:00:59,155 Then over the previous few weeks he made a number of large withdraws from a 17 00:00:59,155 --> 00:01:02,190 Russian bank account. And placed repeated calls to a few people 18 00:01:02,190 --> 00:01:04,660 in Syria. And more recently he rented a truck, 19 00:01:04,660 --> 00:01:07,730 drove to Orlando and visited Walt Disney World by himself. 20 00:01:07,730 --> 00:01:10,879 And the point they wanted to make in the article is that individually any of these 21 00:01:10,879 --> 00:01:14,520 activities would raise any flags but collectively they might. 22 00:01:14,520 --> 00:01:18,830 They might be worthy of closer inspection and whether you agree with this or not. 23 00:01:18,830 --> 00:01:21,788 Maybe you'd say that this does not warrant for the expression but just 24 00:01:21,788 --> 00:01:26,617 trying to state the facts of what [LAUGH] of what they're doing with the system. 25 00:01:26,617 --> 00:01:30,640 We're not putting a judgement of whether it's the right or wrong thing to do. 26 00:01:30,640 --> 00:01:34,540 So you can encode this and you can encode these facts in these language say data 27 00:01:34,540 --> 00:01:40,160 log although you can also do it in, in, you know as a graph, as an RDF graph. 28 00:01:40,160 --> 00:01:42,825 And in fact that's actually a little closer to what they're actually doing but 29 00:01:42,825 --> 00:01:45,654 you know, you start off with the database of flights that the government has access 30 00:01:45,654 --> 00:01:48,666 to. So you know that they bought a flight to 31 00:01:48,666 --> 00:01:51,640 Cairo to Miami, and the last name was this. 32 00:01:51,640 --> 00:01:54,110 And that it was one way and that it was on this date. 33 00:01:54,110 --> 00:01:56,428 You also know that they made some withdrawals, there's multiple records 34 00:01:56,428 --> 00:01:59,226 here. for various amounts from some bank in 35 00:01:59,226 --> 00:02:02,460 Russia on various dates and what I didn't include here was the calls to people in 36 00:02:02,460 --> 00:02:05,743 Syria, although I probably should have, cause that's perhaps the biggest flag, 37 00:02:05,743 --> 00:02:11,682 but you can write that down to. You can say, call from this person to 38 00:02:11,682 --> 00:02:17,310 some other person, where location of the other person is Syria. 39 00:02:17,310 --> 00:02:20,622 So these are a representation of all the facts that they have access to. 40 00:02:20,622 --> 00:02:27,402 And the point I want to make is that, the, aggregation of these facts into a 41 00:02:27,402 --> 00:02:33,059 alert of some kind. Into a this is, this is worthy of further 42 00:02:33,059 --> 00:02:37,140 inspection can be expressed as a query in these various languages. 43 00:02:37,140 --> 00:02:38,605 In particular, I'm going to talk about datalog here. 44 00:02:38,605 --> 00:02:44,210 So maybe, one, you might flag a person. And this number one is just a token to 45 00:02:44,210 --> 00:02:47,256 say that this is one flag. And this is a date associated with the 46 00:02:47,256 --> 00:02:50,470 time that was flagged, in case you want to do further analysis. 47 00:02:50,470 --> 00:02:54,510 This might become clear in a moment. You, you raise this flag. 48 00:02:54,510 --> 00:02:58,000 If a person bought a flight from some origin to a destination. 49 00:02:58,000 --> 00:03:00,690 Where the origin was one of the flagged airports. 50 00:03:00,690 --> 00:03:05,000 I'm making this up. And the destination was a US airport. 51 00:03:05,000 --> 00:03:08,776 And the ticket type was one way. You know, obviously this alone is not 52 00:03:08,776 --> 00:03:12,760 necessarily suspicious, but it's, perhaps a first step. 53 00:03:12,760 --> 00:03:16,595 Is that from a, you know, airport that we sometimes monitor more closely to a US 54 00:03:16,595 --> 00:03:21,258 destination, and it was one way. Okay. 55 00:03:21,258 --> 00:03:24,870 Okay. Then, you know, you might build a table 56 00:03:24,870 --> 00:03:28,830 of foreign with, you might express a query producing foreign withdrawals that 57 00:03:28,830 --> 00:03:33,030 are the sum total amount withdrawn from a foreign bank where individual amounts are 58 00:03:33,030 --> 00:03:36,570 greater than 1,000 because maybe you're trying to cut out small, small 59 00:03:36,570 --> 00:03:41,559 withdrawals. Okay, and so this says we're assuming 60 00:03:41,559 --> 00:03:46,342 we're building off this withdrawal table. We add up the total for each person 61 00:03:46,342 --> 00:03:51,540 coming from a foreign bank. Okay. 62 00:03:51,540 --> 00:03:54,375 This could maybe be called big foreign withdrawals instead of just foreign 63 00:03:54,375 --> 00:03:57,410 withdrawals, okay. And then the flags are perhaps associated 64 00:03:57,410 --> 00:04:00,354 well when the total amount across of these withdrawals are greater than some 65 00:04:00,354 --> 00:04:05,540 fixed threshold, here I've said 10,000. Maybe that represents a flag. 66 00:04:05,540 --> 00:04:08,342 And notice that these flags are the same relation as these flags. 67 00:04:08,342 --> 00:04:11,492 In datalog, it's okay to have multiple rules like that, and the semantics of 68 00:04:11,492 --> 00:04:14,920 them is you're going to union all these results together. 69 00:04:14,920 --> 00:04:17,188 So you can imagine expressing this in SQL as well, where I query for a bunch of 70 00:04:17,188 --> 00:04:19,600 records, and then query for another bunch of records, and then union the results 71 00:04:19,600 --> 00:04:23,190 together. That's whats going on here. 72 00:04:23,190 --> 00:04:27,222 Alright and then we skip the conditions on the calls to Syria although again 73 00:04:27,222 --> 00:04:32,250 those would be easy to do and probably good examples to include. 74 00:04:32,250 --> 00:04:36,280 But maybe we have this database of all the vehicle rentals with attributes you 75 00:04:36,280 --> 00:04:40,186 know, the person who rented it, the vehicles, the origin, the destination, 76 00:04:40,186 --> 00:04:45,182 and some kind of a date. And to rewrite a query producing yet 77 00:04:45,182 --> 00:04:49,026 another flag when someone rented a vehicle that where the destination was 78 00:04:49,026 --> 00:04:55,045 some important location. And this one's probably not the greatest, 79 00:04:55,045 --> 00:05:01,470 example of a, of something that would generate a, a, a flag. 80 00:05:01,470 --> 00:05:03,510 But it's something you could look for. And you can imagine making this, making 81 00:05:03,510 --> 00:05:06,518 this a little bit more complicated. Okay, and so all these flags together, 82 00:05:06,518 --> 00:05:10,599 you can write another query in Datalog. And again, I haven't told you too much 83 00:05:10,599 --> 00:05:13,938 about the details of Datalog, but one thing you'll notice here is that I've, 84 00:05:13,938 --> 00:05:19,000 I'm using aggregations in the head of the rule, just like you can in SQL. 85 00:05:19,000 --> 00:05:24,229 So, select person sum flag min date, max date, group by person is the same, is 86 00:05:24,229 --> 00:05:29,985 the, the same semantics of what I'm showing you here. 87 00:05:31,750 --> 00:05:35,910 So we add up all the total flags, now we have a relation with people, their total 88 00:05:35,910 --> 00:05:40,820 flags, and the, date range for which those flags occurred. 89 00:05:43,360 --> 00:05:46,636 This won't get you exactly the right result because we didn't really filter 90 00:05:46,636 --> 00:05:49,808 much on the dates, but you can see the argument I want to make is that it's not 91 00:05:49,808 --> 00:05:54,102 too much code. It's not too much work to try to express 92 00:05:54,102 --> 00:05:58,067 these English questions you have over this massive graph in terms of a logical 93 00:05:58,067 --> 00:06:02,010 language like this. Okay? 94 00:06:02,010 --> 00:06:04,960 And so maybe finally the alerts. Things that are, that are warrant more 95 00:06:04,960 --> 00:06:09,108 human attention by some analyst. Are things where the max date minus min, 96 00:06:09,108 --> 00:06:13,581 you know, within the span of just ten days, the total flagent is greater than 97 00:06:13,581 --> 00:06:17,330 say, three. And there you go, one problem I've sort 98 00:06:17,330 --> 00:06:19,890 of pointed out about this, is that this is giving you a total across the entire 99 00:06:19,890 --> 00:06:22,330 range of time for that person, and so you may want to bucket this by weeks or 100 00:06:22,330 --> 00:06:25,672 months. And I haven't expressed that here. 101 00:06:25,672 --> 00:06:29,448 Okay, so what I'm hoping to do is sort of weight your appetite that these 102 00:06:29,448 --> 00:06:33,544 rule-based logical languages can work with a big graph, can work with a lot of 103 00:06:33,544 --> 00:06:37,576 relations and can express fairly complicated conditions and in some sense 104 00:06:37,576 --> 00:06:43,320 they're all you need. If you have a way of implementing this at 105 00:06:43,320 --> 00:06:47,942 scale, efficiently, this is kind of all you need to do fairly advanced analytics. 106 00:06:47,942 --> 00:06:55,430 Okay. So let me give you one more example of a 107 00:06:55,430 --> 00:07:00,204 datalog query. So, we want to know who contacted who and 108 00:07:00,204 --> 00:07:04,678 when they contacted them, but we don't really care how they did. 109 00:07:04,678 --> 00:07:10,110 And this is a simplification of something something we saw in the previous example. 110 00:07:10,110 --> 00:07:14,560 So we say, person one contacted person two at time, at some time. 111 00:07:14,560 --> 00:07:20,250 If, person one sends an e-mail to person two at some time. 112 00:07:22,310 --> 00:07:27,000 We also say, Person1 contacted Person2 at some time if Person1 called Person2 at 113 00:07:27,000 --> 00:07:31,150 some time. And then finally we say, Person1, person, 114 00:07:31,150 --> 00:07:36,770 contacted Person2 if they sent a text message at some time. 115 00:07:36,770 --> 00:07:39,563 And so the point here is, these would most likely come from three very 116 00:07:39,563 --> 00:07:43,106 different sources. Right, as the government is doing 117 00:07:43,106 --> 00:07:46,042 whatever they're doing to the email. [LAUGH] Again, whether you agree with 118 00:07:46,042 --> 00:07:50,440 this or not. that's one company or one source. 119 00:07:50,440 --> 00:07:54,334 Another source is who called who and a third source is who sent a text message 120 00:07:54,334 --> 00:07:57,460 to who. And so combining all these together 121 00:07:57,460 --> 00:08:01,150 doesn't necessarily take a lot of work. You can express these in these high level 122 00:08:01,150 --> 00:08:04,788 languages. And this is I would argue, the right way 123 00:08:04,788 --> 00:08:11,768 to approach these problems as opposed to a lot of low-level code. 124 00:08:11,768 --> 00:08:13,910 Okay. So maybe one more example. 125 00:08:15,260 --> 00:08:20,490 Who could've know before June 3rd that some event was going to happen. 126 00:08:20,490 --> 00:08:24,715 Maybe you know for a fact that someone named Sam knew, okay, so you're starting 127 00:08:24,715 --> 00:08:28,160 from that point. Well who else could have known? 128 00:08:28,160 --> 00:08:31,988 Well using the same trick we used in the, to build up a contacted relation you can 129 00:08:31,988 --> 00:08:38,424 do this again. Well we know Person2 knew if Person1 knew 130 00:08:38,424 --> 00:08:45,570 and Person1 emailed Person2 before June 3rd. 131 00:08:45,570 --> 00:08:46,565 Sorry. That's the other condition we're looking 132 00:08:46,565 --> 00:08:49,670 for. Right? 133 00:08:49,670 --> 00:08:54,620 And we can also argue that Person2 knew, potentially knew, if Person1 knew, and 134 00:08:54,620 --> 00:09:02,020 Person2 met with Person1 before June 3rd. And, so the point I want to make here is 135 00:09:02,020 --> 00:09:06,777 that, we've referenced the head, the relation that we're creating, knew, we've 136 00:09:06,777 --> 00:09:11,860 referenced in the body of this rule as well. 137 00:09:11,860 --> 00:09:15,111 So, there's a recursive relationship now. Right, it starts with Sam and then, 138 00:09:15,111 --> 00:09:18,946 basically find all the people that Sam emailed before June 3rd, and they're in 139 00:09:18,946 --> 00:09:23,138 the final result. And then all the people that those people 140 00:09:23,138 --> 00:09:26,760 emailed before June 3rd, and they're in the final result, and so on. 141 00:09:28,470 --> 00:09:32,434 And you can do this with met, and you can do this with call, and so on. 142 00:09:32,434 --> 00:09:38,437 So this recursive relationship, this self-reference, is the difference between 143 00:09:38,437 --> 00:09:42,542 Datalog and SQL. You actually can express this kind of 144 00:09:42,542 --> 00:09:47,400 thing in SQL, there's, Microsoft calls them common table expressions. 145 00:09:47,400 --> 00:09:49,942 And you can use the width clause to do this occurs and, but you'll find if you 146 00:09:49,942 --> 00:09:52,484 try to do this in practice, that the implementation of those features, is a 147 00:09:52,484 --> 00:09:56,430 little bit poor in many of the commercial databases. 148 00:09:56,430 --> 00:10:00,674 And it's, there's various limitations. For example, you can only have a depth of 149 00:10:00,674 --> 00:10:03,746 100 recursive steps, which is sort of arbitrary and much too small for many of 150 00:10:03,746 --> 00:10:07,742 these applications. You'll also find that the performance of 151 00:10:07,742 --> 00:10:10,560 these is, varies wildly and, and is not particularly good. 152 00:10:10,560 --> 00:10:14,037 So, it doesn't, it's not clear that the, that the customers of relational 153 00:10:14,037 --> 00:10:17,172 databases have been demanding these features, but I'd argue that 154 00:10:17,172 --> 00:10:21,452 increasingly, this is what people are interested in. 155 00:10:21,452 --> 00:10:25,027 And my evidence is the examples like we just saw from the news, the fact that 156 00:10:25,027 --> 00:10:28,492 graphs specific data base systems are emerging, you know, [UNKNOWN] is, is 157 00:10:28,492 --> 00:10:33,462 getting very, very popular. There's various systems for processing 158 00:10:33,462 --> 00:10:37,923 graphs on top of map reduce and we'll talk about a couple of those and so on. 159 00:10:37,923 --> 00:10:42,280 RDF systems, you know these tre- sort of tripple stores. 160 00:10:42,280 --> 00:10:47,317 So the fact that graphs are becoming more and more important suggests that this 161 00:10:47,317 --> 00:10:51,551 ability to traverse the graphs recursively is becoming more and more 162 00:10:51,551 --> 00:10:56,637 important. Which motivates perhaps a move from SQL 163 00:10:56,637 --> 00:11:01,528 relational algebra languages to this datalog relational algebra language and 164 00:11:01,528 --> 00:11:06,273 so I my prediciton is that you're going to see datalog pop up more and more often 165 00:11:06,273 --> 00:11:10,061 in industry okay.