CMU Database Group · 1:23:38 · https://www.youtube.com/watch?v=APqWIjtzNGE
0:05 official members bounce bust off the Chrome realize it's real hell what we call Home official members bounce bust off the Chrome realize it's real hell where we from the inside one I Vision fat licks and M Clips the Chrome will make the average imitator do back flips you like a pistol to put the best around the issue never miss coming that's official before we get started I have to read this out
0:33 um so I do not have child protection clearance for ACT 153 uh this the state law in Pennsylvania so if anybody here is under the age 18 uh you cannot be in this classroom no it's not a joke seriously I don't think they would have notified me just make sure that anybody here who's who's not uh 18 or older um it's a pen state law criminal history patch um I I don't have I I don't have the crial background history or crial history background to pass this so uh again if you're everybody coming in if you're under 18 please leave the room um
1:08 with that aside I want to give a quick shout out to people who's helped us get here where we are today so this is e in crookland uh JL in Seattle uh and then DJ drop tables unfortunately passed away the summer so rip to him and then DJ Mushu is in lockdown which is a whole another issue uh so we send our respect for him okay all right so with that out of the way uh let's get into to databases so I sort of mentioned this in lecture zero which I did record re-record today I apologize for uh the mic but it should be better now um so as we go along throughout the semester you will see I get very very excited about databases and this is for sort of a a very important reason I only care about two things in my life right the first thing is my wife and my biological
1:52 daughter and then the second thing is databases I don't care about anything else I don't talk to my family they're all Trump supporters the antiac I don't care about them I don't have any hobbies it's just databases I live what is what you call a database Centric lifestyle and hopefully I hope impart to you guys what that means what that entails and you can continue down the path Beyond this course now earlier last week someone posted this on the seam you Reddit
2:18 right they want to know whether taking 440 or 445 is harder uh because they want to spend their time doing other things in their life right so I chime in and say whoever this person is should not be the course because I don't care whether they think it's hard or easy right you will see throughout the semester that if you take a Viewpoint of everything is pretty much a database problem and then all your time should be spending working on databases uh then you you'll be happier in your life uh so again if I don't know if someone's in the class here that post this uh you don't
2:50 belong uh again quickly to reminder about the course Logistics I everything is on the course web page all the announcements and discussion for projects homeworks Logistics and other things we've done through Piaza all the homeworks and projects will be submitted through grade scope and autograd your final grades for the actually the mid-semester grades and the final grades for all your projects and homeworks will be in final exams will be posted on canvas um if you're on the wait list I think our Max Capacity is 140 before the Fire Marshall shows up uh and as of uh an hour or so ago we have six open seats
3:20 and the administrators will fill off people uh from the weight list into that uh so if you're still on the weight list you may have a chance to get in but I I can't guarantee it okay and then if you're not at CMU
3:30 uh we make everything available for the projects through this grade scope use this code make sure you put yourself as uh as as University of Carnegie melon everybody in this room right now do not do this because then then you won't get a grade and we ask everyone else who's not at CMU who's watching the videos don't post your Solutions on GitHub don't do the stupid thing of spitting the pr with with your code because we're going to put a Wall of Shame up for that and then don't email myself or the Tas if you're not a senior student everybody else here in the class please post on piao and we will respond any questions or comments about any these
4:01 things again if you're coming in if you're not 18 or older you have to leave the room because of the ACT 153 okay all right so today's agenda we're going to talk about quick background what database systems are that sort of sets us up for what the course will be about uh we'll spend most of our time talking about the relational model and relational algebra this is going to be the Bedrock for how most database systems that you're going to care about
4:23 uh not all but but most systems uh will be predicated on this we'll talk a little bit about alternative data models that are out there like aod DBS document stuff Json stuff um and Vector databases U but these will sort of be anary to what we talk about this course the core ideas beyond the relational model of how we're going to build these these datab system will be applicable to these other alternative data models it's just I care less about them right because I I care about SQL I care about the relation data model and as I said on Piaza yesterday
4:56 uh we'll have since this comes up every year people always sort of high level questions about databases throughout the semester I want to try to cover as much as I can at the very beginning uh so if you have any Q&A if you have any questions you want to ask me at the end we can we can take those
5:09 okay and again as I said on in lecture zero uh I get very excited about databases I talk very fast please tell me to stop and slow down and if you have any questions please interrupt me uh and ask me to repeat myself and and I'm not going to I refuse to answer any questions about the lecture uh at the end of class so don't line up and say you know what did you say on lecture you know Slide Five said this what do you mean right interrupt me as a go along because if you have a question somebody else also probably has the same question
5:33 uh and so we want to cover these things okay all right databases the second most important thing in my life um can anybody give me an example of a database yes click house he says click house anybody else aary you said a dictionary yeah yeah that's pretty good what else
6:02 nobody can can nobody can my database the contact manager on your phone contact manager phone good excellent one more IM say what IMDb IMDb good excellent all right so he said click house he said dictionary said he said contct manager he said I'm DB so click housee is a database management system
6:20 the other examples are all databases and and so what's tricky in in well the common semantics of how people describe databases is usually they meant the database systems which we'll focus on this class but I want to First s discover discuss what a database is and then how we're going to build a databas man system to manage it
6:39 okay so database is going to be an organized collection of data no surprise there that are related to way in in in some some Manner and it's meant to model some aspect of the real world so he said dictionary and what is the dictionary a bunch of words and then their definitions and maybe like the part of speech or whatever right so that's modeling sort of this you know the vocabulary you said a contact manager that's modeling someone keeping track of of pencil on paper here's all my contacts and their phone numbers and email addresses right you're modeling some aspect of the real world and you're trying to capture all the constraints
7:13 and and aspects of that real word concept in in your database and again I'm highly biased because all I care about is databases uh but the database is going to be the core concept among all Computer Applications and almost all of computer science the end day what is a computer doing some input comes in you do something on data you produce some output that's a database that middle part most almost always as a database what is a file system file system is a database if you use a website what are you doing you're interacting some form that talks to a database right what is an llm it's a database more or
7:49 less right so this is be the most important thing in in in computer science again I'm biased but you're going to encounter databases all throughout your life and what this class is going to teach you is to understand what a database management system is trying to do for you right why are things going slow why is my query coming back with with garbage right so if you understand what the how the components are implemented what they're doing you're in a better position to to use a database system to to to manage a database so no matter where you go off and become a you know database systems internal developer like all the companies that are coming in a few weeks to talk to us or you go off and do something else the end of the day you're going to interact with databases because that's what really life is all about
8:32 everyone's got a smartphone here right all those applications are running SQL light SQL light is a database management system it's the most widely deployed one right so we'll understand how sqlite is actually implemented and in homework one you you'll use
8:44 sqlite so let's use it let's discuss a toy example and we can use that as to explain you know the various parts of the oral model and and database man systems as we go along so assume we're trying to build a a Spotify clone right it's some kind a digital music store and we want to keep track of the artists that are putting out music and then the albums that those artists release right we want to know what you know for given album what artist appears on those
9:08 albums so a really simple implementation of the database could just be a bunch of files on disk right my example here I'm showing them as csvs or comma separative values but it could be Json the kids love yaml you could do yaml it doesn't matter right but we're going to have a separate file per per per entity so I a file for the artists and artists have a name the year that they came out and maybe the country that they're located in and then we'll have albums with the name of the the the the album the artist that appears on the album and then the year the album is
9:41 released right this is a database I don't recommend doing it this way but you could do it this way a bunch of files on disk so now anytime you want to update or insert a new record we just could go open the file you know pen to the end of it or if you need to answer a query we just scan through it untilt we find the answer that we want right so say want answer query like what year did the jiz go go solo well I could write some python code that just opens the file up reads every line
10:09 parses the parses it as a CSV to get back an array or or list of values I know that I'm trying to look up the the name jiza well the name is the first field in my file so I just jump to the the first element of the array check to see whether that value equals jiza if it does then I print it out
10:31 right this is the database system more or less well this is interacting with the database uh that I'm basically embedding The Logical datas system inside my application to do this is this a good idea or a bad idea I guess it says strawman at the top so you know it's a bad idea so why is it a bad
10:52 idea yes so we kind of need to look over every entry so he says you kind of need need to look over every entry yes so my example here my file has three lines okay who cares like that that'll sit in L1 cache it'll be super fast but always when you think about in computer science especially in databases think about what happens if you scale up to really large numbers so what if my line what if my file had a billion records do I want to be scanning through and parsing every single uh line just to find the element I'm looking for one entry
11:23 no what are some other problems yes you have to rewrite the code every time you want to change your query excellent so he says you have to rewrite the code every time you want to change your query worse than that what if I want to add a new new field right now I gotta change much of my code as well is updating the file that
11:43 sucks maybe one more in the back yes yes so he says what if you come across a line that's reordered in a different way right maybe like they SWA the some someone some stupid somebody stupid again these are just files on disc they open up a text editor and flip the order of these things and now my python code is going to choke on it right or even like what if I put instead of the you know the year 1990 I put a phone number in what happens
12:13 then right so there's a bunch of problems doing this approach but this is this is what the datab system is going to prevent you from from encountering these these issues because it'll manage all these things for you so there's some other issues we have to deal with right so in my in my file I just if if if a if an artist put puts out multiple albums then in my my album file I'm just repeating their name over and over again wuen Clan wuang Clan wuen Clan but how do I make sure that someone doesn't like drop an n in the you know the name of the wuen clan and now it's Wang claw right well I know that they should be the same thing but the data says that they're
12:51 different we brought this up before what have someone comes along and overwrites the the album name with a weird string puts email address in or puts in number that shouldn't be there and then we didn't talk about this but in my toy example I assume that there was one artist per
13:09 album but you know if it's if it's a mixtape there's a lot of artists on that and in my my simple example I couldn't couldn't handle that then what happens is what if I delete an artist by accident or by choice from the artist file but now I got a bunch of albums that rep that are you know that mention an artist that doesn't exist in my my table or my my file so I basically have a dangling pointer
13:35 now we've talked about how on the implementation side how do we find a particular record well just iterating over single file and parsing it one by one that's terrible that's slow what if you have another application that wants to use the same database well now I got to basically copy and paste the code that I wrote to parse that file and and get records out and put it to my other application but what if I wrote the first version of the application in Python then I rewrote it in Rust now I got to translate all the python code to rust code that sucks but then what also what if the file sorry what if the the the other application is running on a different machine or bunch of cell phones now I got to make sure that they all the application
14:13 implementations can access that file some way to like a distribut a file system which is the database by the way and then what happens if we have two threads try to write to the same file at the same time well we can do something really really stupid and just let the OS lock stuff for us lock the file and then prevent only one only allow one thread to write into it at a time but a reoccurring theme you're going to see throughout the semester is in the world of databases the OS is our Frenemy we never want to let it do anything for us so letting the OS lock files for us is a bad idea because we're database people we can always do it better than they can
14:46 so only allowing one thread to write it to the file at a time that is actually what SQL light does but SQL light's meant to run on cellphones you know you're running a machine with you know thousand cores you don't want to do that
14:58 and the OS is always going to be more inefficient anyway then lastly what happens if we're modifying the the the file and we going to write a new record we write half of it and then it crashes the the the machine crashes someone chps over the power cord lightning strikes the Transformer whatever now we come back online what should be in our
15:20 file well if we just write to the file we'll just see whatever we wrote before to the crash but that's invalid right now we have a record that's missing half of it and then what if we want to allow multiple shees to access the the the file or the database uh and we want to make sure that and if any one of those machines goes down we can keep running and still you know serve queries serve
15:41 requests well now I got to basically Implement a bunch of load balancing stuff to to handle accessing the file that sucks so this is just a quick smattering of the problems that we're going to have to solve throughout the entire semester to make it so people don't have to do stupid things like relying on the operating system or managing a stuff in application
16:00 code right and this is what a database management system is going to do for you right it's going to be the software that that allows applications to store analyze query data uh in a database and a general purpose database system will be one that can support the any arbitrary schema within reason of course uh it can allow any arbitrary queries meaning it's not hardcoded just to do that one look up on the jiza you can change the query to do any look up on any artist or or any field or do any kind of
16:30 transformation and it's going to do this according to what we'll call a data model it's a way a high level representation of what is in a database right and again just to push this uh this this point home further database systems are some of the most widely deployed and widely tested and vetted pieces of software in the world that maybe Rivals you know maybe operating system is the only one I could think of maybe some ineda systems right
16:56 there's you know multi-billion dollar corporations that are running off of database systems that are tested and sold by Major Enterprises there's a lot of money involved in database both you know building them and selling them 's a lot of money riding on a datab system operating
17:09 correctly and so at no point say again if you go off in the real world and you're do a startup or whatever at no point you should you say to yourself oh I'm just going to build my own you know databas system in my application that's a bad idea you're going to have problems we going to rely on these existing uh existing tools that are out there and again this class is going to teach you how to how to do
17:31 it all right so a data model is going to be this high level abstraction that is going to represent data in a database again According to some to some scheme we we'll see in a second and within for
17:47 most database systems support only one data model like a relational database or a document database the lines start to get blurred more recently because in relational databases you can store documents you can store Json now and if field and now the document databases all support SQL and like relational like things on top of Json so in some cases it's clear that there there's a distinction between the data models uh but in the more more widely played systems again the lines get
18:12 blurry and so given a data model your database will be defined according to a schema that just specifies I have these tables or these collections of data they have these attributes with this name and this data type again we'll see this throughout the entire semester but it's a way to to specify the structure of the things you want to store in your database because without a schema it's just a bunch of random bits and it doesn't mean anything right the schema is going allow you to to provide a
18:41 structure to to the data so that you can write queries against it another way I think about this save a bunch of log files for my application server it's a bunch of text lines right you know with time stamps and so forth if I don't have any structure on top of that I then there's no way to sort of find the data I'm looking for but if I say oh a log file entry is going to have a timestamp
19:01 followed by maybe an event code followed by a string that with the event well that's a schema that's a structure that I can then run queries on top of it because otherwise again if it's just a random bunch of blob random bunch of bits the data is useless the data is meaningless yes how this the data model
19:20 model also the data model is we'll see this second a data model is the the abstraction for how you define collections of data and then and then their relationships between other collections the schema says okay within that data model I have these collections that have these attributes with these these types think of it like a it's almost like a uh like a class versus object in like Java world the class is the definition of of the of like the the the data model and then the instantiation
19:53 would be actually that's a bad example um it would be like a I in the programming language you specify like in Java the Java you has a has a way to define how you represent data and then you you would create instances of it in
20:10 classes let's go further along I think it's a b ex able to but it I think it makes sense when you start see uh when you start seeing differentiations between it okay other questions okay so I'm going to be highly highly biased the entire semester I love the relational data model I think it's how every datab system should be implemented because relational model can be contorted at least in the modern version of it into any possible data model you would care about except for one I'll talk about in a second so most database systems we're to talk about this semester and most database systems that are in the real world that you've heard of are very likely going to be relational databases um but it's not to say that's it's the only one out there
20:53 right there's these key value stores that are out there things like rock DB level DB um reddis sort of like this where you sort of have a key and then a value and that's it and there's no meaning to the actual value except for what the application puts upon it so this is typically used for simple applications or caching like you know cookie ID to some payload then you have this whole sort of category what falls under the moniker no SQL which is ironic now because now they now they really mean at the beginning when no SQL came out they were like oh guys you know SQL sucks we're not doing any SQL no SQL now they really mean now they say oh no SQL really means not only SQL right because they've seen the light and basically become relational
21:31 databases um so the the document stuff the Json databases probably the ones that are you've heard about the most like mongodb would would be a document database uh wide column or column family is a subset of of document Json databases it's like uh uh Google big table was this uh Cassandra was this then you have these uh array databases so vectors matrices and tensors uh tensors are probably the thing you don't want to store in inter relational database because it's since it's like a multi-dimensional array it's it's kind of weird to do that in a relational model um even though the SQL standard last year just added it multidimensional
22:13 arrays and then there's these hod podge of these ones at the end uh hierle Network semantic ntid relationship I'll talk about Network one a little bit from kodil but these are like stuff from the 70s and 80s they were doing cocaine back then they were experimenting but it basically the world has come back to realize that the relational model is the right way to go every 10 years though there's always this repeat where someone says oh relational model stupid SQL stupid we're GNA have a new data model
22:38 and then everyone gets all excited about that on Hacker News and then they eventually come around say oh yeah relational model is is the right idea so we're right now we're in the phase where all these guys have said oh yeah SQL is actually a good idea and then the next step is going to be the vector databases come back and say SQL is a good idea uh but we'll get there all right so again this course is going to be about relational databases but it's not to say that the things we're talking about can't be applied to the other data models it's just you know most of the systems you encounter are going to be
23:07 relational all right so why is relational model matter matter and why do I why am I so keen on it well if you go back to like the 60s and early early 70s the there wasn't this sort of plethora of database systems that we have now uh there was a small number of them and it was very difficult to build database applications like think of like Mainframe days um and so in the early days the one the first dat systems that was built thing called IDs for integrated data store uh that was actually built by GE in
23:37 1965 or 66 IMS was a hierle database built by IBM to manage the Apollo moon mission the keeping track of all the parts to build the the the the rocket going up and then part of this IDs work there was this thing called kodil which came out of the cball world I was basically trying to Define what the API is how you would interact with with the database and and so back in the day in the 60s and 70s computers were very very expensive and humans were relatively cheap the labor of humans were relatively cheap to uh computers so it wasn't that big of a deal that people had to spend a lot of time rewriting their code as he brought up every time you to change make a change to your database right if you use these other uh other data models and that's because there was a tight coupling between at The Logical level how you're defining your database and then how the data system actually physically represented
24:26 it so now in your application code you had to be aware of how the D was laid out in the bits on disk and how things were connected with pointers and you had to basically Traverse those those data structures manually in your code right so that meant that anytime there was a change in your database schema you have to go back and rewrite all your application code to account for that so an example would be in IMS least the early days you would you would Define a table and then you would tell the they I want to start it either either as a hash table or a B tree and then say if you made a mistake said oh I really want to store you know I decided to do a hash table but I really need to do range scans and you can't do range scans on a hash table and I want to switch it to a b tree well I got to dump the data out
25:07 then load it back in as a b tree then rewrite all my application code because now the API to that table has changed because it went from a hash table to a b Tre so there was this guy at IBM uh who basically saw all these programmers doing the same thing over again making all these these mundane changes to their Davis applications every single time there was a change and there's always going to be changes in databases right because as the world evolves or the the data you're capturing evolves you want to you know evolve your
25:36 database so there's this guy named Ted Cod who was originally a mathematician he did his PhD in mathematics um he joins IBM research in in New York and as I said he was seeing all these programmers doing the same thing over and over again is rewriting their applications every single time the the the layout or schema changed and he obviously thought that there has to be a better way to do this and so he devised the relational model in 1969 as a sort of abstraction uh to a database based on sets or sorry based on relations which I'll explain that in a second and that
26:11 there would be this logical connection between data through values rather than physical connections like pointers and offsets and things on disk as you would have to do in in the other data models so the first paper that defined the relational model came out in 1969 I think this was an internal tech report at uh at IBM but the one that's really really famous that everyone refers to is is this one here that came out in the cacm in uh in 1970 so if you say what's the first paper relational model people typically point to this other one here
26:42 and so when this came out all the academics thought this was the greatest thing ever this is clearly how we should be building database systems but IBM poo pooed it or ignored it right because they were making so much money on IMS which is the high Echo database system and then one of their own employees comes along and say hey the thing you're making a lot of money on is actually stupid you don't want to do this way you want to do this other way for this system that I I don't hasn't actually been implemented but here's the better way to to represent databases again he was a mathematician he didn't he he wasn't building a system at the time and actually in this first paper here it's all mathematics there is no there is no SQL at this time he didn't find a programming language it's all through relational algebra and how you
27:21 manipulate databases so from IBM's perspective they were like well we can't do anything with this it's just a paper right so but eventually IBM did do this did take the paper uh but not in New York act AC San Jose they got a team together which will cover throughout the semester and actually build one of the first relational databases as a prototype based on Ted cod's
27:43 paper so I mentioned kodil Kil was a highle database that was that was spearheaded by this the the guy that building IDs or I'm um a GE um and so there's a sort of back and forth between the relational guys
27:58 uh the people that like in Academia like relational datas is the right way to go and then all the cell people all the Cobalt people said no no no cell is the way the right way to go and so actually who has ever heard of cotol
28:09 ktool no one right because it's dead right uh so codale was based on these like sets so you would have you would Define like these collections as if tables and you would Define the relationships between them through these sets and you would and you would basically iterate over every element each set and follow pointers to go find the data that that you're looking for and so there was this uh famous Workshop in 1974 at at in Michigan where they got all the people from the codale camp and all people from relational database Camp put them in a single room and they they fought over it so this is a very very famous meeting uh obviously Ted cob was there but there's been four four touring Awards in databases and all four of those people were there so we're going to cover a bunch of these guys uh throughout the semester uh Bachman was the the kotto sale guy He's dead Jim Gray and Ed two- phase locking we'll have a whole lecture on that he's dead
29:01 and then Stonebreaker uh invented Ingress and postgress and a bunch of other stuff uh that you may have heard of before uh he's still alive um he's 80 turns 81 this year so he was my pH adviser he's brilliant um but basically the the all the Koto guys were saying hey this relational model stuff you can't actually build a real system doing this right uh people aren't going to understand what it means to have relations and tables and then furthermore you if you're going to be programming at a high level language
29:29 again SQL uh the guys that been to SQL were were actually at this conference too um but at the time SEL was you know very early like you're never going be able to to take SQL and compile it to a program that can run efficiently right
29:43 so they all complained the cot cell guy said that that relational database is a bad idea but then the relational guy says they all say that this this cotell thing these these sets and you have to walk through these records and deal with the physical data structure that's all a bad idea too like it's makes the makes the application brittle makes the application more likely to break when one part of your you know your of the database breaks it breaks all the other stuff because it relies on the physical Integrity of of data right and as I said nobody here has ever heard of Cil the relational Camp one but again as I was saying every 10 years people forget all the things we've learned before and now the graph database guys are basically making the same claims now as the Coto people did in the
30:22 70s all right so what is the relational model so it's a data model that that's going to find a abstraction for a database based on relations to avoid the cost of having to maintain the the the implicit knowledge of what the data looks like physically in your application code so there's three key ideas in the the relational model first is that we're going to store our database in as simple data structures I.E relations or tables and that we don't expose that information to the application code right you get this abstraction just I tables and I can interact with
30:59 them the physical storage the way actually datab system is going to going to actually write down the bits of your of your tables is left up to the implementation so the idea here is that say I have a database I use a datab system I have my database I store A datab system that stores things on disk but may maybe I want to store things in you know uh in memory in in memory database well if I just Define things through through relations and interact it through SQL in theory I could take my database out of the disc database and put it into the in memory database where some new some new storage device comes along I just plop it in that one and now I don't have to change any of my application code even though the physical layout of the bits has changed
31:39 now I say in in theory this should work as we see next class the there is a SQL standard nobody follows it exactly uh the only sort of defacto SQL standard we have now would be postgress because everyone can take the post parser and reuse that but we'll see many cases where if just because I have you know two relational databases doesn't mean they're always going to be compatible so again I say in theory you should be able to do this but not
32:04 always and then at the last one again is that instead of writing procedural code like a lowlevel for Loops to iterator single uh you know one record at a time as I showed my toy example before we're going to write queries in some kind of high level language uh and the spoiler is going to be SQL but we have to do relation algebra first before we get there and then that way we just say here's the answer that I want and it's up to databas system to figure out what's the most efficient way to to implement it to execute
32:32 it right so my example before where I said I was parsing that file to try to find one record and in said what if I have a billion records uh then that would really be slow but if I wrote it as a SQL query and say I had a billion records and things went slow well then I can go back and add an index so I can jump to the exact record that I want think of like a glossery in a text book I can jump to the page I want for for some keyword and then now I don't again I don't to rewrite my application code because I have an index index because I've extracted away the the actual the implementation of both the data and the query
33:07 plan so we'll see as we go throughout the semester again in back in the 70s people were making the same arguments uh when C came along the C programming language that oh you know there's never going to be a compiler that can generate assembly uh for C code as well as a human can write of course now we know that's crazy right compilers are very very efficient same thing was said about SQL back in the day from the codell guys that no no computer program is going to be able to generate a query plan for a SQL query that's as efficient as what a human could write
33:36 themselves uh and of course again nobody writes SQL by hand anymore or at least sorry nobody writes the query Plans by hand let let the D system do it for you all right so there's going to be sort of three comp three components of the relational model there's going to be the structure of of the database again that's going to the definition of of the tables we have you can use the term tables and relations interchangeably but to be pedantic you would say relations not tables right you define the what's going to be in your relations and then their contents and you define this independent of their physical
34:07 representation and we we'll cover that a bit further next slide and then you can also Define what we'll call sort of Integrity constraints and these are going to be definitions of what the data is allowed to look like in accordance to whatever you're trying to model in the real world right so if you store someone's age in a database we know no one no no one can be negative right there's nobody that's negative 10 years old so we can put a constraint in our in our table say
34:32 this value of this age can never be less than zero and the last one is going to be the manipulation mechanism and this is basically the the API the programming interface that that is exposed to us to allow us to access and modify the contents in our in in our database and this is what relational algebra will this is what relational algebra will be that we'll see in a second but I'm going to cover this Independence thing first a little bit more because this is it seems obvious now but again in the 1970s this was considered you know
35:01 groundbreaking but the idea of data independ is that again we don't want to uh have to expose necessarily the physical layout of data on whatever storage device we're storing it on uh to the application so they can program against it using a high level
35:18 extraction right so at the lowest level there's database storage I'm not defining what that is because it could be in memory it could be an SSD it could be an object store like S3 again for our purposes here it doesn't matter and then you define a physical schema of of basically how to represent the the database you're trying to store in that that database storage device so this would be defining the pages the layouts of the pages like where how the bits are actually laid out in a single page where the files are how the files are organized is your database one file multiple file multiple directories all right what do your extents look like are you packing multiple you know files in a single or sorry multiple pages in a single St or is a single St for part
35:57 table all that is is handled at the physical schema level and then above that you have the logical schema which is how the application is going to Define what's in my my database I have these tables I have these columns I have these constraints on them typically you would do this through through sqle like a a crate crate table
36:16 command then I have a further abstraction on top of that called an external schema and this is where I can Define sort of virtual tables on top of my existing tables these are called views again we'll cover this uh throughout the semester but the idea here is that say I have some table of student records and I want to expose to different applications
36:37 uh portions of what's in that table so say like ACC accounting needs to know your social security number but they don't need to know your your grades say it's all on a single table so I can create a view that says this application can see the table with with these columns and this application can see the table of these other columns even though physically it's the same table it's just exposed to you in a different uh different
36:59 way and above that very top this is the application code right this is the python code JavaScript whatever doesn't matter that's going to interact with with our our database So Physical Independence would be this part here where I could Define my tables uh and and their contents but I don't care about how they're actually being physically stored and I have a further level of logical Independence
37:22 where I could say I have these logical tables but then I could sort of recompose them in different ways for different applications or different users and they don't need to know how things are actually being stored at The Logical level right below it so this physical data Independence
37:38 this was this was a big deal because Cod of sale couldn't do this in your application code you had to know how to follow the pointers of the data structures that the data system was storing for you relational model says there is no notional pointers right even though we're going to use pointers to implement our system but we don't expose that to to the application code
37:58 again it's one of those things where it seems obvious now when you hear it but back in the day back in the day this was this was groundbreaking all right so let's go a bit more now what you know what relations look like so as I said I'm going to could use the term relation interchangeably with table but to be uh sort of again pedantic to the relational model we'll call them relations so a relation going to be an unordered set of of data that contains a relationship of
38:24 attributes uh that represent some in the world right so again going back to the artist table a one record or one entity would be an artist that exists like the wuang clan and we would have all the attributes that represent the information or the metadata or sorry not the metadata the attributes of the of that entity together within within a record and a record we're going to call Tuple again think of I want use the term row because a row mean applies to a row store we'll see column stores later on but a tuple is is going to represent some entity or instance of an entity within my
39:01 relation and so the original relational model had to Define that the all the the attributes you would have in your uh in in in in your relation had to be Atomic or scalar you couldn't have lists you couldn't have like nested documents like Json that has s OB since obviously been relaxed in the SQL standard and most Data Systems Support these things but back in the 70s you couldn't do
39:22 this we'll also have a special value of null uh if it's because we can Define that things can't be null in in our in our relations but this is just a way to say that the value of something uh is unknown for a given
39:37 attribute so you would say a again to be sort of be pedantically correct you would say a Nary relation meaning a relation with n attributes that's more or less equivalent to a table with n columns right and similar to if you say oh I'm using what database are using I'm using my SQL or postgress people know what you mean so if you say table with these columns know what you
39:59 mean so a core concept of of relation model is this is this idea of having a primary key and a primary key is going to be some some set of attributes that uniquely represent one entity within our within our
40:17 relation right so say you know for Simplicity we' have like we could say that there's no no artist can have the same name so we could say that's our primary key of course we know that doesn't you know that's not correct in the real world but for our purposes here we can say oh yeah there's there's the primary key is a name for for an artist so given for a given name like a string I can jump to one tubal that has that
40:39 information so you don't always have to define a primary key uh most relational dat will let you define tables without it what we'll see later on is underneath the covers if you don't Define a primary key some SES will actually create one for you and then even though you may Define a primary key some systems May ignore that treat that as still like a unique constraint like the value of the primary key is still unique but underneath the covers it maintains its own primary key
41:05 so sqlite does this sqlite has its own incrementing incrementing value as the primary key even though and treats whatever you define as primary key as a unique attribute so going back here as I said before we could use the name as the primary key but that's that's bad because obviously artists could have the same name so to get around this we could rely on like a a synthetic ID
41:28 uh like like a number that could represent you know that that given attribute or sorry given tupal right and they could just be incremented monotonically 101 102 103 so the Seagle standard allows you to Def find what are called identity columns again think of these like synthetic values that don't really map to things in the real world but it's going to allow us in our application code to uniquely Define where where that data is located SQL standard calls it identity
41:53 post Oracle called these sequences and as we'll see throughout the semester my SQL for whatever reason does things differently they call it an auto increment key right so it's it would be this column here so in addition of the primary Keys we also have foreign keys and the foreign keys are going to allow us to map some some set of attributes from one relation to another relation to Define that those things are linked together
42:17 and again this is different what from what codell did cotell would actually have pointers from one one record to another record that you would literally follow either through through memory or through dis dis access to go find the things that it was connected to but in the relational model instead we're going to use values to to represent those those relationships so say before remember we wanted to be able to keep track of all the artists in our album but if the album only has one artist well that's fine because we just stored the single
42:48 value uh but what if I have a mixtape again with multiple multiple artists on it now again I said you can store arrays uh in as attributes ignore that for now and in in the sort of in the true relational model form you would actually have to store this as a separate cross reference table that keeps track of for given artist ID what album do they appear on and so these would be called the foreign Keys you would have a foreign key from the artist table the artist ID that points to the record on the artist table and you have an Alum ID that's a far key pointing to
43:22 uh the album table and again it's up to the data system to decide how to make this work efficiently typically there's going to be an index that says for a for this record here given a look up on if I have an album ID I have to have an index on the on that ID in the other table so when I go insert something into this table and I need to quickly check does this album ID actually exist I can do quickly do that
43:47 lookup and these foreign keys are allow us to handle constraints or other issues where like if now I delete a artist and I want to Cascade and remove all it all their albums well I can follow this table to go find all the albums that they belong to and then go make sure I delete things here or in some cases you can prevent you from deleting things you say I can't delete a record if I know I have a forign key reference over
44:09 here basically the data system is is preventing you from shooting yourself in the foot and you may think oh I'm a c student I'm not GNA make mistakes everybody makes mistakes right and so the DAT systm can prevent you from causing a lot of
44:22 problems so I sort of mentioned this with the foreign keys but the idea of constraints these are way to define what data is allowed to look like uh and that could be either within a single attribute uh or multiple attribute within a uh within a tupal or what values are allowed to look like across multiple tupal within the with within a table within a relation so we said oh the the the artist ID has to be unique because that's the primary key that's a constraint right that's saying that there's only one tool can have a given artist ID and across the entire table
44:57 so the most common ones are going to be unique keys and then the foreign key references uh the SQL standard from 1992 has this idea of basically Global asserts but I think maybe some systems implement this but they're really used because they're really slow because think of like every single time I insert into the table I got to run this other query to see whether my my constraint has been violated or not so the most common you'll see them is defined in the table itself right so if I could say I have a name it's going to be a barart that's a string string type and then not null that not null part is the constraint that says you can't insert a record with it with a null
45:33 name another one could be explicit check down here you could say that the year has to be greater than 1900 because you know nobody can be born in 1800 it's not correct but you know in the real world but like that's the idea of how you could apply different constraints like that and I said you have you have these Global asserts is a create assertion uh command you basically put a SQL statement in every single time you you modify the table this thing runs but again they're super slow again always think big I have a billion records and I got to scan to make sure some constraints not violate across those billion records every single update
46:07 update that table I got to run that across a billion tub and that's bad all right so then next thing is the DML and this basically the way we're going to manipulate interact with the the database through the relational model and there's sort of two categories of uh of you know the DML you could have a programing language which you could have for in a database the first is going to be procedural but this is basically defining the exact steps you want the data system to execute in order to run your query and the other one would be non-procedural or declarative
46:39 where this is you're specifying the answer you want that the data to compute for you you don't Define how you should you want to compute it uh you say but this is just what I want so for this class here this today's lecture we're going to focus on this one because this is be relational algebra and as I said no datab expose a relational algebra interface to you because it's just it's too cumbersome to write it uh and again you're basically defining what the the query plan should
47:05 be most systems will will support this a declarative language and this will be based on what we call relational calculus uh for this class you don't need to know relational calculus but it's a higher higher level form of defining uh you know operations over the relational model so if you take the advanced class or we might do the special topics class in the in the spring semester on query optimizers the relational calculus will come up
47:30 sparingly uh but for for our purposes here today in this semester we only need to care about relational algebra earlier inversions of this course used to teach relational calculus but it's nobody uses that in the real world unless you're burning query
47:44 Optimizer all right so relational algebra is going to be Bas or it's going to Define so the raal model is going to Define uh seven Primitives and the idea here is that we can use these to construct any possible query you would want to have on a relational database now not entirely true right Ted CA Ral paper in the 70s to find these these uh these seven seven Primitives it's since been expanded because you this doesn't handle things like sorting or aggregations or group eyes uh but I want to cover the core uh the core Primitives
48:16 and then it's sort of trival to see how you could extend that to do other things that you you want to do in a real system so we're going to be able to chain these things together to compute more complex queries but I'm going to go them each each of them one by
48:29 one so the most basic operation you can do is is a select um and this is basically the first order predicate logic to say here's how to identify the tobs that I want for a given relation and it could be what I'll call the base relation like whatever I defined in my my database I'm going directly at at at those tables or could be from the output of another relational operator and that's feeding into my to my select
48:54 operator and so basically you're going to find predicates that uh be based on Boolean logic to Define what tupes are allowed to sat or what tupal satisfy the the constraints you want on the data and then any T that that does satisfy is then emitted as output so say I have a really simple table or relation with two attributes a ID and B ID I can define a uh do a select where the predicate is where a ID equals A2 against the relation R and that just matches any any record where a a a ID equals
49:28 A2 right it's like the wear clause in a select statement if you remember that and you can combine these things together conjunctions and disjunctions so I can say find me all the the the two BS from R where a ID equals 2 and b d is greater than 102 and it produces that relation as the
49:47 output right so for me the way I always remember this is like the it's the the lowercase Sigma symbol S for Sigma s for select easy nemonic to remember that so in SQL which most going to be writing it's just the wear Clause right so select start from R and then my wear Clause be the predicate for how I'm filtering
50:10 tubes and that's equivalent to defining the the select operator here all right the next thing we do is projection and this is where we're defining what the output should look like in terms of what attributes we care about from our input that that we want to produce as the output as well as how to manipulate that those attributes in any given way so again same same relation on r with Aid and B ID I could have a projection where I take whatever the the input is from the from this inter relation sorry in operator here so here I'm doing a select or uh on Aid equals A2 and then I take the output of this inter select and now project it where I take the bid value or B attribute subtract 100 to it and then also produce Aid as the output so not only am I selecting what attributes I want I can change the order of them I can manipulate them I can do arithmetic
51:06 operations string functions whatever you want right and you're just defining what you want the output to look like from any given input and that's equivalent to the like the select operator the projection Clause of a select operator in in
51:20 SQL so far so good so then now we we going to be able to start com Bing relations together because again the idea is that instead of having this one giant relation with everything possible attribute I could have for whatever whatever is it whatever it is I'm trying to model my database I'm want to break it up into relations and then combine them together to to reconstruct the the original form so I have the union operator which basically just takes all the attributes
51:48 uh from one side and all the on the other side and uh just s of mashes them together into a single single relation in this case here this this operator only works if the uh if the the both relations you're trying to Union have the same the same attributes with the same
52:08 types right because you're literally taking concatenating you know taking R putting S at the bottom of it and that's the output so in SLE you can do this with there's there is a unit operator uh where you basically combine the the values of two select statements and again they have to have the same attributes because you're just concatenating the two bols combining them into a single output
52:28 of course there's a union there's an intersection right an intersection is just taking the uh finding the where sorry back yes this question is if there's in for Union if there's a two that exist in both tables will will it reuse
52:50 them uh let me about this in the original relational model no because it's based on in SQL the answer is yes I other way around in in the Rel model it'll remove duplicates in SQL it will keep them so in SQL if you do a union it keeps them you put Union all then uh it removes them because by default they want to be efficient because it's extra work to find the
53:21 duplicates I'll say too the this is unordered so even though I'm showing R followed by S this is going be a key thing we see throughout uh throughout the semester is the order of of of the relational model and SQL is undefined so it's okay for things to end up being you maybe inserted into your table and then when you read them back they come back in a different order and this is going to open up a lot of opportunities for us to optimize things in different ways because we don't have to maintain that order now in some cases we do want that order uh we have to put constraints on top of that to do that and some systems would always store data
53:54 in sorted order uh in some manner but we'll see examples when we see you know manipulating or updating the the the database uh through transactions that if we maybe running a background garbage collector it could reorder things in any way we want and we get back things in a different order so if you care about getting back things in the right order you you define an order by clause in in in SQL but again the original version of relational model does not have
54:20 that so intersection is again finding things that are that are in both in this this case here I have to have again I have to have the same attributes there's only one uh Tuple that matches to both them A3 and 103 and that produces the output uh
54:37 below difference is finding all the tupal that appear in the first relation uh but not in the second relation right again this is just sort of set theory stuff here nothing nothing exotic right so I can do this again in SQL using the accept operator again here I have a my prod my output A1 100 101 A2 102 because those things don't exist in s but because I have A3 103 also in s that thing it's excluded as from my
55:09 output all right so this is again this is basic set the uh but it still doesn't it's not allowing us to to identify the the relations that we would or the relationship or the connections between different relations that we would want
55:23 so to do that we want to do what are called joins but before we get joins we have to do a cartisian product because that's the basis of how we're going to do joins later on so cartisian product
55:33 yes the operations covered do the colums have to be the same this question is for these operations here do the columns have to be the same yes joins we'll see in a second they don't for Union intersection and difference they have to
55:49 yes all right so the the I'm say the easiest the the a naive join would be the cartisian product you're just taking all the tupal that are one relation and all the tup in the other relation and just finding all combinations of them and producing the output right so in this case here if I do the cartisian product on RNs I get all of these for every Aid sorry where AID is is A1 and 101 I then generate all of
56:17 the sorry I generate all of the these guys here just match them together and that's these and then I go into the next tup on this side and and get all the 18 102s and then match them together that right
56:30 so you may think why is this a good idea why would you ever actually want to do this because you're generating a bunch of data that actually doesn't actually match with with with with what's in the real world um this shows up when you do experiments and experiment analysis and as in testing because you want to get all possible combinations of your inputs you would do the cartisian product for
56:48 that but more importantly from a theoretical perspective this is going to be the the basis of how we're going to do joins in the next operator because what we're going to want to do is find all the you know where the AIDS in R matches the AIDS in s's because we know they're going to be connected in some way based on how we Define them in our
57:06 schema so you can do this in SQL there is a explicit crossjoin operator or keyword right so I can say select star from R cross join with s and that gives you the cartisian product or it's not recommended in the standard but you can just put you know the comma separated list of the tables and this will produce the cartisian product for you right
57:28 but joins the important thing that we care about this is basically a getting all finding all the matches from one relation quing some value with the with the given attributes in s and so unlike in the intersection operator where the the the schemas of the two relations have to be the same joined doesn't have to be so implicitly it's going to look for the name of the column and find the corresponding matching name in in the yellow column when I do a joint so for RNs
57:57 here when I do a join on RNs with a joint operator I'll find where the values of Aid and B ID are the same and then value just sort of comes along for the ride too because it was part of the matching tupal right so you again you sort of think of this as like
58:15 uh you sort of sort of mashing the the two tupal together then checking to see where things match like r r a ID for R has to match a aid for S and the the B ID for R has to match the B ID for S and then you just you throw away the duplicate
58:32 attributes right and then that's your output joins are going to see this we have spend a whole lecture on this joins going to be where where Data Systems are going to spend most of their time in in running queries so this is the thing we're going to try to optimize the most to make them run the
58:47 fastest there's a lot of different ways to Define joints a lot of different types of joins we we'll see more in next class um and so my example here where I'm sort of implicitly joining based on the the having the values be the same or sorry the names of the attributes be the same that's called a natural join so there's a natural join keyword that's basically going to look up the names and see of columns see whether they match and then do a join against them I don't recommend doing this because again it's plicitly storing the uh implicitly figuring out what the joint should be based on um and you actually want to actually Define how you want to do your join so you can either do this with a join clause for RNs and there's a using uh keyword you say what what you're doing look your look up on or you can do the on Clause where explicit to say like Aid has to for R has to equal to aid for S and the bid for R has to equal to B ID for
59:35 S right so the bottom one is probably if you're writing by hand is probably what you're going to be doing um this has a little bit more information because you're actually specifying what columns you want to to do the join on and then natural join again is not something I
59:49 recommend again the anti SQL standard prefers want to to explicitly Define as much as possible uh so that way if the schema changes or things evolve it doesn't break your application code all right so there's a bunch of other stuff in that came along later in the 70s for uh the rational model how to rename columns uh how to assign colums to to variables removing duplicates de aggregations and sorting and division uh again these all came after Ted CS original paper and most Data Systems are going to
1:00:23 support maybe not division but everything above okay so that's the crash course what you need to know for relational algebra but we'll see how this you know as we go along I should build the the query engine of a system that's be predicated on on these
1:00:41 ideas all right so as I said before relational algebra is considered a procedural language like even though it's mathematical notation but you can kind of easily see how you can Implement a system to implement it right one of the complaints about Ted cod's paper in the 70s was they thought it was too
1:00:58 mathematical I'm not saying that I'm I'm I'm brilliant and I could easily decipher it but I was surprised when when they said that because it it's not that it's not that esoteric it's not that hard right any I think any uh you know CS undergrad people should be able to understand it but it's still defining the steps you want the data system to perform in order to compute your query
1:01:18 right so I have to say if I'm going to join RNs uh I have to Define how in what order I want that to happen so I would say all right first my choices are first join R and then s then do the select on it uh to to filter out the tupal that I want or I could do the filter on s first based on the B ID then take whatever the output of that uh select operator then do the join against
1:01:44 that and again there would be pretty dramatically different performance uh uh of these two queries based on what the database actually looks like again if if if RNs only have 10 tup then it's not that big of a deal but if RNs have billions of tup then I definitely want to filter as much as I can out from s before I join it with with r but in raal algebra there is no concept of of allow things to be reorder I'm defining exactly what I want to
1:02:12 happen so this is going to lead us to next class talking about SQL but a better solution is going to be say again the high level definition or Declaration of the answer that I want in my query and let the data system figure out what's the best way to to perform that and again now if I change the physical layout or data structures that are in my database uh I don't have to change my query plan uh or don't to change my query if it's def find a SQL I let the data system figure that out for
1:02:41 me so that that's why SQL matters and we again we'll see this more next class all right so the as I said the relational model defined by Ted cod in the 1970s didn't come with a programming language SQL was amended by IBM a few years later Ted cot eventually proposed his own query language called Alpha but nobody actually implemented that um and there was actually an early version of SQL called Square which we'll see next time
1:03:06 which required a keyboard that didn't exist because you had to write things vertically right it was a bizarre thing um but SQL basically became the defao standard that it is now it wasn't the first one there was another language called quell invented by Stonebreaker uh from Ingress which later became postgress um but there was there's a bunch of there was other variations of of Rel query languages SQL end up being the dominant one there is a SQL standard
1:03:30 but again nobody actually implements that uh exactly in every system so the idea is that instead of writing procedural code like this like doing my lookup in in in Python code I'm better off writing SQL because now I don't care about how stuff's physically stored I don't care how how the query plan is actually going to execute I let the data system handle all that for
1:03:52 me so any questions about the relational model yes when we talked about relational algebra there was no concept of a key like a primary key in that situation because when we did unions I didn't understand like what if we had two values the same key so this question is we didn't when we talk about relational algebra we didn't mention primary Keys
1:04:12 uh and that's because the you would Define that in the schema of like here's what My Relations look like the DAT syst can then enforce that the constraint that the primary key has to be unique but then when it came time to actually run queries uh you don't care like what the primary key actually is so I can do joins I can do intersections all that without worrying about what the primary key
1:04:36 is likewise I didn't have toine what the far key was right it's it's there it's it's a it's Integrity constraint all right so I want to briefly talk about uh in the last five minutes uh the leading alternative is going to be the the document Json model and then the the vector database stuff is the hot thing now uh I just want to expose you to this real quickly what what these ideas are and then we'll we can mostly ignore them throughout the rest of the
1:05:04 semester all right the docine data model is just think Json right or XML or or object Orient uh you know uh data right but the idea is that you're going to have some kind of pical collection of of data where there's going to be these name key value pairs but then within a given doc you can have a nesting of arrays nesting of other documents and so forth right
1:05:32 Json is how you would implement this today there's older systems from XML and then even earlier than that in the early 90s late 80s when object oriented programming was a big thing there was these object oriented databases that you've never heard of uh that basically try to map like C++ objects into objects in a database so instead of operating on relations you would operate on on objects so we'll see this more next class but the problem that they're trying to solve is the idea of the Rel ational object impedance mismatch meaning I'm writing code in my application based on objects uh that have this High structure but then when I have to store it in my database the DAT requires me to store it as relations and then now I need a way to map that back and forth between relations and objects which can be
1:06:12 cumbersome there's a bunch of systems out there uh that implement this the document model manga to be is probably the most famous one uh CB or cou Bas is probably the second one but again this idea goes back to the 1980s
1:06:26 so going back to my example of the of our music store I would have a relation for artists I would have a relation for album and then I have this this cross reference table cross reference relation that Maps artists to albums right so now if I want to get for a given artist all the albums that they appear on I have to do a join to go from the artist table to then the artist album table and then to the the the album table so the document
1:06:52 model people say this is stupid joins are slow you want get rid of this thing and instead what you want to do is just embed for a given artist all the albums that they appear on or the reverse of that for given album all the artists that appear on it so the idea is like if you're writing much uh python code or Java code whatever you define these classes and then when now you actually want to store it in your database uh in this case here for given an artist we're now going to embed the the list of of albums that they appear on so now for again when I want to do that lookup for a given AR artist go give me all their albums it's one query to go fetch that artist record and then it pulls on all their
1:07:31 albums so this a good idea or a bad idea again I'm it's obvious what my answer is GNA be uh why is it a bad idea yes you can direct quy onbs he says you can't query directly on albums you could you can do like you you can do nesting inside get things yes
1:07:55 prict what she said yes she said and she's correct this is you have to predict what the query is are going to want to look up on and then model that in your in your database absolutely yes and then likewise I I'm going to be end up duplicating a bunch of information if if if a artist appears on sorry if multiple artists appear on one album I got to re-record that over and over again so some cases this nesting makes sense in many cases it doesn't yes and also you want Del an
1:08:26 album you said if you got to delete an album you got to find all the artists that where the album appears on yes you can do an index an index could help find that but still it's it's implicitly in in your application what the layout
1:08:38 is so in some cases you do want to store things as as Json in your database uh but often times you do not all right so the last one to talk about is the vector databases so this is the hot thing now there's a bunch of companies that have gotten a lot of money
1:08:56 uh that are Building Systems in the space we is coming to talk with us on campus uh in a few weeks uh I like those guys they're good people um but no they fun I was I was on their podcast they're fun
1:09:11 uh so a a vector database at its core when when you say a vector database they really mean a document database that also has this extra data type called a vector an embedding and and think of that as a it's a larger array of floating Point numbers and what they're trying to provide is the ability to do
1:09:31 approximate nearest neighbor search searches based on these vectors because these vectors are going to be generated from some kind of Transformer embedding that's trying to represent what's actually in the data you're storing right the end of the day there's just a fast index to do approximate nearest neighbor search so what does that look like so again say I have my album table and then somehow I'm going to get out all the lyrics from these albums from from you know from Rap Genius or whatever right and I'm going to feed that into some kind of Transformer uh either I'm using obing eye or or or something from hugging face and then that's going to generate me a bunch of these embeddings which is just floating Point arrays of floating Point numbers
1:10:11 and that somehow they the the magic of the Transformer is that somehow implicitly the information or the semantics of the data that I fed into the Transformer is is is in those uh floating Point numbers so then I'm going to show that in my vector vector database it's going to have a vector index uh the most common one is hnsw
1:10:30 highle near or highle navigable small worlds ivv IVF flat it's another one but there's a bunch of libraries like meta Fest or Spotify noi there can be some data structure we'll cover in a few lectures to to easily do these these these near nebor searches on these uh uh on these embeddings so now my query instead of doing exact lookups like find me jiz albums I can say things like find me albums that are similar to Liquid
1:10:56 Swords and somehow assuming I have lyrics to Liquid Swords I can convert that information into uh put that in my Transformer I get out the same kind of embedding that I would get when I first loaded my database and then I do nearest neighbor search on the vector index and that it returns back the A ranked list of of matches right so the vector database is essentially this part here they can also store metadata like they also store this information I over here as Json right so I say find me all the albums that are sound like liquid stores that came out after 2012 or something
1:11:30 and I can incorporate that in my lookup but at its core a vector database is this Vector index piece here but in the last year or so pretty much all the relational databases now support Vector indexes right so it's again it's it's I argued I've told the we8 guys this directly like it's
1:11:48 not the idea of vector search near neighbor search does not mean you have to build a whole new system that throws away everything we talk about the entire semester it's just an extra thing we can add and the relational model can accommodate it so the the SQL standard does not support doesn't have a notion of this nearest neighbor searches uh postgress through PG Vector has their own API Oracle has copied that I think that's going to end up in the SQ standard in a few years uh and the the vector guys will have to figure out how to how to overcome
1:12:18 that okay this is like crash course in vector vector databases in in in two minutes but the we8 guys come talk about it more uh later in the semester all right soever it is databases are ubiquitous databases are important databases are the second level in my life um the relational algebra is going to be the foundation for how we're going to build our systems to support them uh and then we're going to see this over and over again we talk about crit optimization career execution uh and certainly we'll see this next class when we talk about SQL okay so next class will be not done yet Q&A next class we're going to do modern SQL so by modern SQL I mean like I'm not going to te you what a select star is it's 2024 you guys are see me students I'm assuming most of you have seen seable 4 in some form the basic form of it so I'll try to teach you the more advanced things and where things break in the SQL standard okay so least make sure you understand basic SQL for showing up next class
1:13:08 okay all right we have eight minutes left any questions about databases yes so you talked about a little bit earlier we talked about the blurry line between relational and do a little bit yes and it feels like relational database support SE now right
1:13:33 so you explain little that me so his question is he's used dyb dynb is one of the uh from Amazon one of the first no SQL databases it originally started off as I think a as a key value store then they added for Json and then more recently they've added basically looks like tables and I don't think it's directly SQL I think it's the it's part of ql it's it's it's no not graph there part of ql is Amazon's dialect of SQL
1:14:00 and it looks like SQL so why is this why is this uh convergence between the the no seal guys and the and the um and in the relational World well because all the things we talked about today why having a relational model and and making sure you can't shoot yourself in the foot in your database is a good idea they they've come realize oh customers actually want these things and they've added added it added it on top of it
1:14:24 right so that's why I think there's a convergence because like in the same way that no one's going to vent a new mathematics where like CU cuz 1 plus 1 equals 2 is just true I think like the relational model is just the true way the correct way to implement to represent data and you can add accoutrements like the vector indexes on top of that or the various things dealing with Json but everyone's basically coming back around like the relational model is the right way to go
1:14:47 katab is a genius yes so I have a question about the uh V database yes you know there a very famous St Rock by yes I wonder like with this kind of real time Vector search database what kind of realistic um you know applications you can imagine like for Vector index for dates
1:15:14 uh dat all right so his first question you start off with uh open ey made a major acquisition the summer they bought rocket rocket was a database startup a relational database startup uh based on the guys that that created frb out of Facebook an opening eye uh he paid a lot of money for it um so the question is
1:15:33 what first of all what is open ey going to do with rocket I can't tell you uh but what are some uses for a vector database so going back to my example here um right this idea of this semantic search like find me the albums that are similar to Liquid Swords I'm not defining what it means to be similar right or find me the albums where they talk about slinging rocks well you could have your Transformer know that slinging rocks means dealing drugs and even though you ask for something in rocks it knows somehow magically knows because the training data based on can how to match that to to different things so
1:16:11 it's a way to do better searching based on the semantics rather than find exact matches that's that's where these things are being used for yes are we not able to do like these kind of semantic or like fuzzy search through Rel database the question is are we not able to do the semantic searches Rel no I said absolutely yes you can assuming you can store this an embedding and then have a vector a vector index do the fast approximate nearest neighbor search you could write SQL queries against this postest does this PG Vector all all relational databases have now some form of a vector index you can do this prior to this though the way you would do lookups would be like fuzzy matching
1:16:49 like find me all the albums that you know have the word swords in it right you couldn't do this this the semantic meaning is that's that's part that's new in the back yes his question is if every record needs to go through a Transformer wouldn't that be slow
1:17:12 yes I mean milliseconds it takes milliseconds yeah it's not it's not seconds yeah it's Rel again be very clear here like you can put the you can put this in a relational database right the question would be is the is running through the Transformer to get back the the embedding they didn't do the lookup is that going to be slower than doing an inverted index which we'll cover later on
1:17:40 maybe depends on what this is depends on what's the memory there's so many different factors involved it's hard to say and that's and then that that assumes that you're you're going to get the data you'd want using a fuzzy fuzzy search anyway again for some things like it's not going to work CU there's no no understanding of what actually is in the in the in the data what it means that's what the Transformer does for
1:18:03 you yes when we are taking interview sometimes the interviewer ask us to uh design a system and they want us to choose which kind of database like C no sometimes they are more satisfied with you when you choosing Nole but as you said that right
1:18:19 so his question is sometimes in the job interview the interviewer ask you pick a database for whatever like prototype system you're building the answer is postgress always pick postgress right I'm dead serious right and you can't say oh because Andy said so but like postgress is a rock solid database system that has a lot of the features you would see in a you know sort of enterprise system um and actually just not just for interviews for anybody doing a startup anything your first choice would be postgress right because because you want to be spending your time like building your application not worrying about what datab system you want to build so you just say postgress because I want to spend my time building the application because that's what matters like no one's going to know or care that your application is running on postgress versus mongod DB because they don't interact with the data at that level
1:19:04 postest is almost always the right choice now you may get to the point where postest can't scale handle your data and at which point you pay not me but paid somebody else a lot of money to help figure out what dat is you know how to make post
1:19:15 scale in the back yes can you speak up sorry yeah so as as a career wise like what do you think like good compies can work you know it's a good place to work and you we should run his question is uh what are some good database companies to work at what are some bad database companies to work
1:19:36 at all right so good database companies this is the great thing about databases there's a lot of money and there's a lot of lot of lot of people building database systems so like say you you're in operating systems where can you go to build an oper system IBM Red Hat maybe right the Linux guys are all doing their various things but like there isn't there there aren't a lot of competing operating systems there's a ton of databases and if you want to go to a big company the Microsoft the Amazon the Googles even the Facebooks right all of them are building database systems and then there's a bunch of startups that are all in the space as well now some of them have questionable uh Financial
1:20:09 footings um but I say this that because my database start up failed this summer but um the so there's a lot of choices in the database and there's a lot of money in it right even now even though you know the relational model relation dees are 50 years old there's still trying people trying to build new systems all time now in terms of bad companies uh I mean I'll to say off the bat Enterprise DB
1:20:34 uh them so avoid Enterprise DB uh in terms of other ones I mean for startups obviously you want to talk to people and see what their the finances look like uh you can maybe get a sense of how much they're chasing bads like if they're a uh if if all a sudden they they start off being you know some kind of database and now they're a vector database because it's the hot thing or the AI database looks a little dicey
1:20:59 right another interesting Avenue is also I mentioned like Google Google and Amazon they'll sell you you know they sell datab Services then there's companies like uh I can't say well I'll bleep it out like they're building a database system and like the great thing about it is they're building it in house they they don't have to worry about getting customers because they're they're their own customer but they're actually building a whole system from scrap from and doing some interesting things so there's so many different options to do this in databases and that's why I think this class is super important because you're you're
1:21:26 encounter this throughout your life and the companies don't want to hire a bunch of random JavaScript programmers because those people are going to break your database system you don't want them to touch the internals they want CMU students who know how to you know handle these things uh and are dying to hire you guys uh yes quick do you think this class is a good preparation for database career his question is is this class good preparation for databased career I am biased because it's my class um I've been told by certain davus companies this class is the uh onboarding process for davus companies
1:21:55 uh I've also been told that the the interviews for some D companies are basically entire lectures from this class uh so take that to mean what it what it means right um there's always money in databases how about that okay last question what's the best way to incorporate blockchain into
1:22:18 my all right do do you have a real question uh what happened to the DJ in this course uh all right um yeah so unfortunately we cannot have a DJ this year because of legal problems dealing with uh War Hall so I apologize uh they
1:22:33 I there is the moral T I have tenure but there is the moral T Clause that seeu where I can still get fired uh so I'm trying to lay low this year so I apologize okay all right all right guys uh that's it see you on tues or Wednesday I need something refreshing when I get finished manifesting too cold a whole B like Smith and Wesson one court and my th's hip hop related write a rhyme in my pants intoxicated lyrics are quicker with a simple Mo licker since on a city slicker play waves are picker rhes I create rotate at a r too quick to duplicate feel a breze as a skate mik at fah when I hold it real tight then I'm in flight then we ignite
1:23:16 starts to boil you I heat up the party for you let a girl R me and my mic down with oil Rec still turn with third degree burn for one man I heat up your brain give it a suntan to just cool let the temperature rise to cool it off with s eyes
1:23:34 [Music]