Data construction with recursive set expressions

J. Eder, A. Rudloif, F. Matthes, J. W. Schmidt

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

2 Zitate (Scopus)


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.

TitelNext Generation Information System Technology - 1st International East/West Data Base Workshop, Proceedings
Redakteure/-innenJoachim W. Schmidt, Anatoty A. Stogny
Herausgeber (Verlag)Springer Verlag
ISBN (Print)9783540541417
PublikationsstatusVeröffentlicht - 1991
Extern publiziertJa
Veranstaltung1st International East/West Data Base Workshop on Next Generation Information System Technology, 1990 - Kiev, Ukraine
Dauer: 9 Okt. 199012 Okt. 1990


NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Band504 LNCS
ISSN (Print)0302-9743
ISSN (elektronisch)1611-3349


Konferenz1st International East/West Data Base Workshop on Next Generation Information System Technology, 1990


Untersuchen Sie die Forschungsthemen von „Data construction with recursive set expressions“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren