JavaScript: querying facts stored as triples
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.
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");