Universal Nulls (Extended Abstract) In this paper we revisit the foundations of the relational model and unearth universal nulls, showing that they can be treated on par with the usual existential nulls [10,4,5,2] Recall that an existential null in a tuple in a relation R represents an existentially quanti ed variable in an atomic sentence R(::). This corresponds to the intuition \value exists, but is unknown." A universal null, on the other hand, does not represent anything unknown, but stands for all values of the domain. In other words, a universal null represents a universally quanti ed variable. Universal nulls have an obvious application in databases, as the following example shows. The symbol \∗" denotes a universal null. Example 1. Consider binary relations F (ollows) and H(obbies), where F (x; y) means that user x follows user y on a social media site, and H(x; z) means that z is a hobby of user x. Let the database be the following.
(1) The answer to our example query is {(Movies); (Music)}. Note that star-nulls also can be part of an answer. For instance, the query x1; x2 : F (x1; x2) would return all the tuples in F . ◂
Another area of applications of \*"-nulls relates to intuitionistic, or
constructive database logic. In the constructive four-valued approach of [
( ) to a pair of queries ('+(x); '−(x)) such that '+(x) returns the tuples a for which '(a) is true in I, and '−(x) returns the tuples a for which '(a) is true in I (i.e. '(a) is proven to be false in I). It turns out that databases containing \*"-nulls are suitable for storing I−. Example 2. Suppose that the instance in Example 1 represents I+, and that all negative information we have deduced about the H(obbies) relation, is that we know Alice doesn't play Volleyball that Bob only has Basketball as hobby, and that Chris has no hobby at all. This negative information about the relation H is represented by the table H− below. Note that H− is part of I−.
H− Alice Volleyball Bob ∗ (except Basketball)
Chris ∗ Suppose the query ' asks for people who have a hobby, that is ' = x1 : ∃x2 H(x1; x2). Then '+ = x1 : ∃x2 H+(x1; x2), and '− = x1 : ∀x2 H−(x1; x2). Evaluating '+ on I+ returns {(Alice); (Bob)}, and evaluating '− on I− returns {(Chris)}. Note that there is no closed-world assumption as the negative facts are explicit. Thus it is unknown whether someone called David has a hobby or not. ◂
This example highlights our main motivation for adding universal nulls to databases. When intuitionistic logic is used in answering queries with negation against four-valued database instances, universal quanti ers are necessary. In fact, even the simplest queries, such as Conjunctive Queries will be translated to a universally quanti ed disjunction of the atoms in the query. The cost of evaluating FO-queries ' intuitionistically on four-valued databases remains the same as evaluating ' with standard semantics on two-valued databases. Note however that '+ and '− are always negation free.
The Cylindric Set Algebra [
The objects C and dij of [
Example 3. Continuing Example 1, in that database the atoms F (x1; x2) and H(x3; x4) of query (1) are represented by star-tables CF and CH , and the equality atom is represented by the star-cylinder C23. Note that these are positional relations, the \attributes" x1; x2; x3; x4 are added for illustrative purposes only.
CF x1 x2 x3 x4 Alice Chris ∗ ∗ ∗ Alice ∗ ∗ Bob ∗ ∗ ∗ Chris Bob ∗ ∗
CH x1 x2 x3 x4 ∗ ∗ Alice Movies ∗ ∗ Alice Music ∗ ∗ Bob Basketball The algebraic translation of query (1) is the SCA-expression C23 x1 x2 x3 x4 ∗
∗ ∗ ∗ 2=3 c_2(c_3(_1c((CF ⩀ CH ) ⩀ C23))) (2) The intersection of CF and CH is carried out as star-intersection ⩀, where for instance {(a; ∗; ∗)} ⩀ {(∗; b; ∗)} = {(a; b; ∗)}. The result will contain 12 tuples, and when these are star-intersected with C23, the star-cylinder C23 will act as a selection by columns 2 and 3 being equal. The result is the left-most star-cylinder C′ = (CF ⩀ CH ) ⩀ C23 below. x1 x2 x3 x4 ∗ Alice Alice Movies ∗ Alice Alice Music Bob Alice Alice Movies Bob Alice Alice Music Bob Bob Bob Basketball Chris Bob Bob Basketball x1 x2 x3 x4
Alice Alice Movies Alice Alice Music x1 x2 x3 x4
Movies
Music
∗ ∗
∗ ∗
Applying the inner star-cylindri cation on column 1 results in C′′ in the middle
above. Finally, applying outer star-cylindri cations on columns 2 and 3 of
starcylinder C′′ yields the nal result C′′′ = c_2(c_3(_1c((CF ⩀ CH ) ⩀ C23))) right-most
above. The system can now return the answer, i.e. the values of column 4 in
cylinder C′′′. Note that columns where all rows are \∗" do not actually have to
be materialized at any stage. Negation requires some additional details that can
be found in the full version [
The aim of this paper is to develop a clean and sound modeling of universal
nulls, and furthermore show that the model can be seamlessly extended to
incorporate the existential nulls of Imielinski and Lipski [
At the end of Section 3 we we take the third step show how to tie these
two results together, delivering the promised SCA evaluation of FO queries on
databases containing universal nulls. In the full paper [
Relational calculus and cylindric set algebra Throughout this paper we assume a xed schema R = {R1; : : : ; Rm; ≈}, where each Rp, p ∈ {1; : : : ; m}, is a relational symbol with an associated positive integer ar(Rp), called the arity of Rp. The symbol ≈ represents equality.
Logic. Our calculus is the standard domain relational calculus. Let {x1; x2; : : :} be a countably in nite set of variables. We de ne the set of FO-formulas ' (over R) in the usual way: Rp(xi1 ; : : : ; xiar(Rp) ) and xi ≈ xj are atomic formulas, and these are closed under ∧; ∨; ¬; ∃xi; and ∀xi; in a well-formed manner possibly using parenthesis's for disambiguation. If an FO-formula uses n variables, it will be called an FOn-formula.
Instances. Let D = {a1; a2; : : :} be a countably in nite domain. An instance I (over R) is a mapping that assigns a possibly in nite subset RpI of Dar(Rp) to each relation symbol Rp, and ≈I = {(a; a) ∶ a ∈ D}. Note that our instances are in nite model-theoretic ones. The set of tuples actually recorded in the database will be called the stored database (to be de ned in Section 3).
In order to de ne the (standard) notion of truth of an FOn-formula ' in an
instance I we rst de ne a valuation to be a mapping ∶ {x1; : : : ; xn} → D. If
is a valuation, xi a variable and a ∈ D, then (i~a) denotes the valuation which is
the same as , except (i~a)(xi) = a. Then we use the usual recursive de nition
of I ⊧ ', meaning instance I satisfying ' under valuation , i.e. I ⊧ (xi ≈ xj )
if ( (xi); (xj )) ∈ ≈I , I ⊧ Rp(xi1 ; : : : ; xiar(Rp) ) if ( (xi1 ); : : : ; (xiar(Rp) )) ∈ RpI,
and I ⊧ ∃xi ' if I ⊧ (i~a) ' for some a ∈ D, and so on. Our stored databases
will be nite representations of in nite instances, so the semantics of answers to
FO-queries will be de ned in terms of the in nite instances:
De nition 1. Let I be an instance, and ' an FOn-formula with f ree(') =
{xi1 ; : : : ; xik }, k ≤ n. Then the answer to ' on I is de ned as
'I = {( (xi1 ); : : : ; (xik )) ∶ I ⊧
'}:
Algebra. As noted in [
Let n be a xed positive integer. The basic building block of the Cylindric Set Algebra is an n-dimensional cylinder C ⊆ Dn. Note that a cylinder is essentially an in nite n-ary relation. They will however be called cylinders, in order to distinguish them from instances. The rows in a cylinder will represent run-time variable valuations, whereas tuples in instances represent facts about the real world. We also have special cylinders called diagonals, of the form dij = {t ∈ Dn ∶ t(i) = t(j)} representing the equality xi ≈ xj . We can now de ne the Cylindric Set Algebra.
De nition 2. Let C and C′ be in nite n-dimensional cylinders. The Cylindric Set Algebra consists of set theoretic union C ⋃ C′, complement C = Dn ∖ C, diagonals dij = {t ∈ Dn ∶ t(i) = t(j)}, and outer cylindri cation:
ci(C) = {t ∈ Dn ∶ t(i~a) ∈ C; for some a ∈ D}:
The operation ci corresponds to existential quanti cation of variable xi. For the
geometric intuition behind the name cylindri cation, see [
ic(C) = {t ∈ Dn ∶ t(i~a) ∈ C; for all a ∈ D}:
Equivalence of FO and CA. In the next two theorems we will restate, in the
context of the relational model, the correspondence between domain relational
calculus and cylindric set algebra as query languages on instances [
Once an instance is expanded it becomes a sequence C = (C1; : : : ; Cm; dij)i;j of n-dimensional cylinders and diagonals, on which Cylindric Set Algebra Expressions can be applied. The main technical di culty in the translation from FOn to CAn is the correlation of the variables in the FOn-sentence ' with the columns in the expanded relations in the instance. This can be achieved using a derived \swapping" operator zi1;:::;ik that interchanges the columns il and jl, where l ∈ j1;:::;jk {1; : : : ; k}.3 Every atom Rp in ' will correspond to a CAn-expression Cp = h ( n RpI).
However, for every occurrence of an atom Rp(xi1 ; : : : ; xik ) in ' we need to interchange the columns 1; : : : ; k with columns i1; : : : ; ik. This is achieved by the expression z1;:::;k
i1;:::;ik (Cp). The entire FOn-formula ' with f ree(') = {xi1 ; : : : ; xik } will then correspond to the CAn-expression E' = zi11;:;::::;:k;ik (F'), where F' is de ned recursively as follows: { If ' = Rp(xi1 ; : : : ; xik ) where k = ar(Rp), then F' = zi11;:;::::;:k;ik (Cp): { If ' = xi ≈ xj, then F' = dij. { If ' = ∨ , then F' = F ⋃ F , if ' = ∧ , then F' = F
' = ¬ , then F' = F . { If ' = ∃xi , then F' = ci(F ).
{ If ' = ∀xi , then F' = ic(F ).
For an example, let us reformulate the F O4-query ' from (1) as
⋂ F , and if
x4 : ∃x2∃x3∀x1 R1(x1; x2) ∧ R2(x3; x4) ∧ (x2 ≈ x3):
3 For a de nition of swapping using primitive operators, see De nition 1.5.12 in [
4 'I ). The following fundamental result follows from
[
Theorem 1. For all FOn-formulas ', there is a CAn expression E', such that E'(hn(I)) = h (
n 'I ); for all instances I. ◂
The translation from CAn-expressions to FOn-formulas is fairly
straightforward an can be found in the full version [
Cylindric Set Algebra and Cylindric Star Algebra
Since cylinders can be in nite, we want a nite mechanism to represent (at
least some) in nite cylinders, and the mechanism to be closed under queries.
Our representation mechanism comes in two variations, depending on whether
negation is allowed or not. Here we only consider the positive (no negation) case.
The full machinery is described in [
Star Cylinders. We de ne an n-dimensional (positive) star-cylinder C_ to be a nite set of n-ary star-tuples, the latter being elements of (D ∪ {∗})n × ´( n), where n denotes the set of all equalities of the form i = j, with i; j ∈ {1; : : : ; n}. Star-tuples will be denoted t_; u_ ; : : :. A star-tuple such as t_ = (a; ∗; c; ∗; ∗; {(4 = 5)}) is meant to represent the set of all \ordinary" tuples (a; x; c; y; y) where x; y ∈ D. It will be convenient to assume that all our star-cylinders are in the following normal form.
De nition 3. An n-dimensional star-cylinder C_ is said to be in normal form if t_(n + 1) ⊧ (i = j) entails (i = j) ∈ t_(n + 1) and t_(i) = t_(j), for all star-tuples t_ ∈ C_ .
The symbol ⊧ above stands for standard logical implication. It is easily seen that maintaining star-cylinders in normal form can be done e ciently in polynomial time. We shall therefore assume without loss of generality that all star-cylinders and star-tuples are in normal form. We next de ne the notion of dominance, where a dominating star-tuple represents a superset of the ordinary tuples represented by the dominated star-tuple. First we de ne a relation ⪯ ⊆ (D ∪ {∗})2 by a ⪯ a, ∗ ⪯ ∗, and a ⪯ ∗, for all a ∈ D.
De nition 4. Let t_ and u_ be n-dimensional star-tuples. We say that u_ dominates t_, denoted t_ ⪯ u_, if t_(i) ⪯ u_(i) for all i ∈ {1;:::;n}, and (i = j) ∈ u_(n + 1) entails (i = j) ∈ t_(n + 1) when t_(i) = t_(j) = ∗, and entails t_(i) = t_(j) otherwise.
We complete the de nition by stipulating that t_ ⪯ u_ whenever t_(n + 1) = {false}4. We can now de ne the meet t_⋏ u_ of star-tuples t_ and u_ : De nition 5. Let t_ and u_ be n-ary star-tuples. If t_(j);u_ j ( ) ∈ D for some j and t_ j ( ) then t_⋏ u_ (i) = a for i ∈ {1;:::;n}, and t_⋏ u_(n + 1) = {false}. 5 ( ) ≠ u_ j Otherwise, for i ∈ {1;:::;n} ⎧t_(i) if t_(i) ∈ D ⎪ ⎪ t_⋏ u_ (i) = ⎨⎪u_ i
( ) if u_(i) ∈ D ⎪⎪⎩⎪∗ if t_(i) = u_(i) = ∗ and t_⋏ u_ (n + 1) = t_(n + 1) ∪ u_(n + 1):
For an example, let t_ = (a;∗;∗;∗;∗;{(3 = 4)}) and u_ = (∗;b;∗;∗;∗;{(4 = 5)}). Then we have t_⋏ u_ = (a;b;∗;∗;∗;{(3 = 4);(4 = 5);(3 = 5)}). Note that t_⋏ u_ ⪯ t_, and t_⋏ u_ ⪯ u_. Note also that for n-ary star-tuples t_∅ = (a;a;:::;a;{false}) and t_Dn = (∗;∗;:::;∗;{true}), and for any n-ary star-tuple t_, it holds that t_⋏ t_∅ = t_∅, t_⋏ t_Dn = t_, and t_∅ ⪯ t_ ⪯ t_Dn.
We extend the order ⪯ to include \ordinary" n-ary tuples t ∈ Dn by identifying (a1;:::;an) with star-tuple (a1;:::;an;{true}). Let C_ be an n-dimensional starcylinder. We can now de ne the meaning of C_ to be the set [[C ]] of all ordinary _ tuples it represents, where [[C_ ]] = {t ∈ Dn ∶ t ⪯ u_ for some u_ ∈ C_}: We lift the order to n-dimensional star-cylinders C_ and D_ , by stipulating that C_ ⪯ D_ , if for all star-tuples t_ ∈ C_ there is a star-tuple u_ ∈ D_ , such that t_ ⪯ u_.
Lemma 1. Let C_ and D_ be n-dimensional (positive) star-cylinders. Then it holds that [[C_]] ⊆ [[D]] i C ⪯ D_ .
_ _ Positive Cylindric Star Algebra. Next we rede ne the positive cylindric set operators so that [[C_ ○_ D_ ]] = [[C_]] ○ [[D_ ]] or ○([[C_]]) = [[○_(C_)]], for each positive cylindric operator ○, its rede nition ○_, and star-cylinders C_ and D_ . De nition 6. The positive cylindric star-algebra consists of the operators 1. Star-diagonal: d_ij = {(∗;:::;∗;(i = j))} 2. Star-union: C_ ⊍ D_ = {t_ ∶ t_ ∈ C_ or t_ ∈ D_ } 3. Star-intersection: C_ ⩀ D_ = {t_⋏ u_ ∶ t_ ∈ C_ and u_ ∈ D_ } 4. Outer cylindri cation: Let i ∈ {1;:::;n}, let C_ be an n-dimensional starcylinder, and t_ ∈ C_. Then
t_(j) if j ≠ i c_i(t_)(j) = ∗ if j = i 4 Note that only in this case t_ is not in normal form. 5 Here a is an arbitrary constant in D.
for j ∈ {1; : : : ; n}, and
c_i(t_)(n + 1) = {(j = k) ∈ t_(n + 1) ∶ j; k ≠ i}:
We then let c_i(C_ ) = {c_i(t_ ) ∶ t_ ∈ C_ }: 5. Inner cylindri cation: Let C_ be an n-dimensional cylinder and i ∈ {1; : : : ; n}.
Then _ic(C_ ) = {t ∈ C ∶ t_(i) = ∗ and (i = j) ∉ t_(n + 1) for any j}:
_ _
The class of positive SCAn- and CAn-expressions will be denoted SCA+n and CA+n. We illustrate the positive cylindric star-algebra with the following small example.
Example 4. Let C_ 1 = {(a; ∗; ∗; ∗; ∗; {(3 = 4)})}, C_ 2 = {(∗; b; ∗; ∗; ∗; {(4 = 5)})}, _ _ _ _ C3 = {(a; b; ∗; ∗; ∗; {(4 = 5)})}, and consider _3c((c_1;4(C1 ⩀ C2)) ⊍ C3): Then we have the following.
(c_1;4(C_ 1 ⩀ C_2)) ⊍ C3 = {(∗; b; ∗; ∗; ∗; {(3 = 5)})
C_ 1 ⩀ C2 = {(a; b; ∗; ∗; ∗; {(3 = 4); (4 = 5); (3 = 5)})}
_ c_1;4(C_ 1 ⩀ C2) = {(∗; b; ∗; ∗; ∗; {(3 = 5)})}
_ _3c((c1;4(C_ 1 ⩀ C_2)) ⊍ C3) = {(a; b; ∗; ∗; ∗; {(4 = 5)})}
(a; b; ∗; ∗; ∗; {(4 = 5)})}
Next we show that the cylindric star-algebra has the promised property. Theorem 2. For every SCA+n-expression E_ and the corresponding CA+n expression E, it holds that [[E( _ _
_ C)]] = E([[C]]) for every sequence of n-dimensional star-cylinders and star-diagonals C_.
Stored databases with universal nulls. We now show how to use star cylindric algebra to evaluate FO-queries on stored databases containing universal nulls. Let k be a positive integer. Then a k-ary star-relation R_ is a nite set of star-tuples of arity k. In other words, a k-ary star-relation is a star-cylinder of dimension k. A sequence R_ of star-relations (over schema R) is called a stored database. Examples 1 and 3 show stored databases. A stored database R_ _ _ _ represents the in nite instance [[R]] = ([[R1]]; : : : ; [[Rm]]; {(a; a)}a∈D):
Everything that is de ned for star-cylinders applies to k-ary star-relations. The major exception is that no operators from the cylindric star-algebra are applied to star-relations. To do that, we rst need to expand the stored database R_, by lling columns n − k : : : n with ∗ in all k-ary relations, and similarly for the diagonals. The result is denoted h_n( R_). We are now ready for our main result.6 Theorem 3. For every FOn-formula ' there is an SCAn expression E_ ', such that for every stored database R_, we have hn('[[R_ ]]) = [[E_ '( h_n( R_))]]: 6 It might be argued for some applications that the \*"-value should range over the nite active domain only. This can be achieved in the positive framework by requiring for each star-cylinder C_ (expanded star-relation), and each star-tuple t_ ∈ C_ , that if ci([[t_]]) ⊆ [[C_ ]], then C_ also contains a star-tuple u_ , where u_ = t_(i~∗).
Universal nulls were rst studied in the early days of database theory by Biskup
in [