JavaScript: querying facts stored as triples

Before you start

JavaScript arrays, objects, and loops.

Represent knowledge as subject–predicate–object triples and answer queries with variables.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

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.

Code example

JavaScript

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");

Output

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

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1const facts = [

2 ["ada", "parentOf", "byron"],

3 ["byron", "parentOf", "cy"],

4 ["cy", "parentOf", "di"],

5 ["ada", "type", "person"],

6];

8function matchPattern(pattern, fact, bindings) {

9 const result = { ...bindings };

10 for (let i = 0; i < 3; i++) {

11 const term = pattern[i];

12 if (term.startsWith("?")) {

13 if (term in result && result[term] !== fact[i]) return null;

14 result[term] = fact[i];

15 } else if (term !== fact[i]) {

16 return null;

17 }

18 }

19 return result;

20}

22function query(patterns) {

23 let answers = [{}];

24 for (const pattern of patterns) {

25 const next = [];

26 for (const bindings of answers) {

27 for (const fact of facts) {

28 const extended = matchPattern(pattern, fact, bindings);

29 if (extended) next.push(extended);

30 }

31 }

32 answers = next;

33 }

34 return answers;

35}

37const grandparents = query([["?x", "parentOf", "?y"], ["?y", "parentOf", "?z"]]);

38for (const a of grandparents) {

39 console.log(a["?x"] + " is a grandparent of " + a["?z"]);

40}

41console.log(query([["?who", "type", "person"]]).length + " person");

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
A variable that is already bound must match the same value again.	`—`	—
Try each stored fact against the next pattern, extending the bindings that stay consistent.	`—`	—
Two patterns share ?y: the child of the first must be the parent in the second.	`x=ada,y=byron,z=cy and x=byron,y=cy,z=di`	—
Each answer binds ?x and ?z.	`x=ada,y=byron,z=cy and x=byron,y=cy,z=di`	ada is a grandparent of cy byron is a grandparent of di
A single-pattern query finds the one person fact.	`x=ada,y=byron,z=cy and x=byron,y=cy,z=di`	ada is a grandparent of cy byron is a grandparent of di 1 person

Behind the scenes

How JavaScript processes this code

A JavaScript engine parses and runs the source. A function body runs when the function is called. console.log writes to the console.

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?

Reveal answer and reasoning

Query [["byron", "parentOf", "?child"]]; it binds ?child to cy.