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

@inproceedings{DBLP:conf/vldb/SudkampL90,
  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, http://dblp.uni-trier.de}
}

Abstract

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 NF² 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 NF² 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

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/vldb8997 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

References

[1]

Serge Abiteboul, Catriel Beeri: The Power of Languages for the Manipulation of Complex Values. VLDB J. 4(4): 727-794(1995)

[2]

Serge Abiteboul, Nicole Bidoit: Non First Normal Form Relations: An Algebra Allowing Data Restructuring. J. Comput. Syst. Sci. 33(3): 361-393(1986)

[3]

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)

[4]

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

[5]

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

[6]

...

[7]

...

[8]

C. J. Date: An Introduction to Database Systems, Volume I, 4th Edition. Addison-Wesley 1986

[9]

...

[10]

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

[11]

Klaus R. Dittrich: Object-Oriented Database Systems: The Notion and the Issue. OODBS 1986: 2-4

[12]

Johann Christoph Freytag: A Rule-Based View of Query Optimization. SIGMOD Conference 1987: 173-180

[13]

...

[14]

...

[15]

...

[16]

Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)

[17]

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

[18]

David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents

[19]

Nikolaus Ott, Klaus K. Horländer: Removing redundant join operations in queries involving views. Inf. Syst. 10(3): 279-288(1985)

[20]

Peter Pistor, F. Andersen: Designing A Generalized NF2 Model with an SQL-Type Language Interface. VLDB 1986: 278-285

[21]

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)

[22]

Michael Stonebraker, Lawrence A. Rowe: The Design of Postgres. SIGMOD Conference 1986: 340-355

[23]

...

[24]

Marc H. Scholl: Theoretical Foundation of Algebraic Optimization Utilizing Unnormalized Relations. ICDT 1986: 380-396

[25]

...

[26]

Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6