Query languages for hierarchic databases

DOI10.1016/0890-5401(92)90074-PMaRDI QIDQ1201723zbMATH OpenOpenAlexFDO

Authors Elias Dahlhaus, Johann A. Makowsky

Publication date 17 January 1993

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0890-5401(92)90074-p

zbMATH Keywords

completeness directory higher order database independence

Mathematics Subject Classification ID

Database theory (68P15)

Review text

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.

Recommendations

Cites work

Cited in

(12)

Describes a project that uses

Uses Software

Smalltalk

This page was built for publication: Query languages for hierarchic databases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1201723)