Query languages for hierarchic databases (Q1201723)

The relational data model is extended to allow cumulative hierarchic structures in the form of directories of relations and directories of directories. Directories are thus just finite sets of (finite sets of \dots) relations, i.e. higher order relations. The main merit of the paper is the precise definition of the semantics of set oriented programming languages and the contributions to generalized computation theory. A higher order database is defined as an ordered tuple \(B=(D,FD_ 1,\dots,FD_ k)\), where \(D\) is a fixed countable set --- the universal domain, and \(FD_ i\) are finite directories. In this framework the authors study computable directory transformations which generalize the computable queries introduced by \textit{A. Chandra} and \textit{D. Harel}. They introduce a set-oriented language \(DL\) language which can serve as a basis for a specification of directory transformations called directory queries. The \(DL\) language is essentially a programming language computing finite higher-order objects (directories) over some finite domain. The semantics is based on the set theory of hereditary finite sets with urelements. Two main theorems illustrate that the chosen framework is correct. By proving the Completeness Theorem the authors show that for every computable directory query there is a program in \(DL\) computing it. Further, a sublanguage \(DL_ 0\) of \(DL\) is defined and the Theorem of Independence is proved which says that for each construct \(c\) of \(DL_ 0\) there is a computable query which is not computable in \(DL_ 0- \{c\}\). The extended query language allowing to handle also names is informally discussed. Finally, a rather detailed discussion is given on the relationship of this approach to various parallel works and other models of hierarchic and object-oriented databases.