NoSQL for Mere Mortals (2015)

---

Values

Values are data stored along with keys. Like luggage, values in a key-value database can store many different things. Values can be as simple as a string, such as a name, or a number, such as the number of items in a customer’s shopping cart. You can store more complex values, such as images or binary objects, too.

Key-value databases give developers a great deal of flexibility when storing values. For example, strings can vary in length. Cust123.address could be “543 N. Main St.” or “543 North Main St. Portland, OR 97222.” Values can also vary in type. An employee database might include photos of employees using keys such as Emp328.photo. That key could have a picture stored as a binary large object (BLOB) type or a string value such as “Not available.” Key-value databases typically do not enforce checks on data types of values.

Because key-value databases allow virtually any data type in values, it is important for software developers to implement checks in their programs. For example, a program that expects either a BLOB or a string with a value of “Not available” might not function as expected if the string “No photo” is used instead. A programmer might decide to support any BLOB or string as valid values, but it is up to the programmer to determine the range of valid values and enforce those choices as needed.

Differences Between Key-Value and Relational Databases

Key-value databases are modeled on minimal principles for storing and retrieving data. Unlike in relational databases, there are no tables, so there are no features associated with tables, such as columns and constraints on columns. There is no need for joins in key-value databases, so there are no foreign keys. Key-value databases do not support a rich query language such as SQL.

Some key-value databases support buckets, or collections, for creating separate namespaces within a database. This can be used to implement something analogous to a relational schema, especially when combined with a key-naming convention like the one described previously.

If you have developed relational data models, you might have noticed parallels between the key-naming convention and tables, primary keys, and columns. The key-naming convention described previously basically uses the convention of concatenating a table name or symbol, a primary key, and a column name. For example, the key ‘cust123.address’ would be equivalent to a relational table named cust or customer, with a column called address, and a row identified by the primary key ID of 123 (see Figure 2.13).

Figure 2.13 The key-naming convention outlined above maps to patterns seen in relational database tables.

Document Databases

Document databases, also called document-oriented databases, use a key-value approach to storing data but with important differences from key-value databases. A document database stores values as documents. In this case, documents are semistructured entities, typically in a standard format such as JavaScript Object Notation (JSON) or Extensible Markup Language (XML). It should be noted that when the term document is used in this context, it does not refer to word processing or other office productivity files. It refers to data structures that are stored as strings or binary representations of strings.

Documents

Instead of storing each attribute of an entity with a separate key, document databases store multiple attributes in a single document.

Here is a simple example of a document in JSON format:

{
firstName: "Alice",
lastName: "Johnson",
position: "CFO",
officeNumber: "2-120",
officePhone: "555-222-3456",
}

One of the most important characteristics of document databases is you do not have to define a fixed schema before you add data to the database. Simply adding a document to the database creates the underlying data structures needed to support the document.

The lack of a fixed schema gives developers more flexibility with document databases than they have with relational databases. For example, employees can have different attributes than the ones listed above. Another valid employee document is

{
firstName: "Bob",
lastName: "Wilson",
position: "Manager",
officeNumber: "2-130",
officePhone: "555-222-3478",
hireDate: "1-Feb-2010",
terminationDate: "12-Aug-2014"
}

The attributes hireDate and terminationDate are in Bob’s document but not Alice’s. This is not a problem from the database perspective. Developers can add attributes as needed, but their programs are responsible for managing them. If you expect all employee documents to have first and last names, you should implement a check in your code that adds employee documents to ensure that the rule is enforced.

Querying Documents

You might be wondering, why couldn’t you store JSON or XML documents in key-value databases? Because key-value databases have few restrictions on the type of data stored as a value, you could store a JSON document as a value. The only way to retrieve such a document is by its key, however.

Document databases provide application programming interfaces (APIs) or query languages that enable you to retrieve documents based on attribute values. For example, if you have a database with a collection of employee documents called “employees,” you could use a statement such as the following to return the set of all employees with the position Manager:

db.employees.find( { position:"Manager" })

As with relational databases, document databases typically support operators such as AND, OR, greater than, less than, and equal to.

Differences Between Document and Relational Databases

As noted, a key distinction between document and relational databases is that document databases do not require a fixed, predefined schema.

Another important difference is that documents can have embedded documents and lists of multiple values within a document. For example, the employee documents might include a list of previous positions an employee held within the company. For example:

{
firstName: "Bob",
lastName: "Wilson",
positionTitle: "Manager",
officeNumber: "2-130",
officePhone: "555-222-3478",
hireDate: "1-Feb-2010",
terminationDate: "12-Aug-2014"
PreviousPositions: [
{ \position: "Analyst",
StartDate:"1-Feb-2010",
endDate:"10-Mar-2011"
} {
position: "Sr. Analyst",
startDate: "10-Mar-2011"
endDate:"29-May-2013"
} ]
}

