#01 - Relational Model & Algebra (CMU Intro to Database Systems)

We'll be right back. Before we get started, I have to read this out: I do not have child protection clearance for Act 153. This is state law in Pennsylvania. So, if anybody here is under the age of 18, you cannot be in this classroom.

No, it's not a joke. Seriously. I don't think they would have notified me, but just make sure that anyone here who is not 18 or older understands that it's a Pennsylvania state law regarding criminal history checks. I don't have the criminal background history to pass this, so, again, if you're anyone coming in and you're under 18, please leave the room. With that aside, I'm going to give a quick shout-out to the people who have helped us get to where we are today.

So this is Eze in Brooklyn, J.L. in Seattle, and unfortunately, DJ Drop Tables passed away this summer, so rest in peace to him. DJ Mushu is in lockdown, which is a whole other issue, so we send our respect to him. Okay, alright, with that out of the way, let's get into databases. I sort of mentioned this in Lecture Zero, which I recorded and re-recorded today. I apologize for messing up the microphone, but it should be better now.

So, as we go through the semester, you will see that I get very, very excited about databases. This is for a very important reason. I only care about two things in my life: the first is my wife and my biological daughter, and the second is databases. I don't care about anything else.

I don't talk to my family. They're all Trump supporters and anti-vaccine. I don’t care about them. I don't have any hobbies; it's just databases. I live what you would call a database-centric lifestyle.

And hopefully, I hope to impart to you all what that means and what it entails, so you can continue down the path beyond this course. Now, earlier last week, someone posted this on the CMU Reddit, right? They wanted to know whether taking 440 or 445 is harder because they want to spend their time doing other things in their life, right? So, I chime in and say that whoever this person is should not be concerned about that because I don't care whether they think it's hard or easy. You will see throughout the semester that if you adopt the viewpoint that everything is pretty much a database problem and that all your time should be spent working on databases, then you'll be happier in your life.

So again, if someone is in this class to post this, you don't belong here. Just a quick reminder about logistics: everything is on the course webpage. All announcements and discussions regarding projects, homework, logistics, and other matters have been communicated through Piazza. All homework and projects will be submitted through Gradescope and will be auto-graded. Your mid-semester grades, final grades for all your projects, homework, and final exams will be posted on Canvas.

If you're on the waitlist, I think our maximum capacity is 140 before the fire marshal shows up. As of an hour or so ago, we have six open seats, and the administrators will fill those spots with people from the waitlist. So, if you're still on the waitlist, you may have a chance to get in, but I can't guarantee it. Okay? If you're not at CMU, we'll make everything available for the projects through this Gradescope. Use this code.

Make sure you refer to yourself as Carnegie Mellon University. Everyone in this room right now, please refrain from doing this because it will result in not receiving a grade. We kindly ask everyone else who is not at CMU and watching the videos not to post your solutions on GitHub. Please avoid the mistake of submitting a pull request with your code, as we will create a "Wall of Shame" for that. Additionally, please do not email me or the TAs if you are not a senior student.

Everybody else here in the class, please post on Piazza and we will respond. Any questions or comments about any of these? Again, if you're coming in and you are not 18 or older, you have to leave the room because of Act 153. Okay? All right, so today’s agenda: we’re going to talk about a quick background on what database systems are. That will set us up for what the course will be about.

We'll spend most of our time talking about the relational model and relational algebra. This will be the foundation for how most database systems that you will care about function. Not all, but most systems will be based on this. We'll also discuss some alternative data models that are available, such as MongoDB, Docker, JSON, and vector databases. However, these will be somewhat ancillary to what we cover in this course.

The core ideas behind the relational model of how we are going to build these database-eminent systems will be applicable to these other alternative data models. It's just that I care less about them, right? Because I care about SQL; I care about the relational data model. As I mentioned on Piazza yesterday, we will have, since this comes up every year, people always asking high-level questions about databases throughout the semester, and I want to try to cover as much as I can at the very beginning. So, if you have any questions you want to ask me at the end, we can address those, okay?

And again, as I said in Lecture Zero, I get very excited about databases. I talk very fast. Please tell me to stop and slow down. If you have any questions, please interrupt me and ask me to repeat myself. I will refuse to answer any questions about the lecture at the end of class.

I don't line up and say, "What did you say in lecture? Slide five said this. What do you mean?" Interrupt me as we go along, because if you have a question, someone else probably has the same question, and we want to cover these things, okay? All right, databases are the second most important thing in my life.

Can anybody give me an example of a database? Yes? ClickHouse. He said ClickHouse. Anybody else?

"A dictionary. You said a dictionary? Yeah. Yeah, that's ClickHouse. Anyone else?"

A dictionary? You said a dictionary? Yeah, that's pretty good. What else? Nobody can get into my database.

Contact the manager on your phone. Contact the manager on your phone—good, excellent. One more? IMDb. Say what?

IMDb. Good, excellent. Alright, so he mentioned ClickHouse, he mentioned dictionary, he mentioned contact manager, and he mentioned IMDb. So, ClickHouse is a database management system. The other examples are all databases.

And so what's tricky in the common semantics of how people describe databases is that they usually refer to database systems, which we will focus on in this class. However, I want to first discuss what a database is and then how we're going to build a database management system to manage it. Okay? So a database is an organized collection of data—no surprise there—that are related in some manner and are meant to model some aspect of the real world. For example, think of a dictionary. What is a dictionary? It is a collection of words along with their definitions, and possibly information like the part of speech or other relevant details.

Right? The vocabulary. You mentioned a contact manager; that's modeling someone keeping track of elements of pencil and paper. Here are 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 and aspects of that real-world concept in your database. And again, I'm highly biased because all I care about is databases, but the database is going to be the core concept of most computer applications and most of computer science. What is a computer doing?

Some input comes in, you do something with the data, and you produce some output. That's a database. The middle part is almost always a database. What is a file system? A file system is a database.

If you use a website, what are you doing? You're interacting with a form that communicates with a database. What is an LLM? It's a database, more or less. So this would be the most important thing in computer science.

Again, I'm biased, but you're going to encounter databases throughout your life. What this class will teach you is to understand what a database management system is trying to do for you. Why are things going slow? Why is my query coming back with garbage? If you understand how the components are implemented and what they're doing, you're in a better position to use a database system to manage a database. So, no matter where you go—whether you become a database systems internal developer like all the companies that are coming in a few weeks to talk to us, or you pursue a different path—at the end of the day, you're going to interact with databases. That's what life is really all about. Everyone has a smartphone, and all those applications are running on SQLite.

SQLite is a database management system. It's the most widely deployed one. So, we'll understand how SQLite is actually implemented. In Homework One, you'll use SQLite. Let's discuss a toy example.

And they can use that to explain the various parts of the original model and database management systems as we go along. So, assume we're trying to build a Spotify clone, right? It's some kind of digital music store, and we want to keep track of the artists who are putting out music, as well as the albums that those artists release. We want to know which artists appear on each album. A really simple implementation of the database could consist of a bunch of files on disk.

In my example here, I'm showing them as CSVs, or comma-separated values, but it could be JSON; the kids love YAML, so you could do YAML. It doesn't matter, right? But we're going to have a separate file for each entity. So we'll have a file for the artist, which will have a name, the year that they came out, and maybe the country that they're located in. Then we'll have albums with the name of the album, the artist that appears on the album, and the year the album was released. Now, this is a database, and I don't recommend doing it this way, but you could do it this way—with a bunch of files on disk. So now, anytime you want to update or insert a new record, we can just open the file, append to the end of it, or if we need to answer a query, we just scan through it until we find the answer that we want. For example, if we want to answer the query, "What year did the Jizzo go solo?" I could write some Python code that opens the file, reads every line, and parses it as CSV to get back an array or list of values. I know that I'm trying to look up the name "Jizzo," which is the first field in my file, so I just jump to the first element of the array, check to see whether that value equals "Jizzo." If it does, then I print it out. Right?

