Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A fast, minimal JS triple store implementation in ~70 lines of code
// three indices to efficiently support all lookups
function createDB() {
return {eav: new Map(),
ave: new Map(),
vea: new Map()};
}
function addToIndex(xs, x, y, z, triple) {
let ys = xs.get(x);
if(ys == undefined) {
ys = new Map();
xs.set(x, ys);
}
let zs = ys.get(y);
if(zs == undefined) {
zs = new Map();
ys.set(y, zs);
}
zs.set(z, triple);
}
function removeFromIndex(table, x, y, z) {
table.get(x)?.get(y)?.delete(z);
}
// always called with at least x
function lookupInIndex(index, x, y, z) {
let triples = new Set();
if (y == undefined) {
index.get(x)?.forEach(function(y) {
y.forEach((z) => triples.add(z));
});
} else if (z == undefined ) {
index.get(x)?.get(y)?.forEach((z) => triples.add(z));
} else {
let triple = index.get(x)?.get(y)?.get(z);
if (triple) {
triples.add(triple);
}
}
return triples;
}
// N.B. upsert semantics!
function add(db, e, a, v) {
// index payloads are all pointers to a single frozen array, thus we
// are able to return an immutable value and JS's questionable equality
// semantics actually work properly for triples (Sets work, &c).
let triple = Object.freeze([e, a, v]);
addToIndex(db.eav, e, a, v, triple);
addToIndex(db.ave, a, v, e, triple);
addToIndex(db.vea, v, e, a, triple);
}
function remove(db, e, a, v) {
removeFromIndex(db.eav, e, a, v);
removeFromIndex(db.ave, a, v, e);
removeFromIndex(db.vea, v, e, a);
}
function get(db, e, a, v) {
if(e != undefined) {
if(a == undefined && v != undefined) {
return lookupInIndex(db.vea, v, e); // e, null, v
}
return lookupInIndex(db.eav, e, a, v); // e, null, null / e, a, null / e, a, v
} else if(a != undefined) {
return lookupInIndex(db.ave, a, v); // null, a, null / null, a, v
} else if (v != undefined) {
return lookupInIndex(db.vea, v); // null, null, v
}
throw 'get() requires at least one of {e,a,v}!';
}
////////////////////////////////////////////////////////////////////////////////
// testing
test_data = [[1, ":username", "arslonga"],
[1, ":firstname", "Alvin"],
[1, ":lastname", "Pencilpoint"],
[1, ":role", "designer"],
[1, ":group", 47],
[2, ":username", "l33t"],
[2, ":firstname", "Edward"],
[2, ":lastname", "Bughands"],
[2, ":role", "developer"],
[2, ":workgroup", 47],
[3, ":username", "baker"],
[3, ":firstname", "Pippin"],
[3, ":lastname", "Apfelbrot"],
[3, ":role", "designer"],
[3, ":role", "developer"],
[3, ":workgroup", 23]];
function addTestData(db) {
test_data.forEach((triple) => add(db, triple[0], triple[1], triple[2]));
}
test_db = createDB();
addTestData(test_db);
console.log(
JSON.stringify(
Array.from(
get(test_db, 1,null,null)
// get(null,":lastname",null)
// get(null,null,"Bughands")
// get(null,":firstname","Alvin")
// get(3,":role",null)
// get(3,null,"Pippin")
// get(2, ":workgroup", 47)
// get(null,null,null)
)
));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment