Query Engine Core

Home · Reasoning · Symbolic · Holographic Finding answers to questions with variable bindings

The Query Engine extends proof search to handle open queries – questions with variables that seek multiple answers. Unlike proof (yes/no), queries return sets of bindings that satisfy the goal.

1. Theoretical Foundation

Proof vs Query:

prove(isA Socrates Mortal) → { success: true }
query(isA ?x Mortal) → [{ ?x: Socrates }, { ?x: Plato }, ...]

A proof determines if a ground goal is derivable. A query finds all instantiations of variables that make the goal derivable.

Formal Definition:

query(G[?x₁, ..., ?xₙ], KB) = { θ | KB ⊢ G·θ }

Where θ is a substitution mapping variables to constants, and G·θ is the goal with substitution applied.

2. Query Processing Pipeline

Query Processing Pipeline Parse Extract variables HDC Filter Find candidates Match Unify patterns Chain Apply rules Collect Aggregate results [ ] isA ?x Animal ~500 candidates Direct: 12 Inferred: 45 Unique: 57 Typical query: 57 results from KB with 10,000 facts

3. Query Modes

Mode Description Example
Single Variable Find all X where P(X) holds isA ?x Animal
Multi-Variable Find all (X,Y) pairs where R(X,Y) holds loves ?x ?y
Constrained Find X with constraints And (isA ?x Animal) (livesIn ?x Africa)
Existential Check if any solution exists exists ?x (isA ?x Dragon)
Counting Count solutions count ?x (isA ?x City)

4. Algorithm: Query Evaluation

Algorithm: query(goal, kb)
  1. Extract variables: vars = findVariables(goal)
  2. Initialize: results = []
  3. HDC pre-filter: If goal has constants, use HDC similarity to find candidate facts
  4. Direct matching:
    • For each fact F in KB (or candidates):
    • θ = unify(goal, F)
    • If θ ≠ FAIL: results.push(θ)
  5. Rule chaining:
    • For each rule R: (premises → consequent)
    • θ = unify(goal, consequent)
    • If θ ≠ FAIL:
    •   premise_bindings = query(premises·θ, kb)
    •   results.extend(compose(θ, premise_bindings))
  6. Deduplicate: Remove equivalent bindings
  7. Return: results with confidence scores

5. Compound Query Handling

And (Conjunction): 
query(And(P, Q)) =
  for θ in query(P):
    for φ in query(Q·θ):
      yield compose(θ, φ)

Bindings from P are used to instantiate Q before querying.

Or (Disjunction): 
query(Or(P, Q)) = query(P) ∪ query(Q)

Results from both branches are merged (with deduplication).

Not (Negation): 
query(And(P, Not(Q))) =
  for θ in query(P):
    if query(Q·θ) is empty:
      yield θ

Keep only bindings where the negated condition has no solutions.

6. Variable Binding Flow

Variable Binding Flow Query And (isA ?x Animal) (eats ?x ?y) isA ?x Animal → [Cat, Dog, Lion] ?x = Cat ?x = Dog ?x = Lion eats Cat ?y eats Dog ?y eats Lion ?y ?x=Cat, ?y=Fish ?x=Cat, ?y=Mouse ?x=Dog, ?y=Meat ?x=Dog, ?y=Bone ?x=Lion, ?y=Zebra ?x=Lion, ?y=Antelope

7. Confidence in Query Results

Each binding carries a confidence score indicating how reliably it was derived:

Result = { bindings: θ, confidence: c, method: m, trace: [...] }
Source Confidence Example
Direct KB fact 1.0 Exact match to stated fact
Transitive chain 0.95^(n-1) isA chain through hierarchy
Rule inference min(premises) × 0.95 Derived via implication rule
HDC similarity similarity score Approximate/fuzzy match

8. Query Examples

Simple Query: 
// Find all animals
query: isA ?x Animal

results: [
  { bindings: { ?x: 'Cat' }, confidence: 1.0 },
  { bindings: { ?x: 'Dog' }, confidence: 1.0 },
  { bindings: { ?x: 'Lion' }, confidence: 0.95 }  // via isA Lion Mammal, isA Mammal Animal
]
Join Query: 
// Find what African animals eat
query: And (livesIn ?x Africa) (eats ?x ?food)

results: [
  { bindings: { ?x: 'Lion', ?food: 'Zebra' }, confidence: 0.95 },
  { bindings: { ?x: 'Elephant', ?food: 'Grass' }, confidence: 1.0 }
]
Negation Query: 
// Find animals that don't fly
query: And (isA ?x Animal) (Not (canFly ?x))

results: [
  { bindings: { ?x: 'Dog' }, confidence: 1.0 },
  { bindings: { ?x: 'Cat' }, confidence: 1.0 },
  { bindings: { ?x: 'Fish' }, confidence: 1.0 }
]

9. Optimization Techniques

Technique Description Benefit
Variable ordering Process most selective subgoal first Reduces intermediate results
HDC pre-filtering Use similarity to narrow candidates Avoids scanning entire KB
Index utilization Use operator/argument indexes O(1) lookup vs O(n) scan
Early termination Stop when limit reached Bounded response time
Memoization Cache subquery results Avoids redundant computation

10. API Reference

import { QueryEngine } from 'agisystem2/reasoning';

const engine = new QueryEngine(session);

// Basic query
const results = await engine.query({
  operator: 'isA',
  args: ['?x', 'Animal']
});

// With options
const results = await engine.query(goal, {
  limit: 100,              // Max results
  minConfidence: 0.5,      // Filter weak results
  includeTrace: true,      // Include derivation
  timeout: 5000            // Max time (ms)
});

// Compound query
const results = await engine.query({
  operator: 'And',
  args: [
    { operator: 'isA', args: ['?x', 'Person'] },
    { operator: 'livesIn', args: ['?x', 'Paris'] }
  ]
});

11. Related Documentation

← Back to Reasoning Engines