This is the database system, more or less. Well, this is interacting with the database. I'm basically embedding the logical database system inside my application to do this. Is this a good idea or a bad idea? I guess it says "straw man" at the top, so you know it's a bad idea.

So, why is it a bad idea? Yes? We need to look over every entry. He says we need to look over every entry. Is that correct? My example here is that my file has three lines.

Okay, who cares? That will sit in L1 cache. That'll be super fast. But always, when you think about computer science, especially in databases, consider what happens if you scale up to really large numbers. So, what if my file had a billion records?

Do I want to be scanning through and parsing every single line just to find the element I'm looking for in one entry? No. What are some other problems? Yes? 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 field? Now I've got to change a bunch of my code as well as update the file. That sucks. Maybe one more. In the back, yes?

If you encounter a line that is reordered and then reordered again? Yes. So he says, what if you come across a line that is reordered in a different way? Maybe they swapped something out, and these files on disk open up in a text editor; they flip the order of these items, and now my Python code is going to struggle with it. Or even, what if I put, instead of the year 1990, a phone number in?

What happens then? There are several problems with this approach, but the Data Better system is designed to prevent you from encountering these issues by managing everything for you. However, there are still some other challenges to consider. For instance, in my file, if an artist releases multiple albums, I'm simply repeating their name over and over again. Wu-Tang Clan, Wu-Tang Clan, Wu-Tang Clan.

But how do I make sure that someone doesn't, like, drop an "n" in the, you know, the name of the Wu-Tang Clan, and now it's Wu-Tang Kla, right? Well, I know that they should be the same thing, but the data says that they're different. We brought this up before: what if someone comes along and overwrites the album name with a weird string, puts an email address in, or puts in a random number that shouldn't be there? And then we didn't talk about this, but in my toy example, I assumed that there was one artist per album. But if it's a mixtape, there are a lot of artists on that, and in my simple example, I couldn't handle that.

Here’s the revised text with correct capitalization and spelling: "Then what happens if I delete an artist by accident or by choice from the artist file? Now I have a bunch of albums that mention an artist that doesn't exist in my table or my file. So, I basically have a dangling pointer now. We’ve talked about, on the implementation side, how to find a particular record. Well, just iterating over a single file and parsing it one by one is terrible."

That's slow. What if you have another application that wants to use the same database? Well, now I've got to basically copy and paste the code that I wrote to parse that file and get records out and put it into my other application. But what if I wrote the first version of the application in Python, and then I rewrote it in Rust? Now I've got to translate all the Python code to Rust code.

That sucks. But then what else? What if the file—sorry—what if the application is running on a different machine or a bunch of cell phones? Now I've got to make sure that all the application implementations can access that file somehow, like a distributed file system, which is the database, by the way. And then what happens if we have two threads trying to write to the same file at the same time?

And then what happens if we have two threads trying to write to the same file at the same time? Well, we can do something really stupid and just let the operating system lock things for us. It would lock the file and then only allow one thread to write to it at a time. But a recurring theme you're going to see throughout the semester is that, in the world of databases, the operating system is our frenemy. We never want to let it do anything for us. So, allowing the operating system to lock files for us is a bad idea because we're database professionals, and we can always do it better than they can. Only allowing one thread to write to the file at a time is actually what SQLite does, but SQLite is meant to run on cell phones.

If you're running a machine with a thousand cores, you don't want to do that. The OS implementation is always going more inefficient anyway. Lastly, what happens if we're modifying the file and we're going to write a new record? We write half of it, and then it crashes. The machine crashes, someone trips over the power cord, lightning strikes the transformer, or whatever. When we come back online, what should be in our file?

Well, if we just write to the file, we'll only see whatever we wrote before 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 machines to access the file or the database? We want to ensure that if any one of those machines goes down, we can keep running and still serve queries and requests. Well, now I've got to basically implement a bunch of load balancing mechanisms to handle accessing the file.

That sucks. So this is just a quick overview of the problems that we're going to have to solve throughout the entire semester to ensure that people don't have to do things like relying on the operating system or managing a bunch of stuff in application code. This is what a database management system is going to do for you. It will be the software that allows applications to store, analyze, and query data in a database. A general-purpose database system is one that can support any arbitrary schema, within reason, of course. It can allow any arbitrary queries, meaning it's not hard-coded just to perform that one lookup on the given dataset. You can change the query to look up any artist or any field or perform any kind of transformation. It will do this according to what we call a data model, which is a high-level representation of what is in a database. Right?

And again, just to emphasize this point further, database systems are some of the most widely deployed, tested, and vetted pieces of software in the world. They may rival operating systems, which is the only other category I can think of, as well as some embedded systems. There are multi-billion dollar corporations that rely on database systems, which are tested and sold by major enterprises. A lot of money is involved in both building and selling databases, and there is significant financial investment riding on a database system operating correctly.

And so at no point, let me reiterate, if you go off into the real world and you're going to start a startup or whatever, should you say to yourself, "Oh, I'm just going to build my own database system in my application." That's a bad idea. You're going to encounter problems; you'll need to rely on the existing tools that are out there. Again, this class is going to teach you how to do it. All right, so a data model is going to be a high-level abstraction that represents data in a database.

Again, according to some scheme. We'll see in a second. Within most database systems, only one data model is typically supported, such as a relational database or a document database. Recently, the lines have started to blur because relational databases can now store documents, including JSON, in a field. Additionally, document databases support SQL and relational-like operations on top of JSON. In some cases, it is clear that there is a distinction between the data models; however, in the more widely used systems, the lines become less distinct.

And so, given a data model, your database will be defined according to a schema that specifies the tables or collections of data you have, along with their attributes, names, and data types. Again, we'll see this throughout the entire semester, but it serves as a way to specify the shape and structure of the things you want to store in your database. Without a schema, it's just a bunch of random bits that don't mean anything. Schemas allow you to provide a structure to the data so that you can write queries against it. Another way to think about this is saving a bunch of log files from my application server.

It's a bunch of text lines with timestamps and so forth. If I don't have any structure on top of that, then there's no way to find the data I'm looking for. But if I say a log file entry is going to have a timestamp, followed by maybe an event code, followed by a string 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 bits, the data is useless and meaningless. Yes? How does this differentiate the data model? I thought the data model would also be... The data model is... We'll see in a second. The data model is the abstraction for how you define collections of data and then their relationships with other collections.

The schema indicates that, within that data model, I have these collections that possess specific attributes with designated types. Think of it like a class versus an object in the Java world. The class serves as the definition of the data model, while the instantiation would be, well, that's not the best example. It resembles how, in a programming language like Java, you define how to represent data and then create instances of it in classes. Let's delve deeper.

I think it's a bad example too. However, I believe it makes sense when you start seeing the differentiations between them. Okay? Any other questions? Alright.

So I'm going to be highly, highly biased throughout the entire semester. I love the relational data model. I think it's how every database system should be implemented because the relational model can be contorted, at least 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 going to discuss this semester, as well as most database systems in the real world that you've heard of, are very likely to be relational databases. However, it's not to say that it's the only one out there. There are these key-value stores that exist, such as RocksDB, LevelDB, and Redis, which operate on a simple premise: you have a key and a value, and that's it.

