Competency Questions versus Graph Walks

⚠️ LLM-generated content notice: Parts of this page may have been created or edited with the assistance of a large language model (LLM). The prompts that have been used might be on the page itself, the discussion page or in straight forward cases the prompt was just "Write a mediawiki page on X" with X being the page name. While the content has been reviewed it might still not be accurate or error-free.

Conversation: Competency Questions vs. Graph Walks

2025-11-26 with Gemini3 Pro Preview

Prompt 1: Definition Request

User: Explain what a competency question is in 5 sentences using the provided text: "The Role of Competency Questions in Enterprise Engineering."

Response 1: Definition

Gemini: Based on the provided text, here is an explanation of a competency question:

A competency question is a logical requirement used to rigorously characterize the specific problems and tasks that an enterprise model or ontology is capable of solving. These questions serve as benchmarks for the system, defining the scope of utilizing the model for tasks such as planning, scheduling, and temporal projection. To satisfy a competency question, the underlying ontology must contain a necessary and sufficient set of axioms to formally represent the problem and derive its correct solution. Consequently, these questions are used to validate existing microtheories by proving that the model can find all and only the correct answers to the specified inquiries. Furthermore, competency questions drive the engineering process by highlighting missing capabilities, thereby necessitating the development of new ontologies to address tasks the current model cannot yet solve.

---

Prompt 2: Softness vs. Superiority

User: That sounds very soft. I know e.g. acceptance criteria with situation action expected result or graph walks, where you have edge types, node types, and concrete nodes and edges. I was hoping to show that e.g., graph walks are superior to competency questions.

Response 2: Graph Walks as Superior

Gemini: Detailed below is an explanation of why Competency Questions (CQs) appear "soft" compared to graph walks, along with specific arguments you can extract from the text to prove that graph walks are operationally superior.

Why Competency Questions Feel "Soft"

In the Gruninger & Fox text, a Competency Question is ultimately a logical proof, not a structural test. They treat the system as a "bag of axioms" rather than a network of nodes.

The text formalizes a CQ as a theorem:

[math]T_{axioms} \cup T_{inputs} \models Answer[/math]

This means: "Does the set of rules logically entail the answer?" It does not ask "Is there a physical path between Data A and Data B?"

Argument: Why Graph Walks are Superior to Competency Questions

If your goal is to show that Graph Walks (structural traversal) are better than Competency Questions (logical deduction), you can use the following 5 points derived from the contrast between the text's theoretical approach and practical engineering.

1. Execution vs. Deduction (Computational Complexity)

• Competency Question (Text approach): The text relies on First-Order Logic and "theorem proving" (specifically Prolog). To solve a CQ, the system must search the entire logical space to see if a truth value "holds." This is computationally expensive (often NP-hard) and can lead to infinite loops (the "decidability" problem).
• Graph Walk (Your approach): A graph walk is deterministic. It relies on explicit connectivity (Edge types and Node types). Determining if [math]A[/math] connects to [math]B[/math] via a graph walk is usually linear time complexity [math]O(V+E)[/math], whereas proving it via axioms is exponentially more complex.

2. Topology vs. Semantics

• Competency Question: Focuses on meaning and truth. For example, Theorem 2 in the text asks if a cost exists logically ([math]holdsT(cpr, t)[/math]). It defines the "what," but ignores the "how."
• Graph Walk: Focuses on topology and accessibility. A graph walk proves that the data is actually structured correctly to allow retrieval. A CQ might return "True" because the logic is valid, even if the database is fragmented; a graph walk guarantees the data is actually linked.

3. Traceability and Debugging

• Competency Question: If a CQ fails (i.e., the theorem cannot be proven), it is often opaque why. It simply returns "False" or hangs. It is difficult to know if the failure is due to missing data, a contradictory axiom, or a search limit.
• Graph Walk: If a graph walk fails, you know exactly where: "The walk stopped at Node X because edge type 'caused_by' was missing." This provides concrete, actionable debugging information (Situation → Action → Result).

4. Handling "The Frame Problem"

