Notation

WARNING

TODO: CHECK/UPDATE (2 years old and formatted in AsciiDocs)

We assume a countably infinite domain D being queried, a finite set P of predicates disjoint from D, and an interpretation function ||.|| defined over P, which to each predicate p in P associates a subset ||p|| of (D \union {NULL})^i^, for some positive integer i. The signature sig(Q) of a (sub)query Q is a subset of P. An the interpretation ||Q|| of Q is built inductively as usual, out of all ||p|| such that p is sig(Q), by application of RA operators.

In addition, we assume a countably infinite set A of attribute names, distinct from D and P. If ||Q|| is the interpretation of (sub)query Q, then the function att(||Q||) associates to ||Q|| a finite tuple ofn distinct elements of A, and n is called the arity of ||Q||.

NOTE: It is also assumed in what follows that the algebraic expression corresponding to an intermediate query is syntactically valid, according to standard requirements on RA operators. For instance, when a projection is performed, the projected attributes must be a subset of the attributes of the argument relation. Similarly, the arguments of a union operator must have identical set of attributes (this is not natively the case of the UNION SPARQL operator, but can be enforced with a straightforward normalization).