Logic Programs as basic representation: Advantages
Declarative: semantics is independent of inferencing procedure implementation, e.g., forward vs. backward chaining, sequencing of executing rules or conditions within rules.
Expressive: relational expressions cf. SQL, large fragment of first-order logic, chaining, basic logical non-monotonicity (unlike first-order logic).
Efficient: computationally tractable given two reasonable restrictions:
- 1. Datalog = no logical functions of non-zero arity.
- 2. Bounded number v of logical variables per rule.
- m = O( n^(v+1) ), where n = ||LP||, m = ||ground-instantiated LP||.
- Inferencing time is O( m) for broad (acyclic) case, O(m^2) generally (for well-founded semantics).
- By contrast, first-order-logic inferencing is NP-hard.