Elimination of View and Redundant Variables in a SQL-like Database Language for Extended NF2 Structures.

Norbert Südkamp, Volker Linnemann: Elimination of View and Redundant Variables in a SQL-like Database Language for Extended NF2 Structures. VLDB 1990: 302-313
  author    = {Norbert S{\"u}dkamp and
               Volker Linnemann},
  editor    = {Dennis McLeod and
               Ron Sacks-Davis and
               Hans-J{\"o}rg Schek},
  title     = {Elimination of View and Redundant Variables in a SQL-like Database
               Language for Extended NF2 Structures},
  booktitle = {16th International Conference on Very Large Data Bases, August
               13-16, 1990, Brisbane, Queensland, Australia, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1990},
  isbn      = {1-55860-149-X},
  pages     = {302-313},
  ee        = {db/conf/vldb/SudkampL90.html},
  crossref  = {DBLP:conf/vldb/90},
  bibsource = {DBLP,}


The Advanced Information Management Prototype (AIM) is an experimental database system, developed and prototyped at the IBM Scientific Center in Heidelberg,Germany. The underlying data model is an extension of the NF2 data model. It is founded on the notions of tuple, set and list. These three constructors may be applied to any valid structure in any order, starting with some atomic domain(s), to get a valid AIM database structure. The corresponding database language, called HDBL (Heidelberg Data Base Language) is an SQL-type language meeting the requirements of the extended NF2 data model.

In this paper we investigate the problem of improving the evaluation of HDBL queries by transformation of the query. The first kind of transformation deals with view processing. Given an HDBL query containing a view it is often not necessary to materializethe view. We will give some rules on how to eliminate the view and evaluate the query against the base relations. Another kind of transformation will be used to remove variables from the query. Some of these transformations are equivalent to the removal of redundant join operations in the relational algebra; a second way to remove variables is the introduction of "complex projections" which can directly be mapped to operations at the storage access interface of the DBMS.

Copyright © 1990 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Dennis McLeod, Ron Sacks-Davis, Hans-Jörg Schek (Eds.): 16th International Conference on Very Large Data Bases, August 13-16, 1990, Brisbane, Queensland, Australia, Proceedings. Morgan Kaufmann 1990, ISBN 1-55860-149-X


Serge Abiteboul, Catriel Beeri: The Power of Languages for the Manipulation of Complex Values. VLDB J. 4(4): 727-794(1995) BibTeX
Serge Abiteboul, Nicole Bidoit: Non First Normal Form Relations: An Algebra Allowing Data Restructuring. J. Comput. Syst. Sci. 33(3): 361-393(1986) BibTeX
Don S. Batory, J. R. Barnett, J. F. Garza, K. P. Smith, K. Tsukuda, B. C. Twichell, T. E. Wise: GENESIS: An Extensible Database Management System. IEEE Trans. Software Eng. 14(11): 1711-1730(1988) BibTeX
Michael J. Carey, David J. DeWitt, Daniel Frank, Goetz Graefe, M. Muralikrishna, Joel E. Richardson, Eugene J. Shekita: The Architecture of the EXODUS Extensible DBMS. OODBS 1986: 52-65 BibTeX
Peter Dadam, Klaus Küspert, F. Andersen, Henk M. Blanken, R. Erbe, Jürgen Günauer, Vincent Y. Lum, Peter Pistor, Georg Walch: A DBMS Prototype to Support Extended NF2 Relations: An Integrated View on Flat Tables and Hierarchies. SIGMOD Conference 1986: 356-367 BibTeX
C. J. Date: An Introduction to Database Systems, Volume I, 4th Edition. Addison-Wesley 1986
Umeshwar Dayal, Frank Manola, Alejandro P. Buchmann, Upen S. Chakravarthy, David Goldhirsch, Sandra Heiler, Jack A. Orenstein, Arnon Rosenthal: Simplifying Complex Objects: The PROBE Approach to Modelling and Querying Them. BTW 1987: 17-37 BibTeX
Klaus R. Dittrich: Object-Oriented Database Systems: The Notion and the Issue. OODBS 1986: 2-4 BibTeX
Johann Christoph Freytag: A Rule-Based View of Query Optimization. SIGMOD Conference 1987: 173-180 BibTeX
Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984) BibTeX
Volker Linnemann, Klaus Küspert, Peter Dadam, Peter Pistor, R. Erbe, Alfons Kemper, Norbert Südkamp, Georg Walch, Mechtild Wallrath: Design and Implementation of an Extensible Database Management System Supporting User Defined Data Types and Functions. VLDB 1988: 294-305 BibTeX
David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents BibTeX
Nikolaus Ott, Klaus K. Horländer: Removing redundant join operations in queries involving views. Inf. Syst. 10(3): 279-288(1985) BibTeX
Peter Pistor, F. Andersen: Designing A Generalized NF2 Model with an SQL-Type Language Interface. VLDB 1986: 278-285 BibTeX
Mark A. Roth, Henry F. Korth, Abraham Silberschatz: Extended Algebra and Calculus for Nested Relational Databases. ACM Trans. Database Syst. 13(4): 389-417(1988) BibTeX
Michael Stonebraker, Lawrence A. Rowe: The Design of Postgres. SIGMOD Conference 1986: 340-355 BibTeX
Marc H. Scholl: Theoretical Foundation of Algebraic Optimization Utilizing Unnormalized Relations. ICDT 1986: 380-396 BibTeX
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6

Referenced by

  1. Elisa Bertino, Mauro Negri, Giuseppe Pelagatti, Licia Sbattella: Object-Oriented Query Languages: The Notion and the Issues. IEEE Trans. Knowl. Data Eng. 4(3): 223-237(1992)
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:45:44 2009