<div dir="ltr"><div class="gmail_quote"><div dir="ltr">On Mon, Sep 25, 2017 at 9:16 PM Grzegorz Junka <<a href="mailto:list1@gjunka.com">list1@gjunka.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div text="#000000" bgcolor="#FFFFFF"><br></div><div text="#000000" bgcolor="#FFFFFF">
    gb_tree would not prevent from having to store the key twice (once
    as the key for gb_tree and once as the value). Not sure why you
    mention gb_tree here?</div><div text="#000000" bgcolor="#FFFFFF"><br></div></blockquote><div><br></div><div>The reason I mention this is because if we have:</div><div><br></div><div>Key = T, % for some arbitrary term T</div><div>Id = Horizon, % for some horizon value</div><div>Tree2 = gb_trees:enter(Key, Id, Tree1),</div><div>Tree3 = gb_trees:enter(Id, Key, Tree2),</div><div><br></div><div>then the `Key` is immutable and thus shared. It will in practice be of pointer size (4-8 bytes). This only holds if you are in a gb_trees setting because if we start going to ETS for this, then we obviously might lose the sharing. Perhaps it does work if you insert multiple entries at once.</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div text="#000000" bgcolor="#FFFFFF">That's the whole point. How would you implement an RDF/triple
    database in Erlang? :)<br>
    <br></div></blockquote><div><br></div><div>The obvious candidate to beat is Postgres with an appropriately designed table structure and indexes. If we can't beat this, we are not even in game. It is also fairly easy to write, so first, we should use that as a baseline implementation.</div><div><br></div><div>If our RDF store is fairly small and can fit in memory, I'd probably just store one ETS table doing a bidrectional ID<->Key mapping as above. And then, depending on query needs store those ID's as {{spo, Subject, Predicate}, Object} or such in ETS. This should allow fairly efficient query, as most of the data resides in memory and lookup is going to be fast. Some data waste is expected in these solutions. It might be beneficial to just ignore the ID mapping for a start and do it naively. This also establishes a model which can be run in unison with other models via QuickCheck so we can check for agreement with a simpler model.</div><div><br></div><div>Going to billions of RDF triples will break the above scheme. I'd probably do like the Cayley datastore in Go: store data in eleveldb and steal the Cayley-format. In this format you store everything in one leveldb database where different parts of the storage are mapped by different prefixes (IDs are <<"z", SHA1:160/integer>> for instance. To run fast SPO, OSP, POS ... indexed hashes are stored for these mappings as well. In addition a horizon and history is tracked for each quad so we can answer a query in the past faithfully if needed. Sharding/Batching might come in handy here at a later point.</div><div><br></div><div>Leveled trees such as the one leveldb uses tend to be quite efficient compared to B+-trees in many situations. It might be in this case too. Because Cayley uses unique SHA1 hashes for data, we obtain that keys with the same subject will be iterable because they will have the same prefix in that part of the data store. We essentially pay with writes up-front to make the lookups faster. Also note that leveldb will naturally keep often used data in memory if tuned.</div><div><br></div><div>TL;DR: either data fits in memory or it doesn't :P</div><div><br></div></div></div>