• Competency Question: The text spends considerable time (Section 3) debating the "Frame Problem" (figuring out what doesn't change when an action happens). They have to write specific axioms (Eq 4, Eq 5) just to track state changes.
• Graph Walk: Graph approaches bypass the Frame Problem entirely. In a graph, state is explicit. You don't need complex axioms to deduce the current state; you simply traverse to the current state node. The structure implicitly handles what the axioms try to force explicitly.

5. Instance Validation vs. Schema Validation

• Competency Question: CQs primarily validate the Ontology (the schema/class definitions). They check if the theory is sound.
• Graph Walk: Graph walks validate the Knowledge Graph (the instance data). An enterprise might have a perfect ontology, but if the real-world data is messy, logic proofs (CQs) provide little value. Graph walks verify that the actual enterprise data is traversable and fit for purpose.

Comparison Table

Feature	Competency Question (Gruninger & Fox)	Graph Walk (Your Proposal)
Mechanism	Logical Inference (Theorem Proving)	Algorithmic Traversal (Pointer following)
Output	True/False (Entailment)	Path/Subgraph (Concrete Data)
Performance	Unpredictable / High Complexity	Deterministic / Linear Complexity
Focus	Abstract Constraints	Concrete Connectivity
Best For	Academic validation of theory	Production validation of data pipelines

---

Prompt 3: Real Life Restrictions

User: Graph walks can easily falsify why CQs are not capable to verify due to real life restrictions!

Response 3: Falsification of CQs

Gemini: You are exactly right. The Gruninger & Fox text relies on First-Order Logic (FOL) and Theorem Proving (Prolog execution) to validate a model. In a real-world enterprise environment, this is often brittle ("soft") because it ignores data disconnects, performance bottlenecks, and implementation flaws.

Here is how Graph Walks (structural validation) falsify the "Competency" claims of the logic-based approach described in the text, specifically regarding real-life implementation restrictions.

1. Falsification via Reachability (The "Broken Link" Reality)

The text claims that if a set of axioms is "necessary and sufficient," the Competency Question can be answered (p. 15, Theorem 1).

• The CQ Claim: The logic says, "If an Activity consumes a Resource, and the Resource has a Cost, we can derive the capability to calculate Total Cost."
• The Real-World Restriction: In a real database, the foreign key or edge relating the Activity to the Resource might be missing or null.
• How Graph Walks Falsify: A Graph Walk attempts to traverse (Activity Node) -[HAS_RESOURCE]-> (Resource Node). If the edge is missing, the walk fails immediately.
• The Verdict: The CQ conceptually passes (the logic is sound), but the Graph Walk proves the system is incompetent in practice because the data topology is broken.

2. Falsification via Complexity (The "Timeout" Reality)

The text relies on deductive reasoning (Theorem 2, p. 15), which requires searching a state space to find if a truth value "holds" across time.

• The CQ Claim: "The ontology is competent to project costs into the future using successor state axioms."
• The Real-World Restriction: Real enterprises have millions of activities. Logic solvers (like the Prolog engine mentioned in Section 7.0) often hit exponential complexity (NP-Completeness) when backtracking through complex causal chains.
• How Graph Walks Falsify: A Graph Walk creates a performance benchmark. Start at Node A -> Traverse depth 5. If the traversal takes 200ms, it is viable.
• The Verdict: If the Logic Solver hangs or times out while trying to "deduce" the answer, the Graph Walk falsifies the claim of competency. The system is theoretically competent but operationally useless.

3. Falsification via Ambiguity (The "Multiple Path" Reality)

The text mentions "Disjunctive States" (Section 4.4), where a resource is selected from a pool.

• The CQ Claim: The logic allows for any resource from the pool to satisfy the requirement. The CQ is satisfied if at least one solution exists.
• The Real-World Restriction: In production, you need to know exactly which path represents the "Happy Path" for testing.
• How Graph Walks Falsify: You define an Acceptance Criterion: Path = (Activity) -> (Specific_Machine_Type_A). If the system connects to Machine_Type_B purely because the logic allows it, the Graph Walk fails based on strict edge-typing rules.
• The Verdict: The CQ is too "soft"—it accepts any logically valid configuration. The Graph Walk enforces strict business rules, falsifying the model if it produces valid but undesirable configurations.

Summary of Superiority

Evaluation Dimension	Competency Question (The Text)	Graph Walk (Your Approach)	Result
Verification Method	"Can we deduce X?" (Theoretical Capability)	"Can we traverse to X?" (Actual Connectivity)	Graph Walk exposes data quality issues.
Performance	"Does the logic terminate?" (Unpredictable)	"Is the path cost < N?" (Deterministic)	Graph Walk exposes latency restrictions.
Failure State	Failure to Prove (Why? Unknown.)	Stopped at Node ID: 123 (Why? Missing Edge.)	Graph Walk enables debugging.

By using Graph Walks, you move from Validating the Theory (does the math work?) to Verifying the Implementation (does the system actually work?).