Lecture
NoSQL (from «not only SQL») is a designation for a broad class of diverse database management systems that emerged in the late 2000s and early 2010s, differing substantially from traditional relational DBMSs that use SQL for data access. It applies to systems that attempt to solve scalability and availability problems by fully or partially abandoning the requirements of data atomicity and consistency.
NoSQL (originally referring to «non-SQL» or «non-relational») database provides a mechanism for storing and retrieving data that is modeled in ways other than the tabular relations used in relational database tools. Such databases have existed since the late 1960s, but the name «NoSQL» was only coined at the beginning of the 21st century , driven by the needs of Web 2.0 companies. NoSQL databases are increasingly used in big data and real-time web applications. NoSQL systems are also sometimes called «Not only SQL» to emphasize that they may support SQL-like query languages or sit alongside SQL databases in polyglot-persistence architectures.
Motivations for this approach include: simplicity of design, simpler «horizontal» scaling to clusters of machines (which is a problem for relational databases), finer control over availability, and limiting the object-relational impedance mismatch. The data structures used by NoSQL databases (for example, key-value pairs, wide columns, graphs, or documents) differ from those used by default in relational databases, which speeds up certain operations in NoSQL. The specific suitability of a given NoSQL database depends on the problem it is meant to solve. Sometimes the data structures used by NoSQL databases are also viewed as «more flexible» than the tables of relational databases.
Many NoSQL stores compromise on consistency (in the sense of the CAP theorem) in favor of availability, partition tolerance, and speed. Barriers to wider adoption of NoSQL stores include the use of low-level query languages (instead of SQL), the inability to perform ad hoc joins across tables, the lack of standardized interfaces, and the substantial prior investment already made in existing relational databases. [10] Most NoSQL stores lack true ACID transactions, although some databases have made them central to their design.
Instead, most NoSQL databases offer the concept of «eventual consistency», in which database changes propagate to all nodes «eventually» (typically within milliseconds), so queries for data may not immediately return updated data, or may result in reading data that is inaccurate — a problem known as stale reads. In addition, some NoSQL systems may exhibit write losses and other forms of data loss. Some NoSQL systems provide concepts such as write-ahead logging to avoid data loss. For distributed transaction processing across multiple databases, data consistency is an even bigger problem, one that is difficult for both NoSQL and relational databases alike. Relational databases «do not allow referential integrity constraints to span databases». Few systems support both ACID transactions and the X/Open XA standards for distributed transaction processing. Interactive relational databases share common approaches to conformational relay analysis. Constraints in the front-end environment are overcome through semantic virtualization protocols, so that NoSQL services are available on most operating systems.
Originally, the word NoSQL was an acronym of two English words: No and SQL (short for Structured Query Language), giving the term the meaning «rejecting SQL». It is possible that the first people to use the term meant «No RDBMS» or «no relational», but NoSQL sounded better and eventually stuck (NonRel was also proposed as an alternative). Later, an explanation was invented for NoSQL: «Not Only SQL». NoSQL became a general term for a variety of databases and stores, but it does not denote any single specific technology or product .
The idea of non-relational databases is not new in itself, and the use of non-relational stores began back in the days of the first computers. Non-relational databases flourished in the mainframe era, and later, during the era when relational DBMSs dominated, found application in specialized stores, such as hierarchical directory services. The emergence of a new generation of non-relational DBMSs came about because of the need to build parallel distributed systems for highly scalable internet applications such as search engines .
In the early 2000s, Google built its highly scalable search engine and applications: GMail, Google Maps, Google Earth, and others, solving problems of scalability and parallel processing of large volumes of data. This resulted in the creation of a distributed file system and a distributed coordination system, a column-family store, and a runtime environment based on the MapReduce algorithm. Google's publication of descriptions of these technologies led to a surge of interest among open-source developers, resulting in the creation of Hadoop and related projects aimed at building Google-like technologies. A year later, in 2007, Amazon.com followed Google's example by publishing papers on the highly available Amazon DynamoDB database .
Support from industry giants led, in less than five years, to widespread adoption of NoSQL (and similar) technologies for managing «big data», with other large and small companies joining in, such as IBM, Facebook, Netflix, eBay, Hulu, and Yahoo!, each with their own proprietary and open-source solutions .
Traditional DBMSs are oriented toward the ACID requirements for a transactional system: atomicity, consistency, isolation, durability, whereas in NoSQL a set of BASE properties may be considered instead of ACID :
The term «BASE» was proposed by Eric Brewer, the author of the CAP theorem, according to which, in distributed computing, only two of three properties can be guaranteed: data consistency, availability, or partition tolerance .
Of course, BASE-based systems cannot be used in every application: for the operation of stock exchange and banking systems, the use of transactions is a necessity. At the same time, ACID properties, however desirable, are practically impossible to guarantee in systems with a multi-million-strong web audience, such as amazon.com . Thus, designers of NoSQL systems sacrifice data consistency in order to achieve the other two properties from the CAP theorem . Some DBMSs, such as Riak, allow the required availability-consistency characteristics to be configured even for individual queries by specifying the number of nodes required to confirm the success of a transaction.
NoSQL solutions differ not only in their design for scaling. Other characteristic features of NoSQL solutions include :
The description of a data schema when using NoSQL solutions can be carried out through the use of various data structures: hash tables, trees, and others.
Depending on the data model and approaches to distribution and replication, four main types of systems are distinguished within the NoSQL movement: key-value stores, document-oriented stores, column-family stores, and graph databases.
The key-value model is the simplest option, using a key to access a value. Such systems are used for storing images, building specialized file systems, as caches for objects, and in systems designed with scalability in mind. Examples of such stores include Berkeley DB, MemcacheDB[en], Redis, Riak, and Amazon DynamoDB .
Another type of system is the «column family» type, the progenitor of which is Google BigTable. In such systems, data is stored as a sparse matrix, whose rows and columns are used as keys. A typical application of this type of DBMS is web indexing, as well as big-data tasks with reduced consistency requirements. Examples of DBMSs of this type include Apache HBase, Apache Cassandra, ScyllaDB[en], Apache Accumulo , and Hypertable
Column-family systems and document-oriented systems have similar use cases: content management systems, blogs, and event logging. The use of timestamps makes it possible to use this type of system to organize counters, as well as to log and process various time-related data .
Unlike column-oriented storage, used in some relational DBMSs that store data by columns in compressed form for efficiency in OLAP scenarios, the column-family model stores data row by row and provides high performance primarily in operational scenarios, whereas for queries that require scanning large volumes of data with result aggregation, it is generally inefficient .
Document-oriented DBMSs serve to store hierarchical data structures. They are used in content management systems, publishing, and document search. Examples of DBMSs of this type include CouchDB, Couchbase, MongoDB, eXist, and Berkeley DB XML .
Graph DBMSs are used for tasks in which data has a large number of relationships, such as social networks and fraud detection. Examples: Neo4j, OrientDB, AllegroGraph[en], Blazegraph[10], InfiniteGraph, FlockDB, Titan .
Since graph edges are materialized, i.e., stored, traversing the graph does not require additional computation (as a join in SQL would), but finding the starting vertex for a traversal requires the presence of indexes. Graph DBMSs typically support ACID, and also support specialized query languages such as Gremlin, Cypher, SPARQL, and GraphQL[en].
In July 2011, Couchbase, the developer of CouchDB, Memcached, and Membase, announced the creation of a new SQL-like query language — UnQL (Unstructured Data Query Language). The work of creating the new language was carried out by SQLite's creator, Richard Hipp, and the founder of the CouchDB project, Damien Katz. Development was handed over to the community as public domain.
The term NoSQL was used by Carlo Strozzi in 1998 to refer to his lightweight open-source relational database, Strozzi NoSQL, which did not provide a standard Structured Query Language (SQL) interface but nonetheless remained relational. [18] His NoSQL DBMS differs from the general concept of NoSQL databases from 2009. Strozzi suggests that, since the current NoSQL movement «departs entirely from the relational model, it would be more appropriately called «NoREL»» [19], meaning «non-relational».
Johan Oskarsson, a Last.fm developer at the time, reintroduced the term NoSQL in early 2009, when he organized an event to discuss «distributed, open-source, non-relational databases». [20] The name was an attempt to denote the emergence of a growing number of non-relational distributed data stores, including Google's Bigtable/MapReduce clones and Amazon's DynamoDB.
There are various ways of classifying NoSQL databases, with different categories and subcategories, some of which partially overlap. Below is a basic classification by data model with examples:
Below is a more detailed classification based on a proposal by Stephen Yen: [21] [22]
| Type | Notable examples of this type |
|---|---|
| Key-value cache | Apache Ignite, Couchbase, Coherence, eXtreme Scale, Hazelcast, Infinispan, Memcached, Redis, Velocity |
| Key-value store | Azure Cosmos DB, ArangoDB, Aerospike, Couchbase, Redis |
| Key-value store (eventually consistent) | Azure Cosmos DB, Oracle NoSQL Database, Dynamo, Riak, Voldemort |
| Key-value store (ordered) | FoundationDB, InfinityDB, LMDB, MemcacheDB |
| Tuple store | Apache River, GigaSpaces |
| Object database | Objectivity/DB, Perst, ZopeDB |
| Document store | Azure Cosmos DB, ArangoDB, BaseX, Clusterpoint, Couchbase, CouchDB, DocumentDB, eXist-db, IBM Domino, MarkLogic, MongoDB, Qizx, RethinkDB, Elasticsearch |
| Wide column store | Azure Cosmos DB, Amazon DynamoDB, Bigtable, Cassandra, Google Cloud Datastore, HBase, Hypertable, Scylla |
| Native multi-model database | ArangoDB, Azure Cosmos DB, OrientDB, MarkLogic |
Correlation databases are model-independent and, instead of row- or column-based storage, use value-based storage.
Key-value (KV) stores use an associative array (also called a map or dictionary) as their fundamental data model. In this model, data is represented as a collection of key-value pairs, such that each possible key appears in the collection at most once. [23] [24]
The key-value model is one of the simplest nontrivial data models, and more extensive data models are often implemented as extensions of it. The key-value model can be extended into a discretely ordered model that supports keys in lexicographic order. This extension is computationally powerful, since it can efficiently retrieve selective ranges of keys. [25]
Key-value stores may use consistency models ranging from eventual consistency to serializability. Some databases support key ordering. Various hardware implementations exist, with some users storing data in memory (RAM), and others on solid-state drives (SSDs) or rotating disks (also known as hard disk drives (HDDs)).
The central concept of a document store is the concept of a «document». Although the details of this definition vary across document-oriented databases, they all assume that documents encapsulate and encode data (or information) in some standard formats or encodings. Encodings used include XML, YAML, and JSON, as well as binary forms such as BSON. Documents are addressed in the database via a unique key that represents that document. Another defining characteristic of a document-oriented database is an API or query language for retrieving documents based on their content.
Different implementations offer different ways of organizing and/or grouping documents:
Compared to relational databases, collections can be considered analogous to tables, and documents analogous to records. But they are different: every record in a table has the same sequence of fields, while documents in a collection can have completely different fields.
Graph databases are designed for data whose relationships are well represented as a graph consisting of elements connected by a finite number of relations. Examples of such data include social relationships, public transit routes, road maps, and network topologies.
Graph databases and their query languages
| Name | Language(s) | Notes |
|---|---|---|
| AllegroGraph | SPARQL | RDF triple store |
| Amazon Neptune | Gremlin, SPARQL | Graph database |
| ArangoDB | AQL, JavaScript, GraphQL | Multi-model document database, graph database, and key-value store |
| Azure Cosmos DB | Gremlin | Graph database |
| DEX / Sparksee | C++, Java, C#, Python | Graph database |
| FlockDB | Scala | Graph database |
| IBM DB2 | SPARQL | DB2 10 added an RDF triple store |
| InfiniteGraph | Java | Graph database |
| MarkLogic | Java, JavaScript, SPARQL, XQuery | Multi-model document database and RDF triple store |
| Neo4j | Cypher | Graph database |
| OpenLink Virtuoso | C++, C#, Java, SPARQL | Hybrid middleware and DBMS core |
| Oracle | SPARQL 1.1 | RDF triple store added in 11g |
| OrientDB | Java, SQL | Multi-model document and graph database |
| OWLIM | Java, SPARQL 1.1 | RDF triple store |
| Profium Sense | Java, SPARQL | RDF triple store |
| Sqrrl Enterprise | Java | Graph database |
Ben Scofield rated various categories of NoSQL databases as follows: [28]
| Data model | Performance | Scalability | Flexibility | Complexity | Functionality |
|---|---|---|---|---|---|
| Key-value store | high | high | high | none | variable (none) |
| Column store | high | high | moderate | low | minimal |
| Document-oriented store | high | variable (high) | high | low | variable (low) |
| Graph database | Variable | Variable | high | high | graph theory |
| Relational database | Variable | Variable | low | moderate | relational algebra |
Performance and scalability comparisons are sometimes carried out using the YCSB benchmark.
Because most NoSQL databases lack the ability to perform joins in queries, the database schema usually needs to be designed differently. There are three main methods for handling relational data in a NoSQL database. (See the table on join and ACID support for NoSQL databases that support joins.)
Instead of retrieving all the data with a single query, several queries are typically executed to obtain the desired data. NoSQL queries are often faster than traditional SQL queries, so the cost of the extra queries may be acceptable. If an excessive number of queries is required, one of the other two approaches would be more suitable.
Instead of storing only foreign keys, the actual foreign values are typically stored alongside the model's data. For example, each blog comment might include the username in addition to the user ID, providing easy access to the username without needing to look it up again. However, when the username changes, it will need to be updated in many places in the database. Thus, this approach works better when read operations are performed much more often than writes.
In document databases such as MongoDB, more data is typically placed into fewer collections. For example, in a blogging application, one might choose to store comments within the blog post document, so that all comments can be retrieved in a single fetch. Thus, with this approach, a single document contains all the data needed for a particular task.
A database is labeled as supporting ACID properties (atomicity, consistency, isolation, durability) or join operations if such a claim is made in the database's documentation. However, this does not necessarily mean that the capability is fully supported in a manner similar to most SQL databases.
| Database | ACID | Joins |
|---|---|---|
| Aerospike | yes | No |
| Apache Ignite | yes | yes |
| ArangoDB | yes | yes |
| Couchbase | yes | yes |
| CouchDB | yes | yes |
| Db2 | yes | yes |
| InfinityDB | yes | No |
| LMDB | yes | No |
| MarkLogic | yes | Yes [nb 1] |
| MongoDB | yes | Yes [nb 2] |
| OrientDB | yes | Yes [nb 3] |
Comments