And there's no meaning to the actual value except for what the application assigns to it. This is typically used for simple applications or caching, such as a cookie ID linked to some payload. Then you have a whole category that falls under the moniker NoSQL, which is ironic now because it has evolved. At the beginning, when NoSQL emerged, there was a sentiment that SQL was inadequate. They asserted, "Oh, guys, SQL sucks; we are not using any SQL." Now, however, NoSQL truly means "not only SQL," as they've recognized the value of relational databases. The document stores and JSON databases, such as MongoDB, are probably the ones you’ve heard about the most; they fall under the category of document databases.

A wide column or column family is a subset of JSON databases. It's similar to how Google Bigtable operates, while Cassandra represents another example. Additionally, there are array databases, which include vectors, matrices, and tensors. Tensors are probably the last thing you would want to store in a relational database, as they are essentially multidimensional arrays. It can be quite unconventional to manage them in a relational model. Interestingly, the SQL standard added support for multidimensional arrays just last year.

And then there are these hodgepodge of concepts at the end: hierarchical network semantic entity relationship. I'll discuss the network aspect a little bit from Codisil. However, these ideas are reminiscent of the 1970s and 1980s, a time when people were indulging in cocaine.

They were experimenting, but basically the world has come 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, the relational model is stupid, SQL is stupid. We're going to have a new data model." Then everyone gets all excited about that on Hacker News.

And then they eventually come around and say, "Oh, yeah, the relational model is the right idea." So right now we're in a phase where all of these experts have acknowledged that SQL is actually a good idea. The next step will be for vector databases to recognize that SQL is a good idea as well. But we'll get there. All right, so again, this course is going to focus on relational databases, but that doesn't mean that the concepts we discuss can't be applied to other data models.

It's just that most of the systems you encounter are going to be relational. So, why does the relational model matter, and why am I so keen on it? Well, if you go back to the 60s and early 70s, there wasn't a plethora of database systems like we have now. There were only a small number of them, and it was very difficult to build database applications. I think of it as the mainframe days.

In the early days, one of the first data systems that was built was a thing called IDS, or Integrated Data Store. That system was actually developed by GE in 1965 or 1966. IMS was a hierarchical database built by IBM to manage the Apollo Moon mission, helping to keep track of all the parts necessary to build the rocket. As part of this IDS work, there was a component called CODACIL, which emerged from the COBOL world. Essentially, it aimed to define the API that was also derived from COBOL.

I was basically trying to define what the API is and how you would interact with the database. Back in the day, in the 60s and 70s, computers were very, very expensive, while humans were relatively cheap. The labor of humans was relatively inexpensive compared to computers. Therefore, it wasn't that big of a deal for people to spend a lot of time rewriting their code, as he mentioned, every time they changed their database if they used these other data models. This was due to the tight coupling at the logical level between how you defined your database and how the data system physically represented it.

So now, in your application code, you had to be aware of how the data was laid out in bits on disk and how things were connected with pointers. You essentially had to traverse those data structures manually in your code. This meant that any time there was a change in your database schema, you had to go back and rewrite all your application code to accommodate it. For example, in IMS, at least in the early days, you would define a table and then specify how you wanted to sort it, either as a hash table or a B-tree. If you made a mistake and decided that you wanted to store it as a hash table, but later realized you needed to perform range scans—which you cannot do on a hash table—you would have to switch it to a B-tree.

Well, I've got to dump the data out, then load it back in as a B-tree, and then rewrite all my application code because now the API to that table has changed. It went from a hash table to a B-tree. There was this guy at IBM who basically saw all these programmers doing the same thing over and over, making all 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? As the world evolves, or as the data you're capturing evolves, you want to evolve your database. So there's this guy named Ted Cobb, who was originally a mathematician. He did his PhD in mathematics.

He joins IBM Research in New York. As I mentioned, he observed all these programmers repeating the same tasks over and over again, constantly rewriting their applications every single time the layout or schema changed. He obviously thought there had to be a better way to do this. Therefore, he devised the relational model in 1969 as a sort of abstraction for a database based on sets—sorry, based on relations, which I’ll explain in a moment. This model proposed a logical connection between data through values rather than through physical connections like pointers, offsets, and similar structures on disk, as was required in other data models. The first paper that defined the relational model was published in 1969.

I think this was an internal tech report at IBM. But the one that's really, really famous that everyone refers to is this one here that came out in the CACM in 1970. So if you ask, "What's the first paper on the relational model?" people typically point to this other one here. When this came out, all the academics thought this was the greatest thing ever; this is

But IBM dismissed it or ignored it, right? Because they were making so much money on IMS, which is the hierarchical database system. Then, one of their own employees came along and said, "Hey, the thing you're making money on is actually flawed. You don't want to do it this way; you want to do it this other way for this system that hasn't actually been implemented. But here's a better way to represent databases."

Again, he was a mathematician. He wasn't building a system at the time. In fact, in this first paper, it's all mathematics. There is no SQL at this time, and he didn't define a programming language.

It's all about relational algebra and how you manipulate databases. From IBM's perspective, they thought, "Well, we can't do anything with this; it's just a paper." However, eventually, IBM did take the paper and acted on it, but not in New York—it was actually in San Jose. They assembled a team, which we will cover throughout the semester, and built one of the first relational databases as a prototype based on Ted Codd's paper.

So, I mentioned Codacil. Codacil is a hierarchical database that was spearheaded by the person who was building IDS or IAM at GE. There was a sort of back and forth between the relational database proponents, primarily from academia, who believed that relational databases were the right approach, and the Codacil supporters, including many COBOL developers, who argued that Codacil was the superior option. So, actually, who here has ever heard of Codacil?

Codasel. No one, right? Because it's dead, right? So, Codasel was based on these sets. You would define these collections as tables, and you would establish the relationships between them through these sets.

You would basically iterate over every element in each set and follow pointers to find the data you are looking for. This refers to the famous workshop in 1974 in Michigan, where they gathered all the people from the CODASYL camp and all the people from the relational database camp, placing them in a single room to debate their ideas. This was a very, very famous meeting. Obviously, Ted Codd was there, and there have been four Turing Award winners in databases, all of whom were present. Throughout the semester, we will cover many of these influential individuals. Bachman was the CODASYL representative; he is deceased.

Jim Gray invented two-phase locking; we'll have a whole lecture on that. He's deceased. Then, Stonebreaker invented Ingres, PostgreSQL, and a bunch of other stuff that you may have heard of before. He's still alive, and he turns 81 this year. He was my PhD advisor.

He's brilliant. But basically, all the Codiso guys are saying, "Hey, this relational model stuff, you can't actually build a real system using this. People aren't going to understand what it means to have relations and tables." Furthermore, if you're going to be programming in a high-level language, like SQL, the people who were working with SQL were at this conference too. But at the time, SQL was very new.

You're never going to be able to take SQL and compile it into a program that can run efficiently. So they all complained. The Codicil guy said that a relational database is a bad idea, but then the relational guy argued that the Codicil approach, with its sets and the need to walk through records, deals with the physical data structure, which is also a bad idea. It makes the application brittle; when one part of the database fails, it causes all the other components to break because they rely on the physical integrity of the data. Right? And as I said, nobody here has ever heard of Codicil.

The relational camp won. But again, as I was saying, every 10 years, people forget all the things we've learned before. Now the graph database advocates are basically making the same claims that the CODASYL people did in the 1970s. All right, so what is the relational model? It's a data model that defines an abstract representation for a database based on relations, which helps avoid the cost of having to maintain the implicit knowledge of what the data looks like physically in your application code.

There are three key ideas in the relational model. First, we store our database as simple data structures, namely relations or tables, and we do not expose this information to the application code. This provides an abstraction where we interact solely with the tables. The physical storage, or how the actual database system writes down the bits of our tables, is left up to the implementation. For instance, imagine I have a database that uses a database system capable of storing data on disk, but I might also want to store data in an in-memory database.

Well, if I define things through relations and interact with them through SQL, in theory, I could take my database out of the disk database and put it into the in-memory database. If some new storage device comes along, I can simply transfer it there as well. This means I wouldn't have to change any of my application code, even though the physical layout of the bits has changed. Now, I'd say, in theory, this should work.

As we see in the next class, there is an SQL standard. However, nobody follows it exactly. The only sort of de facto SQL standard we have now would be Postgres, because everyone can take the Postgres parser and reuse it. But we'll see many cases where just because I have two relational databases, it doesn't mean they're always going to be compatible. So again, I say that in theory, you should be able to do this, but not always. Lastly, instead of writing procedural code, like low-level for loops that iterate one record at a time—as I showed in my toy example before—we're going to write queries in some kind of high-level language. The spoiler is going to be SQL, but we have to cover relational optimization first before we get there.

And then that way, we just say, "Here's the answer that I want." It's up to the database system to figure out the best way to implement it and execute it. In my previous example, I mentioned parsing a file to find one record. I asked, "What if I have a billion records?" That would indeed be slow. However, if I wrote it as a SQL query and found that things were slow with a billion records, I could go back and add an index to quickly jump to the exact record I need.

Think of it like a glossary in a textbook. I can jump to the exact record that I want, similar to how one can look up a keyword and go directly to the corresponding page. Moreover, I don't have to rewrite my application code because I have an index. I've separated the implementation of the data and the query plan. As we progress throughout the semester, we will see that back in the 1970s, people made similar arguments when the C programming language was introduced. Many believed that there would never be a compiler capable of generating assembly code for C code as effectively as a human could write it.

Of course, now we know that's crazy, right? Compilers are very, very efficient. The same thing was said about SQL back in the day by the codicil guys, who claimed that no computer program would be able to generate a query plan for an SQL query as efficient as what a human could write themselves. And of course, again, nobody writes SQL by hand anymore. Or, at least, I'm sorry, nobody writes the query plans by hand.

Let the data system do it for you. All right, so there are going to be sort of three components of the relational model. There's going to be the structure of the database. Again, that's going to be the definition of the tables we have. You can use the terms "tables" and "relations" interchangeably, but to be pedantic, you would say "relations," not "tables." You define what's going to be in your relations and then their contents, and you define this independent of their physical representation. We will cover that a bit further in the next slide.

And then you can also define what we'll call integrity constraints. These are definitions of what the data is allowed to look like in accordance with whatever you're trying to model in the real world. For example, if you store someone's age in a database, we know no one can be negative; there's nobody who is negative 10 years old. You can put a constraint in your table to say that this value of age can never be less than zero. The last component is the manipulation mechanism, which is basically the API (Application Programming Interface) that is exposed to us to allow us to access and modify the contents of our database. This is what relational algebra will cover, which we will see in a moment.

But I'm going to cover the independence aspect a little more because, while it seems obvious now, in the 1970s it was considered groundbreaking. The idea of data independence is that we don't want to have to expose the physical layout of data on whatever storage device we're using to the application. This allows applications to program against the data using a high level of abstraction. At the lowest level, there is database storage. I’m not defining what that is because it could be in memory, it could be an SSD, or it could be an object store like S3. For our purposes here, it doesn't matter. You would then define a physical schema that represents how to store the database within that storage device.

So this would be defining the pages, the layouts of the pages, like how the bits are actually laid out on a single page, how the files are organized. Is your database one file, multiple files, or multiple directories? What do your extents look like? Are you packing multiple pages in a single extent, or is it a single extent per table? All of that is handled at the physical schema level. And then above that, you have the logical schema, which is how the application defines what's in the database. I have these tables, I have these columns, and I have these constraints on them.

Typically, you would do this through SQL, such as a CREATE TABLE command. Then, I have a further abstraction on top of that called an external schema. This is where I can define virtual tables on top of my existing tables. These are called views.

Again, we'll cover this throughout the semester. The idea here is that, say I have some table of student records, and I want to expose two different applications to portions of what's in that table. For example, accounting needs to know your social security number, but they don't need to know your grades. It's all in a single table, so I can create a view that specifies which columns each application can access. This way, one application can see the table with certain columns, while another application can see the table with different columns. Even though physically it's the same table, it is just exposed to you in a different way. And at the very top, this is the application code.

This is the Python code, JavaScript, or whatever. It doesn't matter. That's going to interact with our database. So, physical independence would be this part here, where I could define my tables and their contents, but I don't care about how they're actually being physically stored. I also have a further level of logical independence, where I can say I have these logical tables, but then I can sort of recompose them in different ways for different applications or different users. They don’t need to know how things are actually being stored at the logical level right below it.

So, this physical data independence was a big deal because the code of sale couldn't achieve 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. The relational model says there is no notion of pointers, right? Even though we're going to use pointers to implement our system, we don't expose that to the application code. Again, it's one of those things that seems obvious now when you hear it, but back in the day, this was groundbreaking.

Alright, so let's delve a bit deeper into what relations look like. As I mentioned, I'm going to use the term "relation" interchangeably with "table," but to be precise according to the relational model, we'll refer to them as relations. A relation is an unordered set of data that contains a relationship of attributes representing some entity in the world. For instance, in the artist table, one record or one entity would be an artist that exists, like the Wu-Tang Clan. In this context, we would have all the attributes that represent the information or the characteristics of that entity compiled within a record. We will refer to a record as a "tuple." Again, think of it this way: while I want to use the term "row," because "row" applies to a row store, we will use the term "tuple" for clarity. Later on, we will explore column stores as well.

We'll see column stores later on. But a tuple is going to represent some entity, or an instance of an entity within my relation. The original relational model defined that all the attributes you would have in your relation had to be atomic or scalar. You couldn't have lists, and you couldn't have nested documents like JSON. That restriction has since been relaxed in the SQL standard, and most data systems now support these features.

But back in the '70s, you couldn't do this. We'll also have a special value of null if it's allowed because we can define that things can't be null in our relations. However, this is just a way to indicate that the value of something is unknown for a given attribute. So, to be pedantically correct, you would say "an area relation," meaning a relation with n attributes that is more or less equivalent to a table with n columns. Again, similar to when you say, "Oh, I'm using… What database are you using?" "I'm using MySQL or PostgreSQL."

People know what you mean. So if you say, "Oh, I'm using what data you're using; I'm using MySQL or Postgres," people understand you. If you mention a table with specific columns, people know what you mean. A core concept of a relational model is the idea of having a primary key. A primary key is a set of attributes that uniquely represents one entity within our relation. For simplicity, we could say that no artist can have the same name, and we could designate that as our primary key.

Of course, we know that's not correct in the real world, but for purposes here, we can say, oh yeah, there's the primary key, which is a name for an artist. Given a specific name, like a string, I can jump to one tuple that has that information. So, you don't always have to define a primary key; most relational databases will let you define tables without it. What we'll see later on is that, underneath the covers, if you don't define a primary key, some systems will actually create one for you. Even though you may define a primary key, some systems may ignore that and treat it as still a unique constraint. The value of the primary key is still unique, but underneath the covers, it maintains its own primary key. SQLite does this.

