The QUERY Algorithm

The QUERY algorithm (Koppen & Doignon, 1990) constructs a learning space by systematically querying an expert.

Query format

Each query has the form:

If a student fails all items in \(A\), will they also fail item \(q\)?

A positive answer means: mastering \(q\) requires mastering at least one item in \(A\).

Block 1: Surmise relation discovery

Block 1 uses pair queries (\(|A| = 1\)) to discover the prerequisite relation.

Phase 0: Qmax minimality test

For each item \(q\), ask: \(Q \setminus \{q\} \to q\)?

If NO, by negative monotonicity, no subset of \(Q \setminus \{q\}\) can imply \(q\). Therefore \(q\) is minimal and all pair queries \((r, q)\) can be skipped.

Cost: \(|Q|\) group queries to potentially save \(O(|Q|^2)\) pair queries.

Phases 1–3: Pair queries with pruning

For each non-minimal \(q\), ask pair queries \((r, q)\) with three optimizations:

  • Transitivity: if \((r, q)\) is already in the transitive closure, skip.

  • Antisymmetry: if \((q, r)\) is in the closure, then \((r, q)\) is impossible.

  • Bottom-up construction: start from minimal items and build outward.

Block 2+: Learning space refinement

Block \(n\) tests group queries with \(|A| = n\) to refine the ordinal space \(L_1\) into a learning space.

Inference mechanisms

For each candidate query \((A, q)\):

  1. Negative monotonicity: if \(q\) is globally minimal (from Qmax), then \((A, q) = \text{NO}\) for any \(A\) not containing \(q\).

  2. Positive monotonicity: if there exists a proper subset \(B \subset A\) such that \((B, q) = \text{YES}\) (from a previous block), then \((A, q) = \text{YES}\).

  3. Structural test (Theorem 43): Simulate a YES answer by removing states \(D_K = \{K \in \mathcal{L} \mid q \in K,\, A \cap K = \emptyset\}\). If the result has hanging states (non-empty states with empty inner fringe), the answer must be NO.

State removal

When \((A, q) = \text{YES}\), the states in \(D_K\) are removed from the current structure. These are states that contain \(q\) but are disjoint from \(A\) — they violate the discovered prerequisite.

Generalization

Block \(n\) for any \(n \geq 2\) follows the same pattern. The library supports arbitrary antecedent sizes via max_antecedent_size.

References

  • Koppen, M., & Doignon, J.-P. (1990). How to build a knowledge space by querying an expert. Journal of Mathematical Psychology, 34, 311–331.

  • Doignon, J.-P., & Falmagne, J.-C. (1999). Knowledge Spaces, Ch. 4.