Embedding documents or lists of values in a document eliminates the need for joining documents the way you join tables in a relational database. If there are cases where you stored a list of document identifiers in a document and want to look up attributes in the documents associated with those identifiers, then you would have to implement that operation in your program.

Document databases are probably the most popular type of NoSQL database. They offer support for querying structures with multiple attributes, like relational databases, but offer more flexibility with regard to variation in the attributes used by each document.

The next section discusses the column family database, which is another type of NoSQL database that shares some important characteristics with relational databases.

Column Family Databases

Column family databases are perhaps the most complex of the NoSQL database types, at least in terms of the basic building block structures. Column family databases share some terms with relational databases, such as rows and columns, but you must be careful to understand important differences between these structures.

These differences are discussed in Chapters 9 through 11. In the meantime, let’s examine the basic building blocks of column family databases.

Columns and Column Families

A column is a basic unit of storage in a column family database. A column is a name and a value. (Some column family databases keep a time stamp along with a name and value, but let’s ignore that for now.) See Figure 2.14.

Figure 2.14 A column consists of a name and a value. In this example, the column is named lastName and has a value of “Wilson.”

A set of columns makes up a row. Rows can have the same columns, or they can have different columns, as shown in Figure 2.15.

Figure 2.15 A row consists of one or more columns. Different rows can have different columns.

When there are large numbers of columns, it can help to group them into collections of related columns. For example, first and last name are often used together, and office numbers and office phone numbers are frequently needed together. These can be grouped in collections called column families.

As in document databases, column family databases do not require a predefined fixed schema. Developers can add columns as needed. Also, rows can have different sets of columns and super columns. Column family databases are designed for rows with many columns. It is not unusual for column family databases to support millions of columns.

Differences Between Column Family and Relational Databases

Column family databases and relational databases are superficially similar. They both make use of rows and columns, for example. There are important differences in terms of data models and implementation details.

One thing missing from column family databases is support for joining tables. You might have noticed that the term table has not been used when describing column family databases. This is intentional. Tables in relational databases have a relatively fixed structure, and the relational database management system can take advantage of that structure when optimizing the layout of data on drives and when retrieving data for read operations. Unlike a relational database table, however, the set of columns in a column family table can vary from one row to another.

In relational databases, data about an object can be stored in multiple tables. For example, a customer might have name, address, and contact information in one table; a list of past orders in another table; and a payment history in another. If you needed to reference data from all three tables at once, you would need to perform a join operation between tables. Column family databases are typically denormalized, or structured so that all relevant information about an object is in a single, possibly very wide, row.

Query languages for column family databases may look similar to SQL. The query language can support SQL-like terms such as SELECT, INSERT, UPDATE, and DELETE as well as column family–specific operations, such as CREATE COLUMNFAMILY.

The next section discusses a fourth type of NoSQL databases known as graph databases, which are well suited for addressing problems that require representing many objects and links between those objects. Social media, a transportation network, and an electric grid are just a few examples of areas where graph databases may be used.

Graph Databases

Graph databases are the most specialized of the four NoSQL databases discussed in this book. Instead of modeling data using columns and rows, a graph database uses structures called nodes and relationships (in more formal discussions, they are called vertices and edges). A node is an object that has an identifier and a set of attributes. A relationship is a link between two nodes that contain attributes about that relation.

Nodes and Relationships

There are many ways to use graph databases. Nodes can represent people, and relationships can represent their friendships in social networks. A node could be a city, and a relationship between cities could be used to store information about the distance and travel time between cities. Figure 2.16 includes an example of flying times between several cities.

Figure 2.16 Properties of relationships or nodes store attributes about relations between linked nodes. In this case, attributes include flying times between cities.

Both the nodes and relationships can have complex structures. For example, each city can have a list of airports along with demographic and geographic data about the city, as shown in Figure 2.17.

Figure 2.17 Nodes can also have attributes to describe the node. In this case, attributes include information about the airports in the city along with population and geographic area.

Graph databases get their name from a branch of mathematics called graph theory. Graph theory is the study of objects represented by vertices and relations represented by edges. Graph theory is not related to the study of charts and other visualizations sometimes referred to as graphs.

Differences Between Graph and Relational Databases

Graph databases are designed to model adjacency between objects. Every node in the database contains pointers to adjacent objects in the database. This allows for fast operations that require following paths through a graph.

