JavaScript: querying facts stored as triples

Represent knowledge as subject–predicate–object triples and answer queries with variables.

const facts = [
  ["ada", "parentOf", "byron"],
  ["byron", "parentOf", "cy"],
  ["cy", "parentOf", "di"],
  ["ada", "type", "person"],
];

function matchPattern(pattern, fact, bindings) {
  const result = { ...bindings };
  for (let i = 0; i < 3; i++) {
    const term = pattern[i];
    if (term.startsWith("?")) {
      if (term in result && result[term] !== fact[i]) return null;
      result[term] = fact[i];
    } else if (term !== fact[i]) {
      return null;
    }
  }
  return result;
}

function query(patterns) {
  let answers = [{}];
  for (const pattern of patterns) {
    const next = [];
    for (const bindings of answers) {
      for (const fact of facts) {
        const extended = matchPattern(pattern, fact, bindings);
        if (extended) next.push(extended);
      }
    }
    answers = next;
  }
  return answers;
}

const grandparents = query([["?x", "parentOf", "?y"], ["?y", "parentOf", "?z"]]);
for (const a of grandparents) {
  console.log(a["?x"] + " is a grandparent of " + a["?z"]);
}
console.log(query([["?who", "type", "person"]]).length + " person");

ada is a grandparent of cy
byron is a grandparent of di
1 person

Explanation

A simple and flexible way to represent knowledge is as triples of subject, predicate, and object, as in the semantic web and graph databases. Ada parentOf Byron says one fact. A query is a list of patterns in which some positions are variables, written here with a leading question mark.

Answering a query means finding bindings of the variables that make every pattern match some stored fact. The program extends each partial answer with every fact that matches the next pattern and keeps those that stay consistent. The two-pattern query below defines a grandparent as a parent of a parent, a rule derived from the stored facts.

—

—

—

ada is a grandparent of cy
byron is a grandparent of di

ada is a grandparent of cy
byron is a grandparent of di
1 person

Cost and common mistakes

O(f^p) in the worst case for f facts and p patterns, much less when patterns are selective.

• Joining patterns this way compares every partial answer with every fact. Real triple stores index the facts by subject, predicate, and object.
• The closed-world assumption treats facts not in the store as false. Open-world systems treat them as unknown.

Try it yourself

How do you find all of Byron's children?

Further reading

• MDN JavaScript guide (external)
• Node.js API documentation (external)
• Artificial Intelligence: A Modern Approach (Russell, Norvig) (external)