tinylog.js

const _ = new Proxy({}, {get: (target, prop) => Symbol.for(prop)});
const isVar = x => typeof x === "symbol" && x.description !== "_";
const isBlank = x => typeof x === "symbol" && x.description === "_";

const match = (clause, fact) => {
  if (clause.length !== fact.length)
    return;
  let matches = {};
  for (let i = 0; i < clause.length; i++) {
    if (isVar(clause[i])) {
      if (matches.hasOwnProperty(clause[i].description)) {
        if (matches[clause[i].description] !== fact[i]) {
          return;
        }
      }
      matches[clause[i].description] = fact[i];
    } else if (isBlank(clause[i])) { 
      continue;
    } else if (clause[i] !== fact[i]) {
      return;
    }
  }
  return matches;
};

class Relation {
  constructor(vars) {
    this.vars = new Set(vars);
    this.rels = {};
  }
  add(rel) {
    this.rels[JSON.stringify([...this.vars].map(k => rel[k]))] = rel;
    return this;
  }
  [Symbol.iterator]() {
    return Object.values(this.rels)[Symbol.iterator]();
  }
}

const varNames = clause => clause.filter(isVar).map(v => v.description);

const scan = (facts, clause) => {
  const rel = new Relation(varNames(clause));
  for (const fact of facts) {
    let matched = match(clause, fact);
    if (matched) rel.add(matched);
  }
  return rel;
};

const crossJoin = (rel1, rel2) => {
  const rel3 = new Relation([...rel1.vars, ...rel2.vars]);
  for (const rx of rel1) {
    for (const ry of rel2) {
      rel3.add(Object.assign({}, rx, ry));
    }
  }
  return rel3;
};

const innerJoin = (rel1, rel2) => {
  const rel3 = new Relation([...rel1.vars, ...rel2.vars]);
  for (const rx of rel1) {
    next: for (const ry of rel2) {
      let joined = {};
      for (const k of rel3.vars) {
        if (rel1.vars.has(k) && rel2.vars.has(k) && rx[k] !== ry[k]) {
          continue next;
        }
        joined[k] = rel1.vars.has(k) ? rx[k] : ry[k];
      }
      rel3.add(joined);
    }
  }
  return rel3;
};

const intersects = (rel1, rel2) => [...rel1.vars]
      .filter(v => rel2.vars.has(v))
      .length > 0;

const join = (rel1, rel2) => intersects(rel1, rel2) ?
      innerJoin(rel1, rel2) :
      crossJoin(rel1, rel2);

const initRel = (use, vals) => new Relation(varNames(use))
      .add(Object.fromEntries(use.map((u, i) => [u.description, vals[i]])));

const select = (rel, vars) => [...rel]
      .map(rx => Object.fromEntries(vars.map(v => [v, rx[v]])))
      .reduce((xs, y) => xs.add(y), new Relation(vars));

const query = ({find = [], use = [], where = []}, facts, ...vals) => [...select(
  [initRel(use, vals), ...where.map(c => scan(facts, c))].reduce(join),
  varNames(find)
)];

let db = [
  ["sally", "age", 21],
  ["fred", "age", 42],
  ["ethel", "age", 42],
  ["fred", "likes", "pizza"],
  ["sally", "likes", "opera"],
  ["ethel", "likes", "sushi"]
];

const log = x => console.log(JSON.stringify(x));

log(
  query({
    find: [_.e],
    where: [[_.e, "age", 42]]
  }, db)
);
// [{"e":"fred"},{"e":"ethel"}]

log(
  query({
    find: [_.e, _.x],
    use: [_.age],
    where: [
      [_.e, "likes", _.x],
      [_.e, "age", _.age]
    ]}, db, 42) 
);
// [{"e":"fred","x":"pizza"},{"e":"ethel","x":"sushi"}]

log(
  query({
    find: [_.x],
    where: [
      [_._, "likes", _.x]
    ]}, db)
);
// [{"x":"pizza"},{"x":"opera"},{"x":"sushi"}]

log(
  query({
    find: [_.x, _.y],
    use: [_.z],
    where: [
      [_.z, "likes", _.x],
      [_.z, "age", _.y]
    ]}, db, "sally")
);
// [{"x":"opera","y":21}]

log(
  query({
    find: [_.x],
    where: [[_.x, _._, _._]]
  }, db)
);
// [{"x":"sally"},{"x":"fred"},{"x":"ethel"}]