SQLite has its own incrementing value as the primary key, and it treats whatever you define as the primary key as a unique attribute. As I mentioned before, we could use the name as the primary key, but that's not advisable because multiple artists could have the same name. To address this issue, we can rely on a synthetic ID, such as a number, that can represent a given attribute or tuple. These IDs could be incremented monotonically, for example, 101, 102, 103.

The Segal standard allows you to find what are called identity columns. Again, think of these as synthetic values that don't really map to things in the real world, but they enable us in our application code to uniquely define where that data is located. The Segal standard refers to it as "identity," while PostgreSQL and Oracle call these "sequences."

SQL standards refer to it as "identity." PostgreSQL and Oracle call these "sequences." As we will observe throughout the semester, MySQL, for whatever reason, does things differently and refers to it as an "auto-increment" key. This refers to the column here. In addition to primary keys, we also have foreign keys.

And the foreign keys are going to allow us to map a set of attributes from one relation to another relation, defining how those elements are linked together. Once again, this is different from what Codicel did. Codicel would actually have pointers from one record to another that you would literally follow, either through memory or through a disk access, to find the connected items. However, in the relational model, we use values to represent those relationships instead. As we mentioned before, we wanted to be able to keep track of all the artists in our album.

But if the album only has one artist, that's fine because we can simply store that single value. However, if I have a mixtape with multiple artists, we need to consider how to handle that. In the true relational model, you would need to store this information in a separate cross-reference table that keeps track of which artists appear on which albums. This would involve the use of foreign keys. You would have a foreign key from the artist table, specifically the artist ID, that points to a record in the artist table. Additionally, you would have an album ID, which is a foreign key pointing to the album table. Essentially, you are creating a relationship between the artist table and the album table through these foreign keys.

And again, it's up to the data center to decide how to make this work efficiently. There's going to be an index that says, for this record here, given a lookup, if I have an album ID, I need to have an index on that ID in the other table. So when I go to insert something into this table, I need to quickly check if this album ID actually exists. I can quickly do that lookup. These foreign keys allow us to handle constraints or other issues. For example, if I now delete an artist and want to cascade and remove all their albums, I can follow this table to find all the albums and then ensure I delete things here. In some cases, it can prevent you from deleting things. You might say, "I can't delete a record if I know I have a foreign key reference over here." Basically, the data system is preventing you from shooting yourself in the foot. And you may think, "Oh, I'm a CMU student."

I'm not going to make mistakes. Everybody makes mistakes. The data system can prevent you from causing a lot of problems. I sort of mentioned this with the foreign keys, along with the idea of constraints. These are a way to define what data is allowed to look like, either within a single attribute or across multiple attributes within a tuple, or what values are allowed to look like across multiple tuples within a table, or within a relation.

So he said, "Oh, the artist ID has to be unique because that's the primary key. That's a constraint. That means there can only be one tuple with a given artist ID across the entire table." The most common ones are going to be unique keys and foreign key references. The SQL standard from 1992 introduces the idea of global asserts, but I think some systems implement this, though they're rarely used because they can be quite slow.

Because think of it this way: every single time I insert into the table, I have to run another query to see whether my constraint has been violated or not. The most common place you'll see constraints is defined in the table itself, right? For example, I can say I have a name that is a VARCHAR, which is a string type, and then specify "NOT NULL." The "NOT NULL" part is the constraint that says you can't insert a record with a null name. Another option could be an explicit check constraint defined elsewhere.

We could say that the year has to be greater than 1900 because nobody can be born in the 1800s. It's not correct in the real world, but that's the idea of how you could apply different constraints like that. As I said, you have these global assertions. There's a create assertion command where you basically put a SQL statement in every single time you modify the table. This thing runs, but again, they're super slow. You can always think big; I've got a billion records and I have to scan to make sure that some constraint is not violated across those billion records.

Every single time I update that table, I've got to run that across a billion tuples, and that's not ideal. Alright, so the next topic is the DML. This is essentially the way we manipulate and interact with the database through the relational model. There are two main categories of DML that you could use in a database. The first one involves 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, where you specify the answer you want the data system to compute for you. You don't define how you want to compute it; you simply state what you want. So for this class here, in today's lecture, we're going to focus on this topic, because this is going to be relational algebra. As I mentioned, no database system will expose a relational algebra interface to you, as it is too cumbersome to write.

And again, you're essentially defining what the query plan should be. Most systems will support this declarative language, which is based on what we call relational calculus. For this class, you don't need to know relational calculus, but it's a higher-level form of defining operations over the relational model. If you take the advanced class, or if we offer a special topics class in the spring semester on query optimizers, relational calculus will come up sparingly. However, for our purposes here today and this semester, we primarily focus on relational algebra.

Earlier, the inversions of this course used to teach relational calculus, but nobody uses that in the real world unless you're building a query optimizer. Alright, so relational algebra is going to be based on it; it's going to define it. The relational model is going to define 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. However, this is not entirely true. Ted Codd's original paper in the 1970s defined these seven primitives. It has since been expanded because this doesn't handle things like sorting, aggregations, or group buys. But I want to cover the core primitives, and then it will be sort of trivial to see how you can extend that to do other things that 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 through each of them one by one. The most basic operation you can perform is a "SELECT." This corresponds to first-order predicate logic, where you specify how to identify the tuples that you want for a given relation. It could be from what I'll call the base relation, which is whatever I define in my database, directly referencing those tables. Alternatively, it could come from the output of another relational operator that feeds into my SELECT operator. Essentially, you're going to use predicates, employing some Boolean logic, to define which tuples are allowed or which tuples satisfy the constraints you want on the data.

And then any tuple that does satisfy the conditions is admitted as output. So, say I have a really simple table or relation with two attributes, `aid` and `bid`. I could define a selection with the predicate where `aid` equals `a2` against the relation `r`, and that just matches any record where `aid` equals `a2`. Right? It's like the `WHERE` clause in a `SELECT` statement. You can combine these conditions together using conjunctions and disjunctions. For example, I can say, "find me all the tuples from `r` where `aid` equals 2 and `bid` is greater than 102," and it produces that relation as the output. The way I always remember this is through the lowercase sigma symbol: S for sigma, S for select.

An easy mnemonic to remember that is: In SQL, which most people will be writing, it's just the WHERE clause. So, "SELECT * FROM R," and then my WHERE clause would be the predicate for how I'm filtering tuples. This is equivalent to defining the SELECT operator here. The next step is projection, where we're defining what the output should look like in terms of the attributes we care about from our input, as well as how to manipulate those attributes in any given way.

So again, the same relation on r with aid and bid. I could have a projection where I take whatever the input is from this interrelation—sorry, interoperator here. In this case, I'm performing a select where aid equals a2. Then, I take the output of this interselect and project it where I take the bid value, or the bid attribute, subtract 100 from it, and also produce aid as the output. Not only am I selecting which attributes I want, but I can also change the order of them, manipulate them, and perform arithmetic operations, string functions—whatever you want. You're essentially defining what you want the output to look like from any given input, and that’s equivalent to the select operator, the projection clause of a select operator in SQL.

So far, so good? Now we're going to be able to start combining relations together. The idea here is that instead of having one giant relation with every single possible attribute I could have for whatever it is I'm trying to model in my database, I will break it up into smaller relations and then combine them together to reconstruct the original form. I have the union operator, which essentially takes all the attributes from one side and all the attributes from the other side and combines them into a single relation. In this case, this operator only works if both relations you're trying to union have the same attributes and the same types. Right?

