PhD Oral Exam - Ali Moallemi, Computer Science

When studying for a doctoral degree (PhD), candidates submit a thesis that provides a critical review of the current state of knowledge of the thesis subject as well as the student’s own contributions to the subject. The distinguishing criterion of doctoral graduate research is a significant and original contribution to knowledge.

Once accepted, the candidate presents the thesis orally. This oral exam is open to the public.

Abstract

The goal of this thesis is to introduce a logical view of databases based on four-valued logic, to revisit the foundations of the relational model and unearth universal nulls, and to handle finitely representable cases of infinite databases. In order to achieve this, we develop an intuitionistic relevance-logic based semantics that allows us to handle Full First Order queries similar monotone First Order queries.

Universal Null represents all the possible values in the Domain. Next, we fully investigate the relational model and universal nulls, showing that they can be treated on par with the usual existential nulls. To do so, we show that a suitable finite representation mechanism, called Star-Cylinders, handling universal nulls can be developed based on the Cylindric Set Algebra of Henkin, Monk and Tarski. We provide a finitary version of the Cylindric Set Algebra, called Star Cylindric 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 star cylindric algebra, and vice versa. All star cylindric algebra expressions can be evaluated in time polynomial in the size of the database. Furthermore, the representation mechanism is then extended to Naive Star-Cylinders, which are star-cylinders allowing existential nulls in addition to universal nulls. Beside the theory part, we also provide a practical approach for four-valued databases. We show that the four-valued database instances can be stored as a pair of two-valued instances. These two-valued instances store positive and negative information independently, in format of current databases. This procedure is called decomposition. Decomposed instances can losslessly be merged to form the initial four-valued instance. In a similar way, we show that four-valued queries can be decomposed to two-valued queries and can be executed against decomposed instances to obtain the four-valued result, after merging them back.

Later, we show that how these results can be extended to Datalog and we show that there is no need for any syntactical notion of stratification or non-monotonic reasoning, when the intuitionistic logic is implemented. This is followed by presenting the complexity results. For positive queries (with universal quantification), the well known naive evaluation technique can still be applied on the existential nulls, thereby allowing polynomial time evaluation of certain answers on databases containing both universal and existential nulls. If precise answers are required, certain answer evaluation with universal and existential nulls remains in coNP. Note that the problem is coNP-hard, already for positive existential queries and databases with only existential nulls. If inequalities ¬(x_i≈ x_j) are allowed, reasoning over existential databases is known to be Π_2^p -complete, and it remains in Π_2^p when universal nulls and full first order queries are allowed. Finally, we discuss related and future works.