For example, if you wanted to find all possible ways to fly from Montreal to Mexico City using the graph you saw in Figure 2.16, you could start at the Montreal node and follow each of the adjacent nodes to Boston, Chicago, and Tokyo, and then to Mexico City. At the Boston node, you would find no relationship with Mexico City and assume that there are no direct flights available from Boston to Mexico City. From Chicago, a direct flight to Mexico City would take 3 hours and 50 minutes. That time, plus the 1 hour and 20 minutes to fly to Chicago would leave a total flying time of 5 hours and 10 minutes.

Flying from Montreal to Tokyo to get to Mexico City is possible but hardly efficient. Because the relationship between Montreal and Tokyo shows a 13 hour 30 minute flight, over twice as long as the Montreal to Chicago to Mexico City route, you can safely stop following other routes from Tokyo to Mexico City. From Chicago, you could fly to Portland, but like Boston, this does not lead to a direct flight to Mexico City. Finally, a direct flight from Montreal to Mexico City would take 5 hours, the fastest route available.

Performing this same kind of analysis in a relational database would be more involved. We could easily represent the same data shown in Figure 2.16 using a table such as the one shown in Table 2.1.

Table 2.1 Flight Times Between Cities Modeled as a Relational Table

Querying is more difficult. You would have to write multiple SQL statements or use specialized recursive statements if they are provided (for example, Oracle’s CONNECT BY clause in SELECT statements) to find paths using the table representation of the data.

Graph databases allow for more efficient querying when paths through graphs are involved. Many application areas are efficiently modeled as graphs and, in those cases, a graph database may streamline application development and minimize the amount of code you would have to write.

The most widely used types of NoSQL databases are key-value, document, column family, and graph databases. The following chapters describe each of these in depth and present examples of typical use cases for each.

Summary

NoSQL databases are often deployed using clusters of servers. When applications run on multiple servers and coordinate their work across servers, they are known as distributed systems. When you use NoSQL databases in a distributed manner, you will have to decide how to address the challenges that come with that type of implementation. Distributed systems help improve scalability and availability but make it more difficult to ensure consistency of data across servers. There are also potential problems if there is a network failure and some servers cannot send messages to other servers in the distributed database system.

The nature of distributed systems has led NoSQL database designers to choose a different set of principles for building data management systems. Rather than support atomic, consistent, isolated, and durable transactions (ACID), NoSQL databases achieve basic availability, soft state, eventually consistent (BASE). (Some NoSQL databases are working to support ACID transactions, at least in some cases.)

The four types of NoSQL databases described in this chapter all must address the challenges of distributed systems. The types of NoSQL database systems differ primarily in the basic data structures used to model data. The different data structure choices lead to different implementation details. Developers who work with NoSQL databases should understand how the nature of distributed systems could affect their applications, and they should know how to choose among NoSQL databases for their requirements. The rest of this book is dedicated to informing you about those topics.

Review Questions

1. What is a distributed system?

2. Describe a two-phase commit. Does it help ensure consistency or availability?

3. What do the C and A in the CAP theorem stand for? Give an example of how designing for one of those properties can lead to difficulties in maintaining the other.

4. The E in BASE stands for eventually consistent. What does that mean?

5. Describe monotonic write consistency. Why is it so important?

6. How many values can be stored with a single key in a key-value database?

7. What is a namespace? Why is it important in key-value databases?

8. How do document databases differ from key-value databases?

9. Describe two differences between document databases and relational databases.

10. Name two data structures used in column family databases.

11. What are the two fundamental data structures in a graph database?

12. You are assigned the task of building a database to model employees and who they work with in your company. The database must be able to answer queries such as how many employees does Employee A work with? And, does Employee A work with anyone who works with Employee B? Which type of NoSQL database would naturally fit with these requirements?

References

Brewer, Eric. “CAP Twelve Years Later: How the ‘Rules’ Have Changed.” Computer vol. 45, no. 2 (Feb 2012): 23–29

Chodorow, Kristina. MongoDB: The Definitive Guide. Sebastopol, CA: O’Reilly Media, Inc., 2013.

Hewitt, Eben. Cassandra: The Definitive Guide. Sebastopol, CA: O’Reilly Media, Inc., 2010.

Robinson, Ian, Jim Webber, and Emil Eifrem. Graph Databases. Sebastopol, CA: O’Reilly Media, Inc., 2013.

Vogel, Werner. 2008. “Eventually Consistent—Revisited” (December). http://www.allthingsdistributed.com/2008/12/eventually_consistent.html

Bibliography

Hernandez, Michael J. Data Design for Mere Mortals: A Hands-On Guide to Relational Database Design. Reading, MA: Addison-Wesley, 2007.

Viescas, John L., and Michael J. Hernandez. SQL Queries for Mere Mortals. Reading, MA: Addison-Wesley, 2007.