Data construction with recursive set expressions

In this paper we present a conceptually rather conservative approach to data deduction. Instead of introducing new language constructs we stay within the conventional relational framework while exploiting it further by making better use of current language technology. Applying naming, typing and binding to queries and relations leads to a language that gains expressiveness from its orthogonality rather than from extensiveness. As a framework for our presentation we use DBPL, a strongly typed database programming language based on the relational calculus and on Modula-2. In DBPL, data construction is expressed declaratively through set-oriented expressions which can be abstracted by parameterization and by naming, thus allowing powerful recursive constructor definitions. In the paper, a model-theoretic constructor semantics is defined in two steps: parameter substitution in constructor definitions leads to constructor instances which are then evaluated in a second step. The first step can be regarded as logic program generation, the second step as program evaluation. We show that for the general case no procedure exists that evaluates an arbitrary set of parameterized constructors and is guaranteed to terminate. However, we are able to classify constructors and give an evaluation algorithm which terminates for interesting subclasses. Finally, we solve an example from the literature showing that NP-complete problems can be solved by constructors from a subclass which is decidable. This implies that decidable DBPL constructors are strictly more expressive than stratified Datalog.