Doctoral Seminar: Ali Moallemi

Speaker: Ali Moallemi

Supervisor: Dr. G. Grahne

Supervisory Committee: Drs. J. Bentahar, L. Narayanan, R. Raphael

Title: Universal and Existential Nulls in Databases

Date: Thursday, November 16, 2017

Time: 11:40 a.m.

Place: EV 3.309

ABSTRACT

Incomplete Information research is quite mature when it comes to so called existential nulls, where an existential null is a value stored in the database, representing an unknown object. For some reason universal nulls, that is, values representing all possible objects, have received almost no attention. We remedy the situation in this research, by showing that a suitable finite representation mechanism, called Star Cylinders, handling universal nulls can be developed based on the Cylindric Set Algebra. We provide a finitary version of the cylindric set algebra, called Cylindric Star Algebra, and show that our star-cylinders are closed under this algebra. Moreover, we show that any First Order Relational Calculus query over databases containing universal nulls can be translated into an equivalent expression in our cylindric star-algebra, and vice versa. We also show that the positive (allowing universal quantification, but not negation) first order queries can be evaluated naively. The representation mechanism is then extend to Naive Star Cylinders, which are star cylinders allowing existential nulls in addition to universal nulls. For positive queries (with universal quantification), the well-known naive evaluation technique can still be applied on the existential nulls, thereby allowing evaluation of certain answers on databases containing both universal and existential nulls.