DBMS sei ein allgemeines Datenbanksystem. Es wird untersucht, wie DBMS an die spezifischen Anforderungen einer Anwendung A angepaßt werden kann durch Erzeugen von Versionen, die nur die für A erforderlichen Fähigkeiten von DBMS realisieren.

Let DBMS be a general database management system. The problem of tailoring DBMS to the specific needs of an application A at hand by generating versions of DBMS, which provide only the features of DBMS required by A, is studied.

Die Erzeugung von Versionen von DBMS wird allgemein als das Problem der Erzeugung von Teilsystemen eines vollständigen Programmsystems PS behandelt. Das Programm eines Teilsystems t wird durch Auswahl der für t relevanten Teile des Programms von PS erzeugt. Es wird der Begriff Fragment eingeführt und damit ein heuristisches Verfahren zur Zerlegung eines Programmtextes von PS in die Teilstrings angegeben, mit denen als Bausteine die Teilsysteme von PS erzeugt werden können. Diese Zerlegung eines Programmtextes wird formal als sog. B-Programm beschrieben: ein geordneter Baum mit den Teilstrings des Programm von PS als Blattknoten und den Fragmenten als innere Knoten. Eine Abbildung REL: T×F → {0,1} (T: Menge der Teilsysteme von PS; F: Menge der Fragmente) gibt zu jedem Fragment f an, ob der Teilbaum mit f als Wurzel für ein Teilsystem t relevant ist oder nicht (REL(t,f)=1 bzw. 0); zu jedem Fragment f wird ein Ersatz SUBST(f) angegeben.

Generation of versions of DBMS is treated as the general problem of constructing partial systems of a given comprehensive program system PS. The program of a partial system t is composed of the substrings of the program text of PS relevant to t. The concept of fragment is introduced and a heuristic method is developed for the decomposition of the program of PS into the substrings, which serve as the building blocks for the construction of the partial systems of PS. This decomposition is formally described as a so-called B-program: an ordered tree with the substrings as its leaves and the fragments as its non-leaf vertices. A mapping REL: T×F → {0,1} (T: set of partial systems of PS; F: set of fragments) indicates, whether or not the subtree with fragment f as its root is relevant to t (REL(t,f)=1 or 0, resp.); each fragment f is assigned a substitute SUBST(f).

Teilsystem-Erzeugung wird als pre-order Durchlauf eines Teilbaumes eines B-Programms eingeführt. Die Menge T ist bestimmt durch Beziehungen zwischen Fragmenten, die sich aus dem Kontrollfluß von PS herleiten; sie werden formal mittels eines sog. Fragmentsystems (gerichteter azyklischer Graph mit den Fragmenten als Knoten) als Eigenschaften von REL beschrieben. Es wird ein Verfahren angegeben zur Konstruktion einer Teilmenge CF der Menge F, die minimal ist mit der Eigenschaft, daß mit der Zuweisung von Relevanzwerten an die Fragmente von CF die Relevanzwerte aller Fragmente von F festgelegt sind.

Generation of a partial system is formally defined as pre-order traversal of a subtree of a B-program. The set T is characterized by means of interrelationships between fragments reflecting the flow of control of PS. The concept of fragment system (basically a directed acyclic graph) is introduced to describe these relationships as properties of REL. An algorithm is presented for the construction of a minimal subset CF of F with the property, that with the assignment of relevance values to the elements of CF the relevance values of all fragments are determined.

Jedem Element t von T entspricht genau ein Element von Bⁿ (B={0,1}) mit n=|CF|; T wird explizit als Teilmenge von Bⁿ dargestellt. Die Architektur eines allgemeinen Systems zur automatischen Erzeugung von Teilsystemen, insbesondere die Implementierung von B-Programmen als Erweiterung des Programms von PS, wird angegeben.

Thus, each element t of T corresponds to exactly one element of Bⁿ (B={0,1}) with n=|CF|; an explicit representation of T as a subset of Bⁿ is given. The architecture of a program generator for the automatic generation of partial systems based on these ideas, in particular an implementation of B-programs as an expansion of the program of PS, is delineated.

Eine Version V von DBMS ist mit einer Anwendung verträglich, wenn V alle für das Anwenderprogramm erforderlichen Operationen implementiert und alle von V realisierten Operationen auf die gesamte Datenbank ausführen kann. Die Menge der mit einer Anwendung verträglichen Versionen wird als Teilmenge von Bⁿ charakterisiert.

A version V of DBMS is compatible with an application, iff V implements (at least) all operations called for by the application program and is able to correctly execute all operations implemented by V against the database. The set of versions compatible with an application is characterized in terms of subsets of Bⁿ.