I'm reading an article about indexing in Redis. There is a link to so-called Hexastore, it's referred to as a data structure. The link doesn't work, which makes me feel I'm missing something.

I understand from the article that

the hexastore provides a representation for relations between objects, formed by a subject, a predicate and an object. A simple relation between objects could be

antirez is-friend-of matteocollina

What are the key use cases of Hexastore as a data structure? Which indexing problems can it solve along with the quoted example above? How does it work?

There is a paper about Hexastore on the internet, which has a long explanation. Could anybody put it in a nutshell?


1 Answer 1


I only skimmed the paper for 10 seconds, but AFAICS, the fundamental idea (and the reason why it is called the Hexastore) is that the relationship triple (Subject, Relationship, Object) is stored in all 6 of its permutations separately:

  1. (Subject, Relationship, Object)
  2. (Subject, Object, Relationship)
  3. (Object, Relationship, Subject)
  4. (Object, Subject, Relationship)
  5. (Relationship, Subject, Object)
  6. (Relationship, Object, Subject)

Now, you can ask any question you want and the answers will only require a prefix search on the index.

Want to know about any relationship between Anna and Billy? Search for (A, B) or (B, A) (order doesn't matter since both are stored). Want to know all of Anna's Friends? Search for (A, f). Want to know about all married couples? Search for (m) and throw away every odd result. And so on.

Whether you are trying to find relationships between two fixed persons, finding a person that a fixed person has a fixed relationship with, finding all pairs of persons that have a particular relationship, finding all relationships a particular person has with anybody, all of that is fast because all of that is just an index search.

The paper does not actually store all six of those in the same index, rather they use six indices. (Whereas I believe the Redis article suggests to use a single index.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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