class DatalogEngine { constructor() { this.facts = {}; this.rules = {};…
- User
class DatalogEngine { constructor() { this.facts = {}; this.rules = {}; this.resultsCache = {}; }
addFact(predicate, ...args) { if (!this.facts[predicate]) { this.facts[predicate] = []; } this.facts[predicate].push(args); }
addRule(headPredicate, headArgs, body) { if (!this.rules[headPredicate]) { this.rules[headPredicate] = []; } this.rules[headPredicate].push({ headArgs, body }); }
query(queryPredicate, ...queryArgs) { const cacheKey = JSON.stringify([queryPredicate, queryArgs]); if (this.resultsCache[cacheKey]) { return this.resultsCache[cacheKey]; }
let results = []; // Check if there are direct facts matching the query const facts = this.facts[queryPredicate] || []; for (let factArgs of facts) { const substitution = this.unify(queryArgs, factArgs); if (substitution) { results.push(this.applySubstitution(substitution, queryArgs)); } } // Apply rules iteratively until no more changes let changed = true; while (changed) { changed = false; // Use a stack to process rules const ruleStack = [...(this.rules[queryPredicate] || [])]; while (ruleStack.length) { const { headArgs, body } = ruleStack.pop(); for (let substitution of this.evaluateRule(body, {})) { // Apply the substitution to the head arguments of the rule const newResult = this.applySubstitution(substitution, headArgs); // If the result matches the query args (after applying the substitution), add it to the results if (this.unify(queryArgs, newResult)) { if ( !results.find( (result) => JSON.stringify(result) === JSON.stringify(newResult), ) ) { results.push(newResult); changed = true; } } } } } // Deduplicate results results = Array.from(new Set(results.map(JSON.stringify))).map(JSON.parse); this.resultsCache[cacheKey] = results; return results;}
unify(args1, args2, substitution = {}) { // Check if the arguments match for (let i = 0; i < args1.length; i++) { const arg1 = args1[i]; const arg2 = args2[i]; if (typeof arg1 === "string" && arg1.startsWith("?")) { // arg1 is a variable if (arg1 in substitution) { // Variable is already assigned, check if it matches with arg2 if (substitution[arg1] !== arg2) { return null; } } else { // Assign the variable substitution[arg1] = arg2; } } else if (typeof arg2 === "string" && arg2.startsWith("?")) { // arg2 is a variable if (arg2 in substitution) { // Variable is already assigned, check if it matches with arg1 if (substitution[arg2] !== arg1) { return null; } } else { // Assign the variable substitution[arg2] = arg1; } } else if (arg1 !== arg2) { // Both arguments are constants and they don't match return null; } } return substitution; }
applySubstitution(substitution, args) { return args.map((arg) => substitution[arg] || arg); }
evaluateRule(body, initialSubstitution) { if (body.length === 0) { return [initialSubstitution]; }
const [firstClause, ...restClauses] = body; const [predicate, ...clauseArgs] = firstClause; let newSubstitutions = []; // Query for the first clause in the body with the current substitution applied const substitutedArgs = this.applySubstitution( initialSubstitution, clauseArgs, ); const facts = this.facts[predicate] || []; for (let factArgs of facts) { const substitution = this.unify(substitutedArgs, factArgs, { ...initialSubstitution, }); if (substitution) { // Recursively evaluate the rest of the rule's body with the new substitution for (let sub of this.evaluateRule(restClauses, substitution)) { newSubstitutions.push(sub); } } } return newSubstitutions;} }
const datalog = new DatalogEngine();
datalog.addFact("group", "group1", "org1"); datalog.addFact("group", "group2", "org1");
// Direct membership to organization datalog.addFact("direct_member", "user1", "org1"); datalog.addFact("direct_member", "user2", "org1");
// managers / administrator datalog.addFact("manager", "user3", "group1"); datalog.addFact("administrator", "user2", "group1");
// Rules datalog.addRule( "in_group", ["?user", "?group"], [ ["direct_member", "?user", "?org"], ["group", "?group", "?org"], ], );
datalog.addRule( "admin", ["?user", "?group"], [["administrator", "?user", "?group"]], );
datalog.addRule("admin", ["?user", "?group"], [["manager", "?user", "?group"]]);
datalog.addRule( "admin", ["?user", "?group"], [ ["in_group", "?user", "?group"], ["admin", "?admin", "?group"], ], );
// Query const admins = datalog.query("admin", "?", "group1");
console.log(admins); what's the result of admins?
- Assistant
The result of the query for admins would be:
[ ["user3", "group1"], ["user2", "group1"] ] - User
let's add a rule so that user1 is an admin
- Assistant
To add a rule so that user1 is an admin, you can use the
addRulemethod of the DatalogEngine class. Here's how you can add the rule:datalog.addRule( "admin", ["user1", "group1"], [ ["direct_member", "user1", "org1"], ["group", "group1", "org1"] ] );This rule states that if "user1" is a direct member of "org1" and "group1" is a group of "org1", then "user1" is an admin of "group1".
After adding this rule, you can query for admins again to see the updated result.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.