[MUSIC]. 
So these graph pattern search problems 
were in the news in June 2013 pretty 
heavily associated with this PRISM system 
being developed by the NSA. 
And so an article in Business week 
described the kinds of tasks that they're 
interested in doing. 
And by the way the technologies that 
they're using this are things you heard 
about, or as far, as far as we 
understand. 
So the system Accumulo, I mentioned the 
new, new SQL lectures, was actually 
developed by the NSA and then released 
open source and then commercialized after 
that. 
And that's kind of the underlying 
platform, and then the kinds of 
applications they want to do using this 
Accumulo system and other systems are of 
the type we've been describing, in terms 
of pattern search. 
So let me give you an example of that. 
So in this Business Week article, they 
talk about, you know, in October a 
foreign national named so-and-so 
purchased a one-way plane ticket from 
Cairo to Miami where he rented a condo. 
Then over the previous few weeks he made 
a number of large withdraws from a 
Russian bank account. 
And placed repeated calls to a few people 
in Syria. 
And more recently he rented a truck, 
drove to Orlando and visited Walt Disney 
World by himself. 
And the point they wanted to make in the 
article is that individually any of these 
activities would raise any flags but 
collectively they might. 
They might be worthy of closer inspection 
and whether you agree with this or not. 
Maybe you'd say that this does not 
warrant for the expression but just 
trying to state the facts of what [LAUGH] 
of what they're doing with the system. 
We're not putting a judgement of whether 
it's the right or wrong thing to do. 
So you can encode this and you can encode 
these facts in these language say data 
log although you can also do it in, in, 
you know as a graph, as an RDF graph. 
And in fact that's actually a little 
closer to what they're actually doing but 
you know, you start off with the database 
of flights that the government has access 
to. 
So you know that they bought a flight to 
Cairo to Miami, and the last name was 
this. 
And that it was one way and that it was 
on this date. 
You also know that they made some 
withdrawals, there's multiple records 
here. 
for various amounts from some bank in 
Russia on various dates and what I didn't 
include here was the calls to people in 
Syria, although I probably should have, 
cause that's perhaps the biggest flag, 
but you can write that down to. 
You can say, call from this person to 
some other person, where location of the 
other person is Syria. 
So these are a representation of all the 
facts that they have access to. 
And the point I want to make is that, 
the, aggregation of these facts into a 
alert of some kind. 
Into a this is, this is worthy of further 
inspection can be expressed as a query in 
these various languages. 
In particular, I'm going to talk about 
datalog here. 
So maybe, one, you might flag a person. 
And this number one is just a token to 
say that this is one flag. 
And this is a date associated with the 
time that was flagged, in case you 
want to do further analysis. 
This might become clear in a moment. 
You, you raise this flag. 
If a person bought a flight from some 
origin to a destination. 
Where the origin was one of the flagged 
airports. 
I'm making this up. 
And the destination was a US airport. 
And the ticket type was one way. 
You know, obviously this alone is not 
necessarily suspicious, but it's, perhaps 
a first step. 
Is that from a, you know, airport that we 
sometimes monitor more closely to a US 
destination, and it was one way. 
Okay. 
Okay. 
Then, you know, you might build a table 
of foreign with, you might express a 
query producing foreign withdrawals that 
are the sum total amount withdrawn from a 
foreign bank where individual amounts are 
greater than 1,000 because maybe you're 
trying to cut out small, small 
withdrawals. 
Okay, and so this says we're assuming 
we're building off this withdrawal table. 
We add up the total for each person 
coming from a foreign bank. 
Okay. 
This could maybe be called big foreign 
withdrawals instead of just foreign 
withdrawals, okay. 
And then the flags are perhaps associated 
well when the total amount across of 
these withdrawals are greater than some 
fixed threshold, here I've said 10,000. 
Maybe that represents a flag. 
And notice that these flags are the same 
relation as these flags. 
In datalog, it's okay to have multiple 
rules like that, and the semantics of 
them is you're going to union all these 
results together. 
So you can imagine expressing this in SQL 
as well, where I query for a bunch of 
records, and then query for another bunch 
of records, and then union the results 
together. 
That's whats going on here. 
Alright and then we skip the conditions 
on the calls to Syria although again 
those would be easy to do and probably 
good examples to include. 
But maybe we have this database of all 
the vehicle rentals with attributes you 
know, the person who rented it, the 
vehicles, the origin, the destination, 
and some kind of a date. 
And to rewrite a query producing yet 
another flag when someone rented a 
vehicle that where the destination was 
some important location. 
And this one's probably not the greatest, 
example of a, of something that would 
generate a, a, a flag. 
But it's something you could look for. 
And you can imagine making this, making 
this a little bit more complicated. 
Okay, and so all these flags together, 
you can write another query in Datalog. 
And again, I haven't told you too much 
about the details of Datalog, but one 
thing you'll notice here is that I've, 
I'm using aggregations in the head of the 
rule, just like you can in SQL. 
So, select person sum flag min date, max 
date, group by person is the same, is 
the, the same semantics of what I'm 
showing you here. 
So we add up all the total flags, now we 
have a relation with people, their total 
flags, and the, date range for which 
those flags occurred. 
This won't get you exactly the right 
result because we didn't really filter 
much on the dates, but you can see the 
argument I want to make is that it's not 
too much code. 
It's not too much work to try to express 
these English questions you have over 
this massive graph in terms of a logical 
language like this. 
Okay? 
And so maybe finally the alerts. 
Things that are, that are warrant more 
human attention by some analyst. 
Are things where the max date minus min, 
you know, within the span of just ten 
days, the total flagent is greater than 
say, three. 
And there you go, one problem I've sort 
of pointed out about this, is that this 
is giving you a total across the entire 
range of time for that person, and so you 
may want to bucket this by weeks or 
months. 
And I haven't expressed that here. 
Okay, so what I'm hoping to do is sort of 
weight your appetite that these 
rule-based logical languages can work 
with a big graph, can work with a lot of 
relations and can express fairly 
complicated conditions and in some sense 
they're all you need. 
If you have a way of implementing this at 
scale, efficiently, this is kind of all 
you need to do fairly advanced analytics. 
Okay. 
So let me give you one more example of a 
datalog query. 
So, we want to know who contacted who and 
when they contacted them, but we don't 
really care how they did. 
And this is a simplification of something 
something we saw in the previous example. 
So we say, person one contacted person 
two at time, at some time. 
If, person one sends an e-mail to person 
two at some time. 
We also say, Person1 contacted Person2 at 
some time if Person1 called Person2 at 
some time. 
And then finally we say, Person1, person, 
contacted Person2 if they sent a text 
message at some time. 
And so the point here is, these would 
most likely come from three very 
different sources. 
Right, as the government is doing 
whatever they're doing to the email. 
[LAUGH] Again, whether you agree with 
this or not. 
that's one company or one source. 
Another source is who called who and a 
third source is who sent a text message 
to who. 
And so combining all these together 
doesn't necessarily take a lot of work. 
You can express these in these high level 
languages. 
And this is I would argue, the right way 
to approach these problems as opposed to 
a lot of low-level code. 
Okay. 
So maybe one more example. 
Who could've know before June 3rd that 
some event was going to happen. 
Maybe you know for a fact that someone 
named Sam knew, okay, so you're starting 
from that point. 
Well who else could have known? 
Well using the same trick we used in the, 
to build up a contacted relation you can 
do this again. 
Well we know Person2 knew if Person1 knew 
and Person1 emailed Person2 before June 
3rd. 
Sorry. 
That's the other condition we're looking 
for. 
Right? 
And we can also argue that Person2 knew, 
potentially knew, if Person1 knew, and 
Person2 met with Person1 before June 3rd. 
And, so the point I want to make here is 
that, we've referenced the head, the 
relation that we're creating, knew, we've 
referenced in the body of this rule as 
well. 
So, there's a recursive relationship now. 
Right, it starts with Sam and then, 
basically find all the people that Sam 
emailed before June 3rd, and they're in 
the final result. 
And then all the people that those people 
emailed before June 3rd, and they're in 
the final result, and so on. 
And you can do this with met, and you can 
do this with call, and so on. 
So this recursive relationship, this 
self-reference, is the difference between 
Datalog and SQL. 
You actually can express this kind of 
thing in SQL, there's, Microsoft calls 
them common table expressions. 
And you can use the width clause to do 
this occurs and, but you'll find if you 
try to do this in practice, that the 
implementation of those features, is a 
little bit poor in many of the commercial 
databases. 
And it's, there's various limitations. 
For example, you can only have a depth of 
100 recursive steps, which is sort of 
arbitrary and much too small for many of 
these applications. 
You'll also find that the performance of 
these is, varies wildly and, and is not 
particularly good. 
So, it doesn't, it's not clear that the, 
that the customers of relational 
databases have been demanding these 
features, but I'd argue that 
increasingly, this is what people are 
interested in. 
And my evidence is the examples like we 
just saw from the news, the fact that 
graphs specific data base systems are 
emerging, you know, [UNKNOWN] is, is 
getting very, very popular. 
There's various systems for processing 
graphs on top of map reduce and we'll 
talk about a couple of those and so on. 
RDF systems, you know these tre- sort of 
tripple stores. 
So the fact that graphs are becoming more 
and more important suggests that this 
ability to traverse the graphs 
recursively is becoming more and more 
important. 
Which motivates perhaps a move from SQL 
relational algebra languages to this 
datalog relational algebra language and 
so I my prediciton is that you're going 
to see datalog pop up more and more often 
in industry okay.