So, we've seen where databases come from, observed and practiced with many of the traditional concepts
of the relational database model, and talked at length about issues that are both specific to that
model and generalizable to ALL databases and DBMS's. Now it's time to move on to the next level and
begin to look at the new wave
of database engines, known as NoSQL
databases.
NoSQL started out as a sort of rebellion against the idea of relational databases with all their associated complexity and trappings and pitfalls. Starting way back in 1998, the original NoSQL was actually a DBMS that was still relational in nature but eschewed the use of the SQL language. Instead, it used a stream-based set of operators to perform functions on passed data. The stream was supplied by the UNIX pipe system so that true stream-based operation was supported. There were several reasons for avoiding the use of SQL at the time:
Here are some examples so you can see where this stuff comes from and how it basically works.
[Note: this table comes from Wikipedia, under
their common license.]
| SQL | NoSQL |
|---|---|
| select col1 col2 from tablename | column col1 col2 < filename |
| where column - expression | row 'column == expression' |
| compute column = expression | compute 'column = expression' |
| group by | subtotal |
| having | row |
| order by column | sorttable column |
| unique | uniq |
| count | wc -l |
| outer join | jointable -al |
| update | delete, replace |
| nesting | pipes |
BTW, NoSQL itself is still a viable product, maintained by it's author at this location.
There are several different types of NoSQL databases, and there is some overlap between them, since they often include similar functionality, based on the way they treat their data items. Here is a brief list of some of the main types in which we will be interested, with explanations and representative examples.
The key-value store database engine uses the concept of an associative array, which is more
commonly known as a dictionary
, as its underlying data model. Data is stored as a collection or
set of key-value pairs. Each key is only allowed to appear once in any collection, making it unique to
that collection. This allows the keys to model the concept of the primary key in a relational database
table, so that any entry or data item in the collection can be independently accessed.
This model is fundamentally one of the simplest of the non-trivial data models. It can be [and has been] extended to other more complex implementations which do things like ordering the keys so that they can be accessed more efficiently, in ranges, and often without needing complex indexing schemes.
Examples of this model include InfinityDB, Oracle NoSQL, and Redis
The concept of a document store is the idea that every data item is treated as a document
, which
maintains some sort of specific encoding scheme. Typically they encapsulate the data in some
well-known and well-documented form such as JSON or BSON, XML, or YAML. Access to documents in the store
is accomplished using a unique key, which is used as a surrogate for that document. While this sounds
very like [and actually does overlap] the idea of the key-value store, a document store database has the
additional ability to use an API or a query language to retrieve documents based on their contents
instead of just the key.
There are several different ways that document store databases might organize or group the documents
they contain. Collections
can be treated as similar to relational tables, which makes the idea of
documents in the database become relational records or rows in the table, with the stipulation that the
fields in a document can be in any order; in contrast, in a relational table, the fields in all rows
all have the same order in the table. One big advantage of the document store approach is that since
the documents do not have to support a standard schema, they only store the data that is in each of the
documents, and so there is not wasted space as there can be with the relational model.
Other ways of organizing documents are using directory hierarchies, tags, or metadata.
Document stores can be thought of as collections of objects, like in object-oriented programming. As
such, they don't have to keep to a standard schema, since there are many different types of objects
and each one might have different field structures, even though they are related by some mechanism
such as inheritance. Further, since there are different types of objects, that means differences in
the encoding scheme are allowed for documents in the same store. For example, some documents in the
database might be encoded in JSON, and others in XML, and the database has no problem keeping track.
Most [if not all] document store databases also support the idea of CRUD, although some engines use
different names such as edit
instead of update
. Documents are accessed using keys that
represent them; each unique key can be a string, a path, or a URI.
Examples of this model include MongoDB, CouchDB, and PostGreSQL using its HStore facility.
A graph database uses computer science graph structures as the underlying concept for semantic queries, with nodes, edges, and other similar properties of graphs being used to store and retrieve the data. Graph databases are designed for data whose elements can be interconnected, such as networks [social or otherwise], map locations, historical events, and many other linked types. They are based on the ideas of graph theory.
Different graph databases may use differing structures to actually store and maintain the data. In
some cases, the graph DBMS actually uses a relational engine to store the graph in a table! Other
engines use a key-value store or document-store database for storage, making the relationship between
graph databases and these others overlap considerably. However, the data manipulation language for
graph databases must be something other than normal SQL, since that language is not designed for graph
traversals. This constraint is easily overcome by the use of API's for access. There are several
different API instances, and although some standardization has occurred, there is no single universal
method. There are also some graph query languages, which have been developed to help traverse the
graph data in an elegant
manner.
Graph databases store each record as a node. Nodes are linked together by edges.
Nodes and edges can have
Another feature of the graph approach is the speed with which this method can find multi-level data. For example, finding all the subscribers to Time Warner Cable who live in the zip code area 90245 is done by finding the record for the zip code, then back-tracking from that node to locate the nodes with pointers to that node. Contrast that with a relational method, in which all the people that are in that zip code must be retrieved and held in memory, then that temporary data must be looked through to find subscribers to TWC, and THAT temporary data [also held in memory] must be looked through to determine the final result set. Apart from the memory storage requirements and the latency of having to manage [potentially] multiple joins, the time complexity of such a relational search would be Big-Oh(log(n)) *for each lookup* in the relational case, while in the graph case a single constant time lookup would be followed by a single Big-Oh(log(n)) lookup.
Graph databases are also very good at managing indefinite queries, such as who was the bass player
for the Shadows of Knight that also played on an album in 1972 with Ian Anderson of Jethro Tull?
because the information is contained in nodes and edges and they include the ability to backtrack.
Remember that a node is an entity, and as such is roughly equivalent to a record or a row [or perhaps a relation] in a relational database. Edges are similar to relationships between entities, but really don't have a one-to-one relationship with any part of a relational database. They are where the graph database gets much of its power and flexibility. They allow meaningful patterns to emerge between the nodes. Finally, remember that a property is something that is information that relates to a node [or sometimes an edge], similar to how objects in JavaScript have properties. For example, if a node had information for a movie, there might be properties for title, leading actor, leading actress, MPAA rating, director, producer, and release date, depending upon what the database needs to track.
Examples of graph databases include Neo4j and OrientDB.
We will look at three of these: Mongo, Neo4J, and Redis.
As we've seen, MongoDB is an example of a document-store database.