Compiling Equality in an Abstract Relational Model via Preference Tables and Translation Tables

Abstract

Borgida et al. have introduced a refinement to the relational model (RM) [1] which they call the abstract relational model (ARM) that extends the former in the following three ways: 1. the addition of a new abstract domain eid of entity identifiers to Structured Query Language (SQL) built-in concrete domains; 2. a capacity to resolve reference issues via PRIMARY KEY clauses is replaced by a new domain specific language for referring expression types; and 3. terms in SQL of the form “v.A” can now have the form “v.A1. · · · .Ak” to more compactly encode navigation over foreign keys, thus yielding the language SQLP. They have also proposed an algorithm for mapping ARM schemata to corresponding RM schemata via referring expression types and to subsequently map SQLP queries over the former to corresponding SQL queries over the latter, again via referring expression types. This mapping system relies on introducing so-called preference tables to enable coercion between alternative primary keys. Such tables, however, fail to account for circumstances in which explicit translation tables can exist to map between such alternatives in order to satisfy programmer intentions. In this thesis, we remedy this by extending their algorithm to enable the generation of such translation tables and their use in compiling SQLP.