Query Processing Techniques in the Summary-Table-by-Example Database Query Language.

@article{DBLP:journals/tods/OzsoyogluMO89,
  author    = {Gultekin {\"O}zsoyoglu and
               Victor Matos and
               Z. Meral {\"O}zsoyoglu},
  title     = {Query Processing Techniques in the Summary-Table-by-Example Database
               Query Language},
  journal   = {ACM Trans. Database Syst.},
  volume    = {14},
  number    = {4},
  year      = {1989},
  pages     = {526-573},
  ee        = {http://doi.acm.org/10.1145/76902.76906, db/journals/tods/OzsoyogluMO89.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Summary-Table-by-Example (STBE) is a graphical language suitable for statistical database applications. STBE queries have a hierarchical subquery structure and manipulate summary tables and relations with set-valued attributes.

The hierarchical arrangement of STBE queries naturally implies a tuple-by-tuple subquery evaluation strategy (similar to the nested loops join implementation technique) which may not be the best query processing strategy. In this paper we discuss the query processing techniques used in STBE. We first convert an STBE query into an "extended" relational algebra (ERA) expression. Two transformations are introduced to remove the hierarchical arrangement of subqueries so that query optimization is possible. To solve the "empty partition" problem of aggregate function evaluation, directional join (one-sided outer-join) is utilized. We give the algebraic properties of the ERA operators to obtain an "improved" ERA expression. Finally we briefly discuss the generation of alternative implementations of a given ERA expression.

STBE is implemented in a prototype statistical database management system. We discuss the STBE-related features of the implemented system.

Copyright © 1989 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society 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/An3-1 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/aDVD2 or /dvd

References

[1]

...

[2]

Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
BibTeX

[3]

Paul Chan, Arie Shoshani: SUBJECT: A Directory Driven System for Organizing and Accessing Large Statistical Databases. VLDB 1981: 553-563 BibTeX

[4]

E. F. Codd: Relational Completeness of Data Base Sublanguages. In: R. Rustin (ed.): Database Systems: 65-98, Prentice Hall and IBM Research Report RJ 987, San Jose, California : (1972) BibTeX

[5]

E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) BibTeX

[6]

...

[7]

...

[8]

...

[9]

Allen Van Gelder, Rodney W. Topor: Safety and Correct Translation of Relational Calculus Formulas. PODS 1987: 313-327 BibTeX

[10]

...

[11]

...

[12]

...

[13]

Rowland R. Johnson: Modelling Summary Data. SIGMOD Conference 1981: 93-97 BibTeX

[14]

Won Kim: On Optimizing an SQL-like Nested Query. ACM Trans. Database Syst. 7(3): 443-469(1982) BibTeX

[15]

...

[16]

Anthony C. Klug: Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions. J. ACM 29(3): 699-717(1982) BibTeX

[17]

Anthony C. Klug: Access Paths in the 'ABE' Statistical Query Facility. SIGMOD Conference 1982: 161-173 BibTeX

[18]

...

[19]

...

[20]

...

[21]

...

[22]

...

[23]

...

[24]

John L. McCarthy: Metadata Management for Large Statistical Databases. VLDB 1982: 234-243 BibTeX

[25]

...

[26]

...

[27]

Gultekin Özsoyoglu, Z. Meral Özsoyoglu, Francisco Mata: A Language and a Physical Organization Technique for Summary Tables. SIGMOD Conference 1985: 3-16 BibTeX

[28]

Gultekin Özsoyoglu, Z. Meral Özsoyoglu, Victor Matos: Extending Relational Algebra and Relational Calculus with Set-Valued Attributes and Aggregate Functions. ACM Trans. Database Syst. 12(4): 566-592(1987) BibTeX

[29]

...

[30]

...

[31]

Z. Meral Özsoyoglu, Gultekin Özsoyoglu: Summary-Table-By-Example: A Database Query Language for Manipulating Summary Data. ICDE 1984: 193-202 BibTeX

[32]

...

[33]

Z. Meral Özsoyoglu, Gultekin Özsoyoglu: A Query Language for Statistical Databases. Query Processing in Database Systems 1985: 171-187 BibTeX

[34]

Gultekin Özsoyoglu, Z. Meral Özsoyoglu: Statistical Database Query Languages. IEEE Trans. Software Eng. 11(10): 1071-1081(1985) BibTeX

[35]

Gultekin Özsoyoglu, Huaqing Wang: A Relational Calculus with Set Operators, Its Safety and Equivalent Graphical Languages. IEEE Trans. Software Eng. 15(9): 1038-1052(1989) BibTeX

[36]

Arnon Rosenthal, David S. Reiner: Extending the Algebraic Framework of Query Processing to Handle Outerjoins. VLDB 1984: 334-343 BibTeX

[37]

H. Sato: Handling Summary Information in a Database: Derivability. SIGMOD Conference 1981: 98-107 BibTeX

[38]

Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 BibTeX

[39]

Arie Shoshani: Statistical Databases: Characteristics, Problems, and some Solutions. VLDB 1982: 208-222 BibTeX

[40]

...

[41]

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

[42]

...

[43]

Moshé M. Zloof: Query-by-Example: A Data Base Language. IBM Systems Journal 16(4): 324-343(1977) BibTeX

[44]

...

[45]

Gerhard Jaeschke, Hans-Jörg Schek: Remarks on the Algebra of Non First Normal Form Relations. PODS 1982: 124-138 BibTeX

Referenced by

1. César A. Galindo-Legaria, Arnon Rosenthal: Outerjoin Simplification and Reordering for Query Optimization. ACM Trans. Database Syst. 22(1): 43-73(1997)
2. Nevzat Hurkan Balkir, Eser Sükan, Gultekin Özsoyoglu, Z. Meral Özsoyoglu: VISUAL: A Graphical Icon-Based Query Language. ICDE 1996: 524-533
3. Qi Yang, Chengwen Liu, Jing Wu, Clement T. Yu, Son Dao, Hiroshi Nakajima: Efficient Processing of Nested Fuzzy SQL Queries. ICDE 1995: 131-138
4. Jason Tsong-Li Wang, Kaizhong Zhang, Karpjoo Jeong, Dennis Shasha: A System for Approximate Tree Matching. IEEE Trans. Knowl. Data Eng. 6(4): 559-571(1994)
5. Gultekin Özsoyoglu, Z. Meral Özsoyoglu, Kumar V. Vadaparty: A Scientific Database System for Polymers and Materials Engineering Needs. SSDBM 1994: 138-148
6. César A. Galindo-Legaria: Outerjoins as Disjunctions. SIGMOD Conference 1994: 348-358
7. Rosine Cicchetti, Lotfi Lakhal: Matrix-Relation for Statistical Database Management. EDBT 1994: 31-44
8. Kumar V. Vadaparty, Y. Alp Aslandogan, Gultekin Özsoyoglu: Towards a Unified Visual Database Access. SIGMOD Conference 1993: 357-366
9. Priti Mishra, Margaret H. Eich: Join Processing in Relational Databases. ACM Comput. Surv. 24(1): 63-113(1992)
10. César A. Galindo-Legaria, Arnon Rosenthal: How to Extend a Conventional Optimizer to Handle One- and Two-Sided Outerjoin. ICDE 1992: 402-409
11. Gultekin Özsoyoglu, Wen-Chi Hou, Adegbemiga Ola: Database Systems for Programmable Logic Controllers. SSDBM 1990: 183-199
12. Arnon Rosenthal, César A. Galindo-Legaria: Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins. SIGMOD Conference 1990: 291-299