1
00:00:00,001 --> 00:00:05,337
[MUSIC]. 

2
00:00:05,337 --> 00:00:10,343
Alright, so more generally, you can have 
what we'll call a theta-join. 

3
00:00:10,343 --> 00:00:15,543
And this is essentially just a join, but 
the condition here can be anything you 

4
00:00:15,543 --> 00:00:18,740
want. 
Okay. 

5
00:00:18,740 --> 00:00:21,834
Rather than just an equality condition. 
This could be greater than or less than, 

6
00:00:21,834 --> 00:00:26,596
or arbitrary functions, and so on. 
Okay, and so this all pair similarity 

7
00:00:26,596 --> 00:00:32,900
test that I talked about before is an 
example of a theta-join. 

8
00:00:32,900 --> 00:00:34,580
And yeah, we'll see a more detailed 
example in a second. 

9
00:00:38,250 --> 00:00:41,274
Right, and so, just to point out that 
that equi-join itself is a special case 

10
00:00:41,274 --> 00:00:45,235
of theta-join, where, where theta is just 
the equality condition. 

11
00:00:45,235 --> 00:00:48,819
Alright, so here's some examples of 
theta-joins, just to sort of demonstrate 

12
00:00:48,819 --> 00:00:52,347
that these come up pretty often in 
practice, more than you might be familiar 

13
00:00:52,347 --> 00:00:56,046
with. 
And again, especially speaking to the 

14
00:00:56,046 --> 00:01:00,176
people who are familiar, who have 
experience with databases you know, these 

15
00:01:00,176 --> 00:01:05,183
are not going to be along for key 
relationships quite as often. 

16
00:01:05,183 --> 00:01:07,266
Right, okay. 
So if you want to, say, find all 

17
00:01:07,266 --> 00:01:11,199
hospitals within five miles of a school, 
well, you know, this doesn't immediately 

18
00:01:11,199 --> 00:01:15,552
seem like a relation algebra query or, or 
a SQL query. 

19
00:01:15,552 --> 00:01:19,092
But it kind of is, right, it's just a 
join where the join condition is this 

20
00:01:19,092 --> 00:01:24,825
distance function over the location of a 
hospital and the location of a school. 

21
00:01:24,825 --> 00:01:28,241
Okay, and then I did a projection here to 
sort of project out the name of the 

22
00:01:28,241 --> 00:01:31,601
hospital, because the, the English 
version of this seemed to suggest that we 

23
00:01:31,601 --> 00:01:36,103
just want the name of the hospital and 
that's it. 

24
00:01:36,103 --> 00:01:39,379
Okay, and so in SQL, this, this might 
look like this, where you say look, give 

25
00:01:39,379 --> 00:01:42,707
me all combinations of the hospitals and 
schools, and then filter on the ones 

26
00:01:42,707 --> 00:01:46,035
where the location of the hospital is is 
less than five miles away from the 

27
00:01:46,035 --> 00:01:51,286
location of the school. 
And here, I'm kind of assuming that there 

28
00:01:51,286 --> 00:01:54,940
exists some distance function that knows 
how to compute this. 

29
00:01:54,940 --> 00:01:58,040
And we'll talk at the end about how new 
functions that are not part of the 

30
00:01:58,040 --> 00:02:01,240
language, are not part of relation 
algebra, can be registered in the system, 

31
00:02:01,240 --> 00:02:05,220
and that's this notion of user defined 
functions. 

32
00:02:05,220 --> 00:02:07,795
But trust me for right now that these 
things can exist. 

33
00:02:07,795 --> 00:02:09,820
Okay. 
And in fact, they don't even have to be 

34
00:02:09,820 --> 00:02:12,540
user defined. 
There's many functions that are already 

35
00:02:12,540 --> 00:02:15,877
available in databases for manipulating 
say, for example, strings. 

36
00:02:15,877 --> 00:02:18,913
And in fact, even for geographic 
information, there actually are distance 

37
00:02:18,913 --> 00:02:21,800
functions available in those commercial 
databases. 

38
00:02:21,800 --> 00:02:24,570
Okay. 
So you'll see this structure, the 

39
00:02:24,570 --> 00:02:29,210
takeaway here is that I want you to still 
think join, right? 

40
00:02:29,210 --> 00:02:31,355
Just because you don't see a quality 
condition doesn't mean there's not a join 

41
00:02:31,355 --> 00:02:34,295
going on, it's just the same, it's the 
same kind of join as everything else. 

42
00:02:34,295 --> 00:02:37,544
And then, the other thing, the other 
takeaway is just to know the term 