Because it's literally taking, concatenating, you know, taking R, putting S at the bottom of it, and that's the output. So in SQL, you can do this; there is a UNION operator, where you basically combine the values of two SELECT statements. Again, they have to have the same attributes because you're just concatenating the two pools, combining them into a single output. Of course, if there's a UNION, there's an intersection. An intersection is just finding the common values. Sorry, back to the question: if there’s a UNION and a tuple exists in both tables, will it reuse them? In the original relational model, no, because it's based on sets.

In SQL, the answer is yes. Sorry, the other way around. In the relational model, it removes duplicates. In SQL, it keeps them. So, in SQL, if you perform a UNION, it removes duplicates. If you use UNION ALL, it keeps them.

Because by default, they want to be efficient since it's extra work to find the duplicates. I should also note that this is unordered. So, even though I am showing "R" followed by "S", one key aspect we will see throughout the semester is that the order of the relational model in SQL is undefined. Therefore, it's acceptable for things to be inserted into your table and then, when you read them back, they may appear in a different order. This will open up numerous opportunities for us to optimize things in various ways, as we do not have to maintain that order.

Now, in some cases, we do want that order. We have to put constraints on top of that to achieve it. Some systems will always store data in a sorted order in some manner. However, we will see examples when we manipulate or update the database through transactions. If we happen to run a background garbage collector, it could reorder things in any way we desire, and we might receive results in a different order. Therefore, if you care about retrieving items in the correct order, you should define an "ORDER BY" clause in SQL.

But again, the original version of the relational model does not have that. So, intersection is, again, finding things that are in both. In this case, I have to have the same attributes. There's only one tuple that matches the same, so both A3 and 103 produce the output below. Difference is finding all the tuples that appear in the first relation, but not in the second relation, right?

Again, this is just a sort of set theory concept here; nothing exotic, right? So I can do this again in SQL using the except operator. Here, I have set A, and I produce my output: A1, 100, 101, A2, 102, because those things don’t exist in set S. However, since I have A3, 103 also in set S, that item is excluded from my output. Alright, so this is, again, basic set theory, but it still doesn't allow us to identify the relations or the connections between different sets that we would want. To do that, we want to perform what are called joins.

But before we begin with joins, we need to perform a Cartesian product, as that is the basis for how we will conduct joins later on. So, Cartesian product, yes? For the operations we discussed, do the columns have to be the same? His question is: for these operations here, do the columns have to be the same? Yes.

Joins, as we will see in a moment, do not require certain conditions to be met. However, for union, intersection, and difference, they must. Alright, so the simplest or naive join would be the Cartesian product, which involves taking the tuples from one relation and combining them with all the tuples from the other relation to find all possible combinations and produce the output. In this case, if I perform the Cartesian product on the relations, I will generate all of these pairs. For every aid, where aid is a1 and 101, I will generate all of these combinations by merging them together.

And then I go into the next tuple on this side and get all the 8212s, and then mash them together with that. Right? 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 doesn’t actually match with what's in the real world. This shows up when you do experiments, experiment analysis, and testing because you want to get all possible combinations of your inputs.

You would do the Cartesian product for that. But more importantly, from a theoretical perspective, this is going to be the basis for how we're going to perform joins in the next operator. What we want to do is find where the AIDs match with the SIDs because we know they are connected in some way based on how we define them in our schema. You can do this in SQL, as there is an explicit cross-join operator or keyword.

So I can say "SELECT * FROM R CROSS JOIN S," and that will give you the Cartesian product. Alternatively, while it is not recommended in the standard, you can simply list the tables separated by commas, and this will also produce the Cartesian product for you. All right? However, the joins are going to be the important thing that we care about. It's essentially about finding all the matches from one relation based on some value with the given attributes in S. Unlike the intersection operator, where the schemas of the two relations must be the same, a join does not have this requirement. Implicitly, it will look for the name of a column and find the corresponding matching name in the other column when I perform a join.

So for RNS here, when I perform a join on RNS and the operator, I'll find where the values of AID and BID are the same, and then the VALUE just sort of comes along for the ride too because it was part of the matching tuple. Right? So again, you can think of this as mashing the two tuples together and then checking to see where things match. The AID for R has to match the AID for S, and the BID for R has to match the BID for S. Then, you simply throw away the duplicate attributes. And that's your output.

Joins are going to be important for this topic. We will need to spend an entire lecture on them. Joins are where data systems will spend most of their time running queries. Therefore, this is the aspect we will try to optimize the most to ensure they run as quickly as possible. There are many different ways to define joins and various types of joins to consider.

We'll see more in the next class. In my example here, I’m implicitly joining based on having the values be the same, or rather, the names of the attributes being the same. That’s called a natural join. There is a natural join keyword that essentially looks up the names of columns to see whether they match, and then performs the join accordingly. I don't recommend using this method because, again, it implicitly determines what the join should be based on the column names.

You actually want to define how you want to perform your join. You can do this with a JOIN clause for RNS, using the USING keyword to specify what you're looking up on. Alternatively, you can use the ON clause, in which you explicitly state that R has to equal AID for S, and the BID for R has to equal the BID for S. The latter option is probably what you will use if you're writing by hand, as it contains a bit more information because you are specifying which columns you want to use for the join. Additionally, I do not recommend using a NATURAL JOIN.

Again, the ANSI SQL standard requires you to explicitly define as much as possible so that if the schema changes or things evolve, it doesn't break your application code. Alright, so there's a bunch of other stuff that came along later in the 1970s for the relational model, such as how to rename columns, how to assign columns to variables, removing duplicates, and performing aggregations, sorting, and division. These features emerged after Ted Codd's original paper, and most data systems are going to support everything mentioned above, although they may not necessarily support division. Okay, so that's the crash course you need to understand for relational algebra. As we go along, we should build the query engine of a system based on these ideas. Alright, as I mentioned before, relational algebra is considered a procedural language.

Even though it's mathematical notation, you can easily see how to implement a system based on it. One of the complaints about Ted Kott's paper in the 1970s was that people thought it was too mathematical. I’m not claiming to be brilliant or that I can easily decipher everything, but I was surprised when they said that, because it’s not that esoteric or difficult.

I think any computer science undergraduate should be able to understand that. But it's still about defining the steps you want the data system to perform in order to compute your query. So I have to say, if I'm going to join R and S, I have to define in what order I want that to happen. I would say, all right, my choices are to first join R and then S, and then do the select on it to filter out the tuples that I want. Or I could filter S first based on the bid, then take whatever the output of that select operator is, and then do the join against that.

And again, there would be pretty dramatically different performances of these two queries based on what the database actually looks like. If RNS only has about 10 tuples, then it's not that big of a deal. But if RNS has billions of tuples, then I definitely want to filter out as much as I can from S before I join it with R. However, in relational algebra, there is no concept of allowing things to be reordered. I'm defining exactly what I want to happen. This will lead us to the next class, talking about SQL, but a better solution would be to provide a high-level definition or declaration of the answer I want in my query and let the data system determine the best way to perform it.

And again, now if I change the physical layout of the data that is in my database, I don't have to change my query plan or my query if it's defined as SQL; I let the data system figure that out for me. So that's why SQL matters. Again, we'll see this more in the next class. Alright, so the relational model defined by Ted Codd in the 1970s didn't come with a programming language. SQL was invented by IBM a few years later.

Ted Kott eventually proposed his own query language called SQL, but nobody actually implemented that. There was also an earlier version of SQL called SQUARE, which we'll see next time. It required a keyboard that didn't exist because you had to write things vertically, which was quite bizarre. However, SQL eventually became the de facto standard that it is today, even though it wasn't the first one.

