Induction of Relational Algebra Expressions

Abstract

We consider the induction of relational algebra expressions from examples consisting of a relational database and an output relation. This problem fits perfectly in the ILP context but has not been investigated in specific detail. We discuss the importance of negation (difference, complementation, universal quantification), propose a new heuristic to take complementation into account, and propose the use of cylindrical set algebra as a more flexible form for searching expressions. We present some modest experimental results which nevertheless show that our approach allows the induction of typical relational database queries involving universal quantification, such as Codd's relational division operator.