43
00:02:37,544 --> 00:02:41,890
theta-join in case that comes up, okay. 
Usually whenever, when anybody, when 

44
00:02:41,890 --> 00:02:44,690
anybody's talking about theta-join, what 
they mean is, you know, difficult joins, 

45
00:02:44,690 --> 00:02:47,390
right? 
Arbitrary joins, gen, the general case of 

46
00:02:47,390 --> 00:02:51,200
joins. 
Alright. 

47
00:02:51,200 --> 00:02:55,043
So, another example that's maybe you 
might sort of be able to think about 

48
00:02:55,043 --> 00:02:58,764
coming up in practice in your own work 
is, well, you know, find all the user 

49
00:02:58,764 --> 00:03:03,784
clicks made within five seconds of some 
page load. 

50
00:03:03,784 --> 00:03:07,580
And this is sort of much like the 
distance argument behore, before. 

51
00:03:07,580 --> 00:03:10,940
But now we can think about it in terms of 
time, which is just a one-dimensional the 

52
00:03:10,940 --> 00:03:14,120
one-dimensional distometric is easier to 
define. 

53
00:03:14,120 --> 00:03:18,500
So we say, find the click time minus the 
load time of the page. 

54
00:03:18,500 --> 00:03:23,120
Right, so c.click and p.load, and take 
that absolute value and see where that's 

55
00:03:23,120 --> 00:03:26,626
less than five. 
And so, this might be when you're trying 

56
00:03:26,626 --> 00:03:29,410
to find people who find what they're 
looking for quickly. 

57
00:03:29,410 --> 00:03:32,448
Right, this is a, this is a metric that, 
that web analytics people might use 

58
00:03:32,448 --> 00:03:34,856
frequently. 
Right, if people sort of stare at a page 

59
00:03:34,856 --> 00:03:37,890
for a long time. 
Maybe if it's an article, that might be 

60
00:03:37,890 --> 00:03:40,860
good, that means they're reading the 
article, if it's a navigation page, it 

61
00:03:40,860 --> 00:03:43,668
may be bad. 
That means they don't, they don't find 

62
00:03:43,668 --> 00:03:47,875
what they're looking for quickly. 
Okay, you might also hear about band 

63
00:03:47,875 --> 00:03:54,139
joins or range joins, and this is things 
like find the there might be an interval 

64
00:03:54,139 --> 00:03:58,850
of time. 
Start start time and end time in one 

65
00:03:58,850 --> 00:04:01,022
table. 
And you're trying to find tuples from 

66
00:04:01,022 --> 00:04:03,270
another table that fall within that 
interval. 

67
00:04:03,270 --> 00:04:07,333
Okay. 
And we'll actually see an example of 

68
00:04:07,333 --> 00:04:09,074
that. 
Okay. 

69
00:04:09,074 --> 00:04:12,665
There's other joins, the, another join 
to, to recognize that exists is this 

70
00:04:12,665 --> 00:04:17,866
notion of an outer join. 
And here, what you're saying is, you want 

71
00:04:17,866 --> 00:04:24,561
all the tuples from the left. 
R1, R2, we'll write it like this, with 

72
00:04:24,561 --> 00:04:31,729
this sort of missing leg here. 
You'll want all the tuples from the left 

73
00:04:31,729 --> 00:04:38,648
side, if you've written it this way. 
And if the tuple on the right hand side 

74
00:04:38,648 --> 00:04:41,626
matches, great. 
You put it out, and it's just like a 

75
00:04:41,626 --> 00:04:45,410
regular join. 
But if it, if there is no match, you 

76
00:04:45,410 --> 00:04:51,275
still include the R1 tuple, and you pad 
out the other, the other columns with 

77
00:04:51,275 --> 00:04:57,678
null as needed, okay. 
So any value you don't have, make it a 

78
00:04:57,678 --> 00:05:01,729
null. 
Alright, and so the variants here that 

79
00:05:01,729 --> 00:05:08,810
aren't particularly important is left 
outer join, right outer join, so, whoops, 

80
00:05:08,810 --> 00:05:14,200
geez. 
Left outer join, right outer join, and 

81
00:05:14,200 --> 00:05:20,090
sort of full outer join, which is a 
little bit hard to write. 

82
00:05:22,129 --> 00:05:26,130
because it looks like a cross product. 
The right outer join you really sort of 

83
00:05:26,130 --> 00:05:29,430
never need, because you can always just 
reorder the, the operations. 

84
00:05:29,430 --> 00:05:32,139
Full outer joins means that you want 
everything from both tuples padded out 

85
00:05:32,139 --> 00:05:34,815
with null. 
And, these are sort of ugly to reason 

