DATA CONSTRUCTORS: ON THE INTEGRATION OF RULES AND RELATIONS

Abstract

Although the goals and means of rule-based and data-based systems are too different to be fully integrated at the present time, it seems appropriate to investigate a closer integration of language constructs and a better cooperation of execution models for both kinds of approaches. In this paper, we propose a new language construct called constructor that – when applied to a base relation – causes relation membership to become true for all tuples constructable through the predicates provided by the constructor definition. The approach is shown to provide expressive power at least equivalent to PROLOG's declarative semantics while blending well both with a strongly typed modular programming language and with a relational calculus query formalism. A three-step compilation, optimization, and evaluation methodology for expressions with constructed relations is described that integrates constructors with the surrounding database programming environment. In particular, many recursive queries can be evaluated more efficiently within the set-construction framework of database systems than with proof-oriented methods typical for a rule-based approach.