Database Notes part 2

In the last part we outlined notions of what a database is, how a database fits inside the CAP theorem, general notions of a query and a schema, how indexes assist with faster searching, a brief overview of relational and non-relational databases, and how loose and tight coupling between a database and its front end are differentiated.

Moving forward from the swath of new terminology, in this article we will be discussing some more fundamentals:

1. Data models
2. Keys
3. Data redundancy & normalization
4. Database clustering and big data

Let’s begin.

Data models

A Database Management System (DBMS) model defines the logical design and structure of a database (in essence, it is a collection of concepts) that defines how data will be stored, accessed, and updated in this database management system. By structure of a database we refer to what data types, relationships, and constraints apply to the data. Most data models also include a set of basic operations for specifying how retrievals and updates on the database are handled.

Note that the description of a database is called the database schema, which is specified during database design and is not expected to change frequently, if at all.

Around the late 1970s the logical view of data was an important topic of discussion in academia, and certain models were conceptualized.

Hierarchical Model

The gist of it is that data should be organized in a tree-like structure; the root node signals the start of a piece of data. Each child node has one parent node. This model is also called a “one-to-many” relationship, where one record in a table can be associated with one or more records in another table.

Network Model

The network model provides a more natural view of data by separating entities and relationships (to a certain extent). In this model, you are allowed to have more than one parent node, data is more related, and this can be used to model many-to-many relationships. Its capability to achieve data independence has been challenged, and it was used before the relational model.

Relational Model

The relational model is based on representing data and the relations among those data in the form of tables. It can achieve a high degree of data independence, but it may lose some important semantic information about the real world. It used to reduce a concept to its core pieces and have a key to allow it to relate to another simple concept.

Entity-relationship Model

The entity-relationship model adopts the more natural view that the real world consists of entities and relationships between those entities. Entities are objects or things that can be described by their characteristics. As you identify entities, you list the attributes that describe the entity. For example, a customer is an entity that has a name, an address, a phone, and other details. The basic rule is that an entity is an object or thing.

The difference between these two is that the E-R Model is entity-specific, and the Relational Model is table-specific.

Moving forward on concepts of this model, the following is noted.

Relational database — Keys

In relational databases, references to other rows and tables are indicated by referring to primary key attributes via foreign key columns. A primary key is a value that is unique across all rows in a table. Indexing based on primary keys is useful, as finding a particular row is easier than doing it row by row. Meanwhile, a foreign key acts as a constraint where you have, for instance, two tables. A foreign key ensures that a value in table 1 exists (as a primary key) in another table.

Join operations are computed at query time by matching primary and foreign keys of all rows in the connected tables.

Relational database — Normalization

Database normalization is the process used to organize a database into tables and columns. The main goal is that a table should be about a specific criteria, and that only those columns which support that criteria are included in that database table. The 2nd goal is to eliminate the number of duplicate data contained within a database. These normal forms establish a stringent and objective set of rules to which a data model must adhere to. The 3 (but can be more) stages of organization of data into tables are called normal forms. As tables iterate through each normal form they begin to be more focused and granular. In a simple way, data takes up space, and you wouldn’t want to include every piece of data in every single table, as opposed to gathering data by having linked tables. Before starting the process of normalization, you should already have a logical ERD describing your problem domain. This logical ERD should describe all of the entities that make up the problem domain, their major attributes, and their relationships.

Where and when to do this is important in the design stage. Sometimes you don’t want to have the best design possible because the application you are designing has other goals where “normalization” is not as important as front-end use. So a normalization/schema implies long-term organization that considers the growth of your data.

You generally normalize databases so that any piece of data only lives in one place. This means that you can change one thing and not have to worry about the rest of your data becoming inconsistent.

In an ideal world, all databases would be perfectly normalized. In the real world, you find yourself making sacrifices for performance. Let’s look at Reddit for a (theoretical) example:

You’ve got subreddits. Each subreddit has a bunch of posts. Each post has a bunch of comments in it. With a properly normalized database you’d have a table full of subs, a table full of posts, a table full of comments, and a table full of votes. In order to display the front-page of a given sub, you’d need to take all of the posts and count up their votes to figure out which ones are on top. You also need to join that to your comments table to display the number of comments in each post. This is a lot of database work to do on every page load.

You could easily speed this up by adding the vote score and comment count to each post’s record. That’s denormalization — you’re storing redundant information in multiple places across the database.

On the other hand, when the entire database is defined as a single large table, it can result in a large amount of redundant data and lengthy searches for just a small number of target rows. It can also result in long and expensive updates, and deletions in particular, and result in the elimination of useful data as an unwanted side effect. Now, going further, each user submits his comment in a comment tree. An important thing to know about comments on Reddit (and Disqus has this also) is that the comments are threaded. This means that you nest replies so you can see the structure of a conversation. They can also be linked sometimes too deep within that structure. This makes it a bit more complicated to display these trees. It is pretty computationally expensive to go and say, there’s 10,000 comments on this thread, I need to look up all 10,000 comments, find out what the parents are and all the children.

We can improve this performance hit by having the parent relationship tree in one place so we have ahead of time which subset of comments are needed and only look at those comments. Now this is better but also is kind of expensive to do still. So, we defer it to offline job processing.

