A query language for multidimensional arrays: design, implementation, and optimization techniques

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.

REFERENCES

• 1: Arvind , Rishiyur S. Nikhil , Keshav K. Pingali, I-structures: data structures for parallel computing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.4, p.598-632, Oct. 1989 [doi>10.1145/69558.69562]
• 2: H. Barendregt. Lambda Calculus: Its Syntaz and Semantics. North Holland, 1984.
• 3: C. Beeri and D.K.C. Chan. Bounded arrays: a bulk type perspective. Hebrew Univ. Technical Report, 1995.
• 4: P. Buneman. The fast Fourier transform as a database query. Technical Report MS-CIS-93-37/L&C 60, University of Pennsylvania, March 1993.
• 5: Peter Buneman , Susan B. Davidson , Kyle Hart , G. Christian Overton , Limsoon Wong, A Data Transformation System for Biological Data Sources, Proceedings of the 21th International Conference on Very Large Data Bases, p.158-169, September 11-15, 1995
• 6: Peter Buneman , Leonid Libkin , Dan Suciu , Val Tannen , Limsoon Wong, Comprehension syntax, ACM SIGMOD Record, v.23 n.1, p.87-96, March 1994 [doi>10.1145/181550.181564]
• 7: Peter Buneman , Shamim Naqvi , Val Tannen , Limsoon Wong, Principles of programming with complex objects and collection types, Theoretical Computer Science, v.149 n.1, p.3-48, Sept. 18, 1995
• 8: R.G.G. Cattell, ed. The Object Database Standard: ODMG-93. Morgan-Kaufmann, 1994.
• 9: Leonidas Fegaras , David Maier, Towards an effective calculus for object query languages, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.47-58, May 22-25, 1995, San Jose, California, United States
• 10: J. Feo. Arrays in Sisal. in Proc. Workshop on Arrays, Functional Languages and Parallel Systems, L. Mullin et al. eds., Kluwer Academic PubLishers, 1990.
• 11: Sergio Greco , Luigi Palopoli , Eugenio Spadafora, DatalogA: Array Manipulations in a Deductive Database Language, Proceedings of the 4th International Conference on Database Systems for Advanced Applications (DASFAA), p.180-188, April 11-13, 1995
• 12: David Gries, The Science of Programming, Springer-Verlag New York, Inc., Secaucus, NJ, 1987
• 13: Stéphane Grumbach , Tova Milo, Towards tractable algebras for bags, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.49-58, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153855]
• 14: Per Hammarlund , Björn Lisper, On the relation between functional and data parallel programming languages, Proceedings of the conference on Functional programming languages and computer architecture, p.210-219, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165211]
• 15: P. Hudak, S.L. Peyton Jones and P. Wadler. Report on the Programming Language HaskeU. SIGPLAN Notices, March 1992.
• 16: Kenneth E. Iverson, A Programming Language., John Wiley & Sons, 1962
• 17: Bharathi Subramanian , Stanley B. Zdonik , Theodore W. Leung , Scott L. Vandenberg, Ordered Types in the AQUA Data Model, Proceedings of the Fourth International Workshop on Database Programming Languages - Object Models and Languages, p.115-135, August 30-September 01, 1993
• 18: Leonid Libkin , Limsoon Wong, Aggregate Functions, Conservative Extensions, and Linear Orders, Proceedings of the Fourth International Workshop on Database Programming Languages - Object Models and Languages, p.282-294, August 30-September 01, 1993
• 19: Leonid Libkin , Limsoon Wong, Some Properties of Query Languages for Bags, Proceedings of the Fourth International Workshop on Database Programming Languages - Object Models and Languages, p.97-114, August 30-September 01, 1993
• 20: Leonid Libkin , Limsoon Wong, New techniques for studying set languages, bag languages and aggregate functions, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.155-166, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182609]
• 21: Leonid Libkin , Limsoon Wong, Conservativity of nested relational calculi with internal generic functions, Information Processing Letters, v.49 n.6, p.273-280, March 22, 1994 [doi>10.1016/0020-0190(94)90099-X]
• 22: David Maier , Bennet Vance, A call to order, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.1-16, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153851]
• 23: David Maier , David M. Hansen, Bambi Meets Godzilla: Object Databases for Scientific Computing, Proceedings of the Seventh International Working Conference on Scientific and Statistical Database Management, p.176-184, September 28-30, 1994
• 24: Giansalvatore Mecca , Anthony J. Bonner, Sequences, Datalog and transducers, Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.23-35, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.212440]
• 25: Giansalvatore Mecca , Anthony J. Bonner, Finite Query Languages for Sequence Databases, Proceedings of the Fifth International Workshop on Database Programming Languages, p.12, September 06-08, 1995
• 26: Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
• 27: T. More. Axioms and theorems for a theory of arrays. IBM J. Res. and Development 17 (1973), 135-175.
• 28: R. Rew, G. Davis and S. Emmerson. NetGDF User's Guide, Unidata Program Center, 1993.
• 29: Praveen Seshadri , Miron Livny , Raghu Ramakrishnan, Sequence query processing, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.430-441, May 24-27, 1994, Minneapolis, Minnesota, United States
• 30: Praveen Seshadri , Miron Livny , Raghu Ramakrishnan, SEQ: A Model for Sequence Databases, Proceedings of the Eleventh International Conference on Data Engineering, p.232-239, March 06-10, 1995
• 31: Scott Lee Vandenberg, Algebras for object-oriented query languages, University of Wisconsin at Madison, Madison, WI, 1993
• 32: Scott L. Vandenberg , David J. DeWitt, Algebraic support for complex objects with arrays, identity, and inheritance, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.158-167, May 29-31, 1991, Denver, Colorado, United States
• 33: P. Wadler. Comprehending monads. Mathematical Structures in Computer Science 2 (1992), 461-493.
• 34: Limsoon Wong , Peter Buneman, Querying nested collections, 1994

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

General Terms:
Languages, Theory