There was another language called Quell, invented by Stonebreaker from Ingress, which later became PostgreSQL. However, there were various other variations of relational query languages. SQL ended up being the dominant one. There is an SQL standard, but again, nobody actually implements that exactly in every system. So, the idea is that instead of writing procedural code, like doing my lookup in Python code, I'm better off writing SQL.

Because now I don't care about how stuff is physically stored; I don't care how the query plan is actually going to execute. I let the data system handle all that for me. So, any questions about the relational model? Yes? When we talked about relational algebra, we set up a key, like a primary key in that situation. Because when we did unions, I didn't understand: What if we had two values with the same key here?

So his question is, when we talk about relational algebra, we didn't mention primary keys. That's because you would define that in the schema, specifying what your relations look like. The data system can then enforce the constraint that the primary key must be unique. However, when it comes time to actually run queries, you don't care what the primary key is. I can perform intersections and other operations without worrying about what the primary key is. Likewise, I didn't have to determine what the primary key is.

It's there. It's an integrity constraint. All right, so I want to briefly talk about, in the last five minutes, the leading alternative, which is going to be the document JSON model. The vector database concept is currently the hot trend. The leading alternative is the document JSON model, and then the vector database concept is what's popular now. I just want to expose you to these ideas quickly, and then we can mostly ignore them for the rest of the semester. The document data model is essentially about thinking in terms of JSON, XML, or object-oriented data. The idea is that you're going to have some kind of hyper-collection of data where there are these name-key value pairs. However, within a given document, you can have nested arrays, nested documents, and so forth.

JSON is how you would implement this today. There are older systems from XML, and even earlier than that, in the early '90s and late '80s, when object-oriented programming was a big thing, there were object-oriented databases that you may not have heard of. These databases basically tried to map C++ objects into objects in a database. Instead of operating on relations, you would operate on objects. We will explore this more in the next class, but the problem they were trying to solve is known as the relational object impedance mismatch. This means that I am writing code in my application based on objects that have this hierarchical structure, but when I have to store it in my database, the database requires me to store it as relations. Now, I need a way to map that back and forth between relations and objects, which can be cumbersome. There are several systems out there that implement this document model.

MongoDB is probably the most famous one. CouchDB or Couchbase is likely the second one. However, this idea dates back to the 1980s. Returning to my example of our music store, I would have a relation for artists, a relation for albums, and then a cross-reference table, or a cross-reference relation, that maps artists to albums. Now, if I want to get all the albums that a given artist appears on, I have to perform a join to go from the artist table, to the artist-album table, and then to the album table.

So, the document model proponents argue that using joins is inefficient, and suggest eliminating them altogether. Instead, they propose embedding all the albums an artist appears on. Conversely, for a given album, you would embed all the artists featured on it. The concept is similar to defining classes in Python, Java, or other programming languages. When you want to store data in your database, for a specific artist, you would embed the list of albums they are associated with. Consequently, when you want to perform a lookup for a given artist to retrieve all their albums, it becomes one query that fetches the artist's record and pulls out all their albums. The question is: Is this a good idea or a bad idea?

Again, it's obvious what my answer is going to be. Why is it a bad idea? Yes, you cannot query directly on albums. He says you can't query directly on albums.

"You could. You can do nesting inside to get things. Yes? Yes? Maybe it's kind of making you predict what people are going to query and then try to capture that?" She said yes.

She said, and she's correct, that you have to predict what the queries are going to want to look up and then model that in your database. Absolutely, yes. Likewise, I'm going to end up duplicating a bunch of information. If an artist appears on, sorry, if multiple artists appear on one album, I've got to record that over and over again. So in some cases, this nesting makes sense; in many cases, it doesn't, yes?

If you want to delete an album, you just need to handle the content. He mentioned that if you have to delete an album, you need to find all the artists that appear on it. Yes, you could create an index. An index could help with that.

But still, it's implicitly in your application what the layout is. So, in some cases, you do want to store things as JSON in your database, but oftentimes, you do not. All right, the last one I want to talk about is vector databases.

So this is the hot topic now. There are a number of companies that have received significant funding and are building systems in this space. WeV8 is coming to speak with us on KB in a few weeks. I like those guys; they're good people.

But no, they're fun. I was on their podcast, and they're enjoyable. So, a vector database, at its core, means that when you say you have a vector database, it really refers to a document database that also has this extra data type called a vector, or an embedding. Think of that as a large array of floating-point numbers.

And what they are trying to provide is the ability to perform approximate nearest neighbor searches based on these vectors. These vectors will be generated from some kind of transformer embedding, attempting to represent what is actually in the data you are storing. At the end of the day, it’s just a fast index for approximate nearest neighbor search. So, what does that look like? For example, let's say I have my album table, and I am going to extract all the lyrics from these albums from a source like Rap Genius. I will then feed that data into some kind of transformer, either using an OpenAI model or something from Hugging Face.

And then that's going to generate a bunch of these embeddings, which are just arrays of floating-point numbers. The magic of the transformer is that somehow, implicitly, the information or the semantics of the data that I fed into the transformer are contained in those floating-point numbers. I will then store these in my vector database, which is essentially a vector index. The most common one is HNSW (Hierarchical Navigable Small Worlds).

IVF flat is another option, but there are a bunch of libraries like Metafest or Spotify Noise. There will be some data structures we'll cover in a few lectures to easily perform nearest neighbor searches on these embeddings. So now my query, instead of doing exact lookups like "find me Jizz's albums," can be something like "find me albums that are similar to Liquid Swords." If I have the lyrics to "Liquid Swords," I can convert that information and input it into my transformer. I will obtain the same kind of embedding that I would get when I first loaded my database.

And then I perform a nearest neighbor search on the vector index, which returns a ranked list of matches. The vector database is essentially this part here. It can also store metadata and this information that I have over here as JSON, right?

So I can say, "Find me all the albums that sound like 'Liquid Swords' that came out after 2012" or something similar, and I can incorporate that into my lookup. But at its core, a vector database is this vector index piece here. In the last year or so, pretty much all the relational databases now support vector indexes. So again, I've argued, and I've told the UVA guys this directly, that the idea of vector search and nearest neighbor search does not mean you have to build a whole new system that throws away everything we talked about the entire semester. It's just an extra feature we can add, and the relational model can accommodate it. The SQL standard does not support or have a notion of these nearest neighbor searches.

Postgres, through pg-vector, has its own API. Oracle has copied that. I believe this will end up in the SQL standard in a few years, and the vector developers will have to figure out how to overcome that. Okay?

This is like a crash course in vector databases in two minutes. The VDA experts will come to talk about it more later in the semester. All right, so whatever it is, databases are ubiquitous. Databases are important. Databases are the second love of my life.

Relational algebra is going to be the foundation for how we will build our systems to support them. We will see this repeatedly as we discuss career optimization and career execution. Certainly, we will see this in the next class when we talk about SQL.

The next class will be a Q&A session. We will explore modern SQL. By modern SQL, I mean that I won't show you what a "SELECT *" statement is. It's 2024, and most of you are students, so I'm assuming many of you have encountered SQL before in some basic form.

So I'll try to teach you the more advanced concepts and where things deviate from the SQL standard. Please make sure you understand basic SQL to prepare for the next class. Okay? Alright. We have eight minutes left.

Any questions about databases? Yes? You talked about it a little bit earlier. We discussed the blurry line between relational and document-based databases, and how I can use DynamoDB for a bit. We talked about the blurry line between relational and document-based databases.

