Past exam of the computer science course of the University of Oxford / 2015 / Knowledge representation and reasoning / 1 / c / i

With existential rules understood as function-free tuple-generating dependencies, $\boxed{\text{only (ii)}}$ belongs to the fragment. Split its antecedent to obtainThese two existential rules have exactly the same meaning as (ii): either category requires a supervisor, and when both hold the same supervisor may witness both requirements.

Sentence (i) requires a genuine choice between two positive alternatives and also an exclusion condition. Positive existential rules cannot enforce that exclusion: interpreting all their relations as full relations on a one-element domain always satisfies them, whereas that interpretation violates (i). Sentence (iii), in the supplied vocabulary, uses the nonconstant function $CountSupervise$ and is therefore outside the function-free fragment. Introducing a new relation for the counting comparison would change the representation and require additional axioms; it is not an equivalent sentence in the stated vocabulary.