One advantage in the comments tree is that we can batch up messages and mutate the trees in one big batch. That allows for more efficient operations on them. A more important thing to note is the tree structure is sensitive to ordering. If I insert a comment and its parent doesn’t exist, that is weird in a tree structure, right? So that needs to be watched out for, because things happen, and the system had some stuff to try and heal itself in that situation, where it will re-compute the tree, or try to fix up the tree. Think of how RAM works: fast switching pointers. This is how you get a user’s data out of billions in a table. The software doesn’t need to know that the person’s first name is John, it just needs to know that that user’s pointer is here and it points to that table and then that table points to the next connected bit of data, etc. It is a chain of tables. Again, most of the retrieval of the data isn’t getting ALL of the data, it is just getting the pointer. That pointer leads to the next pointer, and so forth. Just fast swapping pointers and then one DISPLAY of the data.

For more information on Reddit’s architecture I highly recommend The Evolution of Reddit.com’s Architecture.

Database clustering and big data

The two biggest goals of clustering are scalability and fault-tolerance. Scalability is the idea that as the cluster needs to do more work or store more data, you can easily just add more computers and the cluster automatically adapts. Fault-tolerance is the idea that if one of the computers randomly crashes (or if there’s an issue with the network interconnecting them), the rest of the cluster can deal with it gracefully. All large websites today heavily use clustering and the internet as we know it could not exist without it. Sometimes a single cluster may contain tens of thousands of servers.

Clustering technology and algorithms are part of a very active area of research called distributed systems.

Next you need to discuss the various methods of clustering. Oracle RAC has data that’s centrally stored and all cluster nodes can access 100% of the data. Or a federated system like MySQL Clustering or DB2, where the configuration is similar to sharding, whereby rows (as opposed to columns in a normalization effort) of a database table are multiple disjoint pieces, each hosted by a separate machine. The differentiator between these products and various NoSQL things like Cassandra, MongoDB, and other products is: are they ACID compliant? What happens in the middle of a workpiece if the task breaks? Many applications must be transaction-safe to prevent losing money. If the transaction breaks, is the user made whole again? If the product is acid-compliant like Oracle, DB2, SQL Server, the answer is yes. Not so with most of these other products like Cassandra. That’s why, if your application has direct financial impact, using something like Cassandra is risky. That said, one could build an application using both Cassandra and Oracle: the serious transactions are managed by Oracle/DB2 while the other parts are managed by Cassandra. Quite a lot, since usually a distributed database like Cassandra is just one component of a larger distributed system. Nowadays service-oriented architectures are the norm when building large systems. Instead of having just a single web application that talks to the database (like your traditional PHP/MySQL setup), you write dozens or perhaps hundreds of small independently running services that each handle one aspect or feature of the larger application. You need a lot of supporting infrastructure to be able to do that with any sanity, as orchestration becomes difficult. For example, how do you deploy code/programs in that situation? You can’t just let engineers copy things manually to each server, since you may have thousands of such servers. So you need lots of internal tooling to let engineers just click a button and have the entire process automated. So you end up with a kind of layered organization, where you have developers building software whose clients are other developers in the company. You really need entire teams of engineers dedicated to just maintaining the infrastructure and operations of these systems. There are many examples of small/medium companies going down this road and failing miserably because they just don’t have that kind of manpower and vastly underestimate how much work it takes. This is where we transition into “big data”. Big Data refers to database storage systems that help manage very large or very dimensional data structures. This happens by storing the data itself across multiple drives / volumes, and creating aggregated indexes or “nodes” to slice the data for retrieval. The actual mechanics of this can be pretty complicated, but there are drop-in solutions like Hadoop to streamline the process. Depending on how quickly you want the data retrieved, how deep the data is, how many simultaneous calls you expect, and a host of other factors, you’ll set the number of nodes accordingly to balance cost (each new aggregation requires disk space and horsepower) and function (more nodes = faster retrieval). You might be surprised by what data actually qualifies as “big” data. With proper indexing and partitioning, a SQL DB can handle millions upon millions of records without flinching. On the other hand, a poorly optimized DB can result in slow read times and clunky operation with just a few million transactions.

End of part 2

Bibliography:

• Chen, P.P.S., 1976. The entity-relationship model—toward a unified view of data. ACM Transactions on Database Systems (TODS), 1(1), pp.9-36.
• Marton, J., Szárnyas, G. and Varró, D., 2017, September. Formalising openCypher graph queries in relational algebra. In Advances in Databases and Information Systems (pp. 182-196). Springer, Cham.
• Elmasri, R. and Navathe, S., 2010. Fundamentals of database systems. Addison-Wesley Publishing Company.
• The Evolution of Reddit.com’s Architecture. https://www.infoq.com/presentations/reddit-architecture-evolution/
• Martinez-Bazan, N., Gomez-Villamor, S. and Escale-Claveras, F., 2011. DEX: A high-performance graph database management system.
• Database Modeling and Design. Toby Teorey, Sam Lightstone, Tom Nadeau. Morgan Kaufmann Publishers, San Francisco, 2006. ISBN 13: 978-0-12-685352-0.
• https://bitalksbi.com/category/dbmsconcepts/page/2/
• https://www.studytonight.com/dbms/database-model.php