So I can use DynamoDB a little bit. Yes. It feels like you're using a relational database. It does support sequences, right? On to it.

So, can you explain the conversion a little bit more and what that means? His question is about DynamoDB. DynamoDB is one of Amazon's first NoSQL databases. It originally started off, I think, as a key-value store, and then they added support for JSON.

And then, more recently, they've added what looks like tables. I don't think it's directly SQL; I believe it's part of QL. It's not GraphQL. A part of QL is Amazon's SQL, and it resembles SQL.

So, why is there convergence between the NoSQL community and the relational world? Well, it's because all the discussions we have today highlight why having a relational model and ensuring you can't make mistakes in your database is a good idea. They have come to realize that customers actually want these features, and they have added them on top of the existing models. That's why I think there is a convergence. Just as no one is going to invent a new mathematics where 1 plus 1 equals 2 is not true, I believe the relational model is the correct way to implement and represent data. While additional features, like vector indexes and various ways of handling JSON, can be added on top of that, everyone is essentially returning to the idea that the relational model is the right approach.

Terakawa's a genius, right? I have a question about the vector database. I also know there's a very famous startup called Rockside.

They're using AI. I wonder, for this kind of real-time vector search database, what realistic applications you can imagine for vector indexes, particularly in using vector databases?

All right, so his first question he started off with is, "OpenAI made a major acquisition this summer. They bought Rockset." Rockset was a database startup, a relational database startup founded by the creators of RocksDB out of Facebook. An OpenAI company, you paid a lot of money for it. So the question is, first of all, what is OpenAI's plan with Rockset?

I can't tell you. But what are some uses for a vector database? Going back to my example, this idea of semantic search: for instance, finding albums that are similar to "Liquid Swords." I'm not defining what it means to be similar, just looking for albums that are akin 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, if you have your transformer, know that "slinging rocks" means dealing drugs. Even though you asked for "slinging rocks," it somehow magically knows, due to the training data it's based on, how to match that to different things. So it's a way to do better searching based on semantics rather than finding exact matches. That's what these systems are being used for.

Yes? Are we not able to perform these kinds of semantics through a traditional database? The question is: Are we not able to conduct these kinds of semantic or fuzzy searches through a relational database? The question is, are we not able to execute this semantic search in a relational database?

No, I said absolutely, yes. Assuming you can store this as an embedding and then have a vector index, you can perform a fast approximate nearest neighbor search. You could write SQL queries against this. PostgreSQL does this with a PG vector. Almost all relational databases now have some form of a vector index. You can do this. Prior to this, though, the way you would perform lookups would be through fuzzy matching.

"Could you find me all the albums that have the word 'swords' in their titles? You couldn't do this because of the semantic meaning—that's a new aspect in the background. If every record needs to go through a transformer, wouldn't that be very slow? Yes. I mean, it takes milliseconds. It takes milliseconds."

Yeah, it's not seconds. So it's slower than a relational database? I can be very clear here: you can put this in a relational database, right?

The question would be, is running through the transformer to get back the embedding and then performing the lookup going to be slower than using an inverted index, which we'll cover later on? Maybe. It depends on what this is and what's in memory. There are so many different factors involved that it's hard to say. Additionally, that assumes you will obtain the data you want using a fuzzy search anyway.

Again, for some things, it's not going to work because there's no understanding of what that actually is in the data and what it means. That's what the transfer does for you, yes? When we are taking interviews, sometimes the interviewer asks us to design a system, and they want us to choose which kind of database, like SQL or NoSQL. Sometimes they are more satisfied when you choose NoSQL. But, as you say, well, forget him if you did that, right?

His question is: sometimes, during a job interview, the interviewer will ask you to pick a database for the prototype system you're building. The answer is PostgreSQL. Always pick PostgreSQL. I'm dead serious. Right? You can't just say, "Oh, because Andy said so," but PostgreSQL is a rock-solid database system that has many features you would find in an enterprise-level system.

And actually, not just for interviews, for anybody doing a startup, your first choice would be Postgres, right? Because you wouldn't want to spend your time building your application while also worrying about what data system you want to use. So you can just choose Postgres, as you want to focus on building the application, because that's what truly matters. No one is going to know or care whether your application is running on Postgres or MongoDB, because they don't interact with the data at that level.

Postgres is almost always the right choice. Now, you may reach a point where Postgres can't scale and handle your data. At that point, you won't pay me, but you'll pay someone else a lot of money to help figure out how to make Postgres scale. In the background, yes? Yes, so you're talking about the enterprise. Can you speak up?

Sorry. Yeah, so in terms of career opportunities, what do you think? What are some good companies where you can work? It's a good place to work. And where do you think we should avoid? This question is: what are some good database companies to work for?

What are some bad database companies to work at? Alright, so let's discuss good database companies. The great thing about databases is that there is a lot of money involved, and many people are working on building database systems. For example, if you're in operating systems...

Where can you go to build an operating system? IBM, Red Hat, maybe, right? The Linux developers are all working on their various projects, but there aren't many competing operating systems. There are a ton of databases, and if you want to go to a big company like Microsoft, Amazon, Google, or even Facebook, all of them are building database systems.

And then there are a bunch of startups that are all in this space as well. Now, some of them have questionable financial footing. I mention this because my database startup failed this summer. However, there are a lot of choices in the database market, and there is a lot of money in it, right?

Even now, even though the relational model and relational databases are 50 years old, there are still people trying to build new systems all the time. In terms of bad companies, I would say right off the bat, EnterpriseDB is one to avoid. As for other options, particularly startups, you definitely want to talk to people and check their financials. This can help you gauge how much they might be chasing fads.

Like if all of a sudden they started 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, nah, it looks a little dicey, right? Another interesting avenue is also, I mentioned like Google. Google and Amazon, they’ll sell you, you know, data services. Then those companies, like— I can’t say, well, I’ll bleep it out—are building a database system. And the great thing about it is they’re building it in-house. They don’t have to worry about getting customers because they’re their own customer.

But they're actually building a whole system from scratch and doing some interesting things. There are so many different options for working with databases, and that's why I think this class is super important. You’re going to encounter these concepts throughout your life, and companies don't want to hire a bunch of random JavaScript programmers because those individuals could break your database system. You don’t want them to touch the internals. They want CMU students who know how to handle these things and are eager to hire you all.

Yes, quickly. Do you think this class is a good preparation for a database career? His question is: Is this class a good preparation for a database career? I am biased because it's my class. I've been told by certain database companies that this class serves as the onboarding process for new employees.

I've also been told that the interviews for some database companies are basically entirely from this class. So take that to mean what it means. There's always money in databases. How about that? Okay?

Last question: What's the best way to incorporate blockchain into my database? Alright. Do you have a real question? What happened to the DJ in this case?

All right. Yes, unfortunately, we cannot have a DJ this year due to legal issues with Warner. I apologize for this. I have tenure, but there is a moral turpitude clause at CMU, which means I could still be fired. So, I’m trying to lay low this year. I apologize for any inconvenience.

Okay. All right. All right, guys. That's it.

See you on Tuesday or Wednesday. I need something refreshing when I finish manifesting. Too cold, like a hobo with a Smith & Wesson. One court, and my thoughts are hip-hop related. Write a rhyme, and my pen is intoxicated. We'll be right back.

A girl by me and my mic, down with oil. The racket still turns with 30-degree burns on one man. I heat up your brain and give it a suntan. So just cool, let the temperature rise. What's odd about it all?