86
00:05:34,815 --> 00:05:38,631
about formally, but they come up pretty 
often in practice, because especially for 

87
00:05:38,631 --> 00:05:41,864
users, when they're well, I say 
especially for users as opposed to 

88
00:05:41,864 --> 00:05:46,112
applications. 
You know, if you were writing a query by 

89
00:05:46,112 --> 00:05:49,784
hand, basically, many times people find 
it surprising that, that records in their 

90
00:05:49,784 --> 00:05:53,956
table disappear because they joined it 
with another table. 

91
00:05:53,956 --> 00:05:57,271
Alright, but that can happen because you 
only, you, you said that you only want 

92
00:05:57,271 --> 00:06:00,400
pairs of tuples where some condition 
matches. 

93
00:06:00,400 --> 00:06:03,400
And so you might, you might have no 
matches, and things disappear. 

94
00:06:03,400 --> 00:06:07,690
And so outer join comes up as a useful 
way to match more what the, what the SQL 

95
00:06:07,690 --> 00:06:11,910
programmers expect, especially with 
novices. 

96
00:06:11,910 --> 00:06:13,454
Okay. 
Alright. 

97
00:06:13,454 --> 00:06:18,982
And so, an example of this. 
We have two tables here. 

98
00:06:18,982 --> 00:06:25,550
Anonymous patient, and an anonymous job, 
we could do an outer join. 

99
00:06:25,550 --> 00:06:28,210
Now what, what, what, what columns did we 
join on here? 

100
00:06:28,210 --> 00:06:32,120
Well it doesn't specify, we sort of 
omitted it here. 

101
00:06:32,120 --> 00:06:34,621
Although technically, we should write 
that, you know, right there in the 

102
00:06:34,621 --> 00:06:37,329
subscript of the join operator. 
But we didn't, but you, of course, you 

103
00:06:37,329 --> 00:06:41,580
can probably figure it out. 
Well, so you look at the columns that 

104
00:06:41,580 --> 00:06:43,669
they have in common. 
Right, this has an age column and this 

105
00:06:43,669 --> 00:06:46,002
has a zip column. 
And this has an age column and this has a 

106
00:06:46,002 --> 00:06:51,320
zip column. 
And so it's actually on both of those 

107
00:06:51,320 --> 00:06:55,939
columns, alright? 
For every tuple in P, find me a 

108
00:06:55,939 --> 00:07:03,940
corresponding tuple in J, in Anonymous 
Job J, whoops, there's extra in there. 

109
00:07:03,940 --> 00:07:07,860
where age equals 54 and zip equals 98125. 
Okay. 

110
00:07:07,860 --> 00:07:12,930
So, if we had just done a join, then this 
tuple would be removed from the output, 

111
00:07:12,930 --> 00:07:18,340
because it has no corresponding tuple on 
this side. 

112
00:07:18,340 --> 00:07:25,448
There is no 33 98120. 
But because we did an outer join, we do 

113
00:07:25,448 --> 00:07:32,330
include the tuple, and we padded it with 
a null here. 

114
00:07:32,330 --> 00:07:35,532
Okay. 
And we write this in SQL wish I'd 

115
00:07:35,532 --> 00:07:38,507
included this. 
We write this in SQL, let me back up a 

116
00:07:38,507 --> 00:07:50,228
couple of steps here and I'll show you. 
So just like we have join here, you can 

117
00:07:50,228 --> 00:07:56,760
actually write outer join explicitly. 
Outer, if you wanted you to. 

118
00:07:56,760 --> 00:08:00,123
I'm not going to leave that in the slide 
because it'll be confusing, since it's 

119
00:08:00,123 --> 00:08:03,390
out of context but 
And, in fact, you can say left outer 

120
00:08:03,390 --> 00:08:05,675
join, I guess underneath, to match our 
example. 

121
00:08:05,675 --> 00:08:11,230
Okay. 
Put in the slides, the database that 

122
00:08:11,230 --> 00:08:14,947
you'll be using in the assignment is 
SQLite, which has some nice properties 

123
00:08:14,947 --> 00:08:19,688
for a single user case. 
The, the entire database is stored as a 

124
00:08:19,688 --> 00:08:23,080
single file and you can pass it around 
and so on. 

125
00:08:23,080 --> 00:08:25,746
So it's a good tool to sort of have in 
your toolbox, it's one of the reasons why 

126
00:08:25,746 --> 00:08:29,316
I selected for the assignments. 
But it actually has some limitations, and 

127
00:08:29,316 --> 00:08:32,370
one of which is, it can't express certain 
kind of outer joins. 

128
00:08:32,370 --> 00:08:34,730
Okay, in particular, full outer join.