A Query Language for Multidimensional Arrays: Design, Implementation, and Optimization Techniques.

@inproceedings{DBLP:conf/sigmod/LibkinMW96,
  author    = {Leonid Libkin and
               Rona Machlin and
               Limsoon Wong},
  editor    = {H. V. Jagadish and
               Inderpal Singh Mumick},
  title     = {A Query Language for Multidimensional Arrays: Design, Implementation,
               and Optimization Techniques},
  booktitle = {Proceedings of the 1996 ACM SIGMOD International Conference on
               Management of Data, Montreal, Quebec, Canada, June 4-6, 1996},
  publisher = {ACM Press},
  year      = {1996},
  pages     = {228-239},
  ee        = {http://doi.acm.org/10.1145/233269.233335, db/conf/sigmod/LibkinMW96.html},
  crossref  = {DBLP:conf/sigmod/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

While much recent research has focussed on extending databases beyond the traditional relational model, relatively little has been done to develop database tools for querying data organized in (multidimensional) arrays. The scientific computing community has made little use of available database technology. Instead, multidimensional scientific data is typically stored in local files conforming to various data exchange formats and queried via specialized access libraries tied in to general purpose programming languages.

To allow such data to be queried using known database techniques, we design and implement a query language for multidimensional arrays. Our main design decision is to treat arrays as functions from index sets to values rather than as collection types. This leads to clean syntax and semantics as well as simple but powerful optimization rules.

We present a calculus for arrays that extends standard calculi for complex objects. We derive a higher-level comprehension style query language based on this calculus and describe its implementation, including a data driver for the NetCDF data exchange format. Next, we explore some optimization rules obtained from the equational laws of our core calculus. Finally, we study the expressiveness of our calculus and prove that it essentially corresponds to adding ranking to a query language for complex objects.

Copyright © 1996 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.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...

• 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/smod9397 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

Online Edition: ACM Digital Library

References

[1]

Arvind, Rishiyur S. Nikhil, Keshav Pingali: I-Structures: Data Structures for Parallel Computing. ACM Trans. Program. Lang. Syst. 11(4): 598-632(1989) BibTeX

[2]

...

[3]

...

[4]

...

[5]

Peter Buneman, Susan B. Davidson, Kyle Hart, G. Christian Overton, Limsoon Wong: A Data Transformation System for Biological Data Sources. VLDB 1995: 158-169 BibTeX

[6]

Peter Buneman, Leonid Libkin, Dan Suciu, Val Tannen, Limsoon Wong: Comprehension Syntax. SIGMOD Record 23(1): 87-96(1994) BibTeX

[7]

Peter Buneman, Shamim A. Naqvi, Val Tannen, Limsoon Wong: Principles of Programming with Complex Objects and Collection Types. Theor. Comput. Sci. 149(1): 3-48(1995) BibTeX

[8]

R. G. G. Cattell: The Object Database Standard: ODMG-93 (Release 1.1). Morgan Kaufmann 1994
BibTeX

[9]

Leonidas Fegaras, David Maier: Towards an Effective Calculus for Object Query Languages. SIGMOD Conference 1995: 47-58 BibTeX

[10]

...

[11]

Sergio Greco, Luigi Palopoli, Eugenio Spadafora: Datalog^A: Array Manipulations in a Deductive Database Language. DASFAA 1995: 180-188 BibTeX

[12]

David Gries: The Science of Programming. Springer 1981
BibTeX

[13]

Stéphane Grumbach, Tova Milo: Towards Tractable Algebras for Bags. PODS 1993: 49-58 BibTeX

[14]

P. Hammarlund, Björn Lisper: On the Relation between Functional and Data Parallel Programming Languages. FPCA 1993: 210-222 BibTeX

[15]

...

[16]

...

[17]

Bharathi Subramanian, Stanley B. Zdonik, Theodore W. Leung, Scott L. Vandenberg: Ordered Types in the AQUA Data Model. DBPL 1993: 115-135 BibTeX

[18]

Leonid Libkin, Limsoon Wong: Aggregate Functions, Conservative Extensions, and Linear Orders. DBPL 1993: 282-294 BibTeX

[19]

Leonid Libkin, Limsoon Wong: Some Properties of Query Languages for Bags. DBPL 1993: 97-114 BibTeX

[20]

Leonid Libkin, Limsoon Wong: New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions. PODS 1994: 155-166 BibTeX

[21]

Leonid Libkin, Limsoon Wong: Conservativity of Nested Relational Calculi with Internal Generic Functions. Inf. Process. Lett. 49(6): 273-280(1994) BibTeX

[22]

David Maier, Bennet Vance: A Call to Order. PODS 1993: 1-16 BibTeX

[23]

David Maier, David M. Hansen: Bambi Meets Godzilla: Object Databases for Scientific Computing. SSDBM 1994: 176-184 BibTeX

[24]

Giansalvatore Mecca, Anthony J. Bonner: Sequences, Datalog and Transducers. PODS 1995: 23-35 BibTeX

[25]

Giansalvatore Mecca, Anthony J. Bonner: Finite Query Languages for Sequence Databases. DBPL 1995: 12 BibTeX

[26]

...

[27]

...

[28]

...

[29]

Praveen Seshadri, Miron Livny, Raghu Ramakrishnan: Sequence Query Processing. SIGMOD Conference 1994: 430-441 BibTeX

[30]

Praveen Seshadri, Miron Livny, Raghu Ramakrishnan: SEQ: A Model for Sequence Databases. ICDE 1995: 232-239 BibTeX

[31]

...

[32]

Scott L. Vandenberg, David J. DeWitt: Algebraic Support for Complex Objects with Arrays, Identity, and Inheritance. SIGMOD Conference 1991: 158-167 BibTeX

[33]

...

[34]

Limsoon Wong: Querying Nested Collections. Ph.D. thesis, Univ. Pennsylvania 1994
BibTeX