1
$\begingroup$

There seems to be two approaches to store data in NoSQL databases:

Key-Value - The Key is usually stored in a hash-table referencing a Value, or Object, which can be either a key (with specific semantic) or any arbitrary data. Examples are Riak, Redis, Dynamo, CouchDB...

Subject-Predicate-Object - Subject and Predicate are interpreted as keys and Object can be either a key or an arbitrary data. This will cover not only all RDF stores, but also graph databases. Examples are Neo4j, Virtuoso, AllegroGraph...

Now I am not that interested in exact definition and which database falls into which category. We know that there are plenty of RDF triple stores implemented on top of SQL databases, as well as that any SQL database can be represented using only RDF triples. And there are other database types too, like column and document databases.

I am interested in finding out which representation is more fundamental in the sense that for example for a given processor assembler is more fundamental than C (because C is written in assembler) and C is more fundamental than Erlang (because Erlang is written in C), and so on. Or also that binary representation is more fundamental than any other (octet, decimal, hexadecimal) because it uses the smallest amount of different numbers (0 and 1). Unfortunately I don't have a strict definition of what more fundamental means exactly.

In other words, if we assume the following:

  • A Key is an IRI resource (globally unique identifier, like used in RDF)
  • A Blob is some arbitrary binary data we can't interpret

Then we can define the following two database types:

  1. Key-Value: Where Key is an IRI and Value is either an IRI or a Blob
  2. Subject-Predicate-Object: Where Subject, Predicate are IRIs, and Object is either an IRI or a Blob

In particular, those would be the fundamental data types stored in those two databases:

Ad 1: Key-Key, Key-Blob

Ad 2: Key-Key-Key, Key-Key-Blob

I have no doubt that any data stored in any database type (graph, column, table, key-value, triple, etc) can be represented in either of those databases. I have also no doubt that data stored in one of those databases can be represented in the other, for example let's assume to represent a Key-Value pair as {Key, Value} and Subject-Predicate-Object as {Subject, Predicate, Object}. Then:

Example 1:

{1, "abc"} can be represented as two triples {2, 3, 1}, {4, 3, "abc"} where 2 means Key, 3 means Stores or Holds, 4 means Value.

Example 2:

{1, 2, "abc"} can be represented as three tuples {1, 1}, {1, 2}, {1, "abc"} where Key = 1 means triple number 1, Value = 1 means Subject position, Value = 2 means Predicate position, Value = 3 means Object position.

The means is a conceptual shortcut for having a proper IRI representing that meaning.

Is there any scientific evidence that one representation is more fundamental than the other? Or, because there is no strict definition of "more fundamental", if we could put it as which representation can more easily and/or efficiently represent data stored in any other database type? And I am asking that because I hope that there isn't just an answer like "it depends" :)

$\endgroup$
1
$\begingroup$

Following your simplicity argument (binary is more fundamental than octal), I'd say that key-value stores are more fundamental. I think that Subject-Predicate is essentially a 'compound' or 'aggregate' key, so a subject-predicate-object store is a key-value store with additional requirements on the key (namely that it can be split into two).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yeah, that's my feeling as well, but I would love if you could back up your answer with some evidence (as proposed in my question). Otherwise is just an opinion. Consider that it's much easier to describe real-world relationships with S-P-O rather than K-V. For example {Car, next_to, Shop}, {London, capitol, UK}, {Bus, color, Red}. Describing those as Key-Value pairs can be done, of course, but is more awkward and difficult to process. Binary representation is the most basic/fundamental in computers because it's easiest for them to process, but would that hold true for K-V over S-P-O? $\endgroup$ – Greg Apr 3 '16 at 14:15
  • 1
    $\begingroup$ As you said, above, it probably boils down to the definition of 'fundamental'. I'm not aware that such definition exists, but I think 'simplicity' is commonly recognized feature of 'fundamental'. I don't think the ability of efficiency is relevant. For example, turing machines are considered fundamental, because of their simplicity, even though they are inefficient, even for computers. $\endgroup$ – TilmannZ Apr 3 '16 at 16:17
  • $\begingroup$ On the other hand, binary representation is fundamental and is widely used. Also assembler or RISC/CISC set of instructions as a programming language are widely used. Turing machine is a model, a hypothetical machine, not something that could be build and used. But both K-V and S-P-O are also practically used. Maybe my question should be worded if there is any fundamental data relationship representation? Even hypothetical one? $\endgroup$ – Greg Apr 3 '16 at 17:36
  • $\begingroup$ I'd say that key->value is fundamental (axiomic?). S-P-O can be expressed as a combined key-value, or as concatenation: s->(set of predicates) followed by predicate->O. But I'd also say that K-V/S-P-O are more than just data relationships. As a database person, for me it also implies efficient look-up with keys (subject/predicates), usually by an index on the key. $\endgroup$ – TilmannZ Apr 4 '16 at 8:30
  • $\begingroup$ I didn't think about the recurring definition of SPO as KVs, that's good enough for me. Thanks! $\endgroup$ – Greg Apr 4 '16 at 10:01
1
$\begingroup$

The choice here is really about what semantics are exposed to the fetch/store process, and are not really about the object representation. By giving syntactic structure to the identifier (key / address / this goes by many names) of the object, the fetch and store may have some useful characteristics. This includes:

  • Fetch with partial identity information (bulk/pattern fetch)
  • Optimised fetch/store possible with locality

Outside semantics useful to the fetch/store process, though, semantic structure in the data from the application is typically far more complex than either of these identity patterns. These are just syntactic flattenings of that more intricate structure for systems that don't need to take dependencies on that structure (and so have more reuse).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ We could formalize it a bit, i.e. having a set of n representative data objects defined and stored in both we are interested in the process of looking up a definition of a specific object, a range of objects, and a range of objects sorted by a specific characteristics. We could also limit the amount of stored objects to be non-trivial but small so that the data structure used to store them doesn't skew the outcome, e.g. 1000 objects. Then the choice isn't really about semantics but other factors, like amount of code needed or performance or else, which will depend on the object representation. $\endgroup$ – Greg Apr 3 '16 at 23:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.