On the primitivity of operators in SPARQL

• We show that AND can be simulated using OPT and FILTER.
• We show that OPT, FILTER, UNION, and SELECT, are primitive.
• We show that two existing semantics for filter conditions can simulate each other.
• We show that these results above are insensitive to the choice of two semantics.

The paper studies the primitivity of the basic operators UNION, AND, OPTIONAL, FILTER, and SELECT, as they are used in the SPARQL query language. The question of whether one operator can be expressed in terms of the other operators is answered in detail. It turns out that only AND is non-primitive. These results are shown to be insensitive to the choice of semantics for filter conditions (three-valued or two-valued). It is also shown that these two semantics can simulate each other.