Of the major categories of NoSQL databases - document-oriented databases, key-value stores and graph databases - we've given the least attention to graph databases on this blog. That's a shame, because as many have pointed out it may become the most significant category.

Graph databases apply graph theory to the storage of information about the relationships between entries. The relationships between people in social networks is the most obvious example. The relationships between items and attributes in recommendation engines is another. Yes, it has been noted by many that it's ironic that relational databases aren't good for storing relationship data. Adam Wiggins from Heroku has a lucid explanation of why that is here. Short version: among other things, relationship queries in RDBSes can be complex, slow and unpredictable. Since graph databases are designed for this sort of thing, the queries are more reliable.

Google has its own graph computing system called Pregel (you can find the paper on the subject here), but there are several commercial and open source graph databases available. Let's look at a few.

Sponsor

Neo4j

This is one of the most popular databases in the category, and one of the only open source options. It's the product of the company Neo Technologies, which recently moved the community edition of Neo4j from the AGPL license to the GPL license (see our coverage here). However, its enterprise edition is still proprietary. Neo4j is ACID compliant. It's Java based but has bindings for other languages, including Ruby and Python.

Neo Technologies cites several customers, though none of them are household names.

Here's a fun illustration of how relationship data in graph databases works, from an InfoQ article by Neo Technologies COO Peter Neubauer:

FlockDB

FlockDB was created by Twitter for relationship related analytics. Twitter's Kevin Weil talked about the creation of the database, along with Twitter's use of other NoSQL databses, at Strange Loop last year. You can find our coverage here.

There is no stable release of FlockDB, and there's some controversy as to whether it can be truly referred to as a graph database. In a DevWebPro article Michael Marr wrote:
The biggest difference between FlockDB and other graph databases like Neo4j and OrientDB is graph traversal. Twitter's model has no need for traversing the social graph. Instead, Twitter is only concerned about the direct edges (relationships) on a given node (account). For example, Twitter doesn't want to know who follows a person you follow. Instead, it is only interested in the people you follow. By trimming off graph traversal functions, FlockDB is able to allocate resources elsewhere.This lead MyNoSQL blogger Alex Popescu to write: "Without traversals it is only a persisted graph. But not a graph database."

However, because it's in use at one of the largest sites in the world, and because it may be simpler than other graph DBs, it's worth a look.

AllegroGraph

AllegroGraph is a graph database built around the W3C spec for the Resource Description Framework. It's designed for handling Linked Data and the Semantic Web, subjects we've written about often. It supports SPARQL, RDFS++, and Prolog.

AllegroGraph is a proprietary product of Franz Inc., which markets a number of Semantic Web products - including its flagship set of LISP-based development tools. The company claims Pfizer, Ford, Kodak, NASA and the Department of Defense among its AllegroGraph customers.

GraphDB

GraphDB is graph database built in .NET by the German company sones. sones was founded in 2007 and received a new round of funding earlier this year, said to be a "couple million" Euros. The community edition is available under an APL 2 license, while the enterprise edition is commercial and proprietary. It's available as a cloud-service through Amazon S3 or Microsoft Azure.

InfiniteGraph
InfiniteGraph is a proprietary graph database from Objectivity, the company behind the object database of the same name. Its goal is to create a graph database with "virtually unlimited scalability."

According to Gavin Clarke at The Register: "InfiniteGraph map is already being used by the CIA and Department of Defense running on top of the existing Objectivity/DB database and analysis engine."

Others

There are many more graph databases, including OrientDB, InfoGrid and HypergraphDB. Ravel is working on an open source implementation of Pregel. Microsoft is getting into the game with the Microsoft Reasearch project Trinity.

You can find more by looking at the Wikipedia entry for graph databases or NoSQLpedia.

Discuss

FLIPBOARD, AS YOU DOUBTLESS know, is a social media magazine for iPad. Part RSS reader, part iPad publication uniquely curated by each reader, the app brings serendipity, discovery, and typographic excellence to the experience of keeping up with one’s friends on Twitter, Facebook, and so on. This morning (last night in Japan), a new, improved version of Flipboard was launched, offering designers like us even more visual pleasure and rewarding the hours we put into our content’s semantic underpinnings.

Designer Craig Mod, in a letter, told me his “goal was to try and produce one of the best RSS experiences out there.” It’s accomplished via features like those listed below and more, as seen in these screenshots Craig sent me from his pre-launch tests:

auto-small caps
portrait and landscape optimized typography
full bleed images
flowing of text based on image size and location in the document
auto-generation of [figure] and [figcaption] objects based on alt
text on images

Adds Craig, “What’s great is that the more semantic and clean your feed, the better it will look in the app.”

Download Flipboard or update your copy in the iTunes Store and see.

It’s only Wednesday but we already have our link of the week. Although they call it merely a “quick write-up” (and it is a fast read), iA’s mini-compendium of design insights before and after the appearance of the iPad at their office should be required reading for all web, app, and/or interaction designers.

In the equivalent of a breathlessly quick seminar presentation, iA discusses typographic resolution and feel; the effect of the device’s brilliant contrast on readability; the kitsch produced by rigorously adhering to Apple’s “make it 3D” guidelines; whether metaphors work; and more—all of it well worth far more than the little time it will take you to absorb.

In particular, I call your attention to the section entitled, “Interaction Design: So What Works?” Although intended as a guideline to producing well-tuned iPad apps, it also works splendidly as a mini-guide to creating better websites, much like Luke Wroblewski’s brilliant “Mobile First” presentation at last week’s An Event Apart, which carried a similar message:

The limited screen estate and the limited credit on the number of physical actions needed to complete one task (don’t make me swipe and touch too often), pushes the designer to create a dead simple information architecture and an elaborate an interaction design pattern with a minimal number of actions. This goes hand in hand with the economic rule of user interaction design: Minimize input, maximize output.
Since the smallest touch point for each operation is a circle of the size of a male index finger tip, we cannot cram thousands of features (or ads!) in the tight frame; we have to focus on the essential elements. Don’t waste screen estate and user attention on processing secondary functions.
We found that the iPad applications we designed, made it relatively easy to be translated back into websites. The iPad could prove to be a wonderful blue print to design web sites and applications. If it works on the iPad, with a few tweaks, it will work on a laptop.

Via iA » Designing for iPad: Reality Check.