A calculus for collections and aggregates
Lecture notes in computer sciencePublished 1 January 1997
Kazem Lellahi, Val Tannen
Citations33
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A calculus that should play for database query languages the same role that the lambda calculus plays for functional programming, and a new concept: monads enriched with algebraic structure is introduced.
Abstract
We present a calculus that should play for database query languages the same role that the lambda calculus plays for functional programming. For the semantic foundations of the calculus we introduce a new concept: monads enriched with algebraic structure. We model collection types through enriched monads and aggregate operations through enriched monad algebras. The calculus derives program equivalences that underlie a good number of the optimizations used in query languages.
Keywords
Computer Science
Graduate texts in mathematicsCategories for the Working Mathematician
8,983 Citations1971Saunders Mac Lane
Information and ComputationNotions of computation and monads
1,711 Citations1991Eugenio Moggi
Calculi are introduced, based on a categorical semantics for computations, that provide a correct basis for proving equivalence of programs for a wide range of notions of computation.
Journal of Symbolic LogicIntroduction to Higher Order Categorical Logic.
1,100 Citations1989J. L. Bell, J. Lambek +1 more
Grundlehren der mathematischen WissenschaftenToposes, Triples and Theories
755 Citations1985Michael Barr, Charles Wells
Lecture notes in computer scienceFunctional programming with bananas, lenses, envelopes and barbed wire
510 Citations1991Erik Meijer, Maarten M. Fokkinga +1 more
A calculus for lazy functional programming based on recursion operators associated with data type definitions is developed and it is shown that all example functions in Bird and Wadler's Introduction to Functional Programming can be expressed using these operators.
A short cut to deforestation
415 Citations1993Andrew Gill, John Launchbury +1 more
This work proposes an automatic technique for improving theiency of programs, by removing many of these intermediate lists, based on a single, simple, local transformation.
Illinois Journal of MathematicsAdjoint functors and triples
384 Citations1965Samuel Eilenberg, John C. Moore
Theoretical Computer SciencePrinciples of programming with complex objects and collection types
261 Citations1995Peter Buneman, Shamim A. Naqvi +2 more
A new principle for the development of database query languages that the primitive operations should be organized around types is presented, in which a number of well-known languages are to be found as natural sublanguages.
Mathematical Structures in Computer ScienceComprehending monads
171 Citations1992Philip Wadler
It is shown how list comprehensions may be generalised to an arbitrary monad, and how the resulting programming feature can concisely express in a pure functional language some programs that manipulate state, handle exceptions, parse text, or invoke continuations.
Lecture notes in computer scienceNaturally embedded query languages
151 Citations1992Val Breazu-Tannen, Peter Buneman +1 more
A progression of sublanguages in this paradigm that have increasing expressive power are described, and robust conceptual restrictions are illustrated thus exhibiting interesting additional properties.
Lecture notes in computer scienceLogical and computational aspects of programming with sets/bags/lists
87 Citations1991Val Breazu-Tannen, Ramesh Subrahmanyam
Back-and-forth translations between the two presentations of the list, bag, and set datatypes are established, from which it follows that they are equally expressive, and results relating proofs of program properties, in the two presentation are established.
Towards an effective calculus for object query languages
86 Citations1995Leonidas Fegaras, David Maier
The monoid calculus is presented, and its effectiveness for object-oriented query languages, exemplified by OQL of ODMG-93 is argued, and it is shown how to extend the monoids to deal with vectors and arrays in more expressive ways than current query languages do.
Comprehensions, a query notation for DBPLs
79 Citations1992Phil Trinder
This paper argues that comprehensions, a construct found in some programming languages, are a good query notation for DBPLs and shows that, like many other query notations, comprehensions can be smoothly integrated into DBPL's and allow queries to be expressed clearly, concisely and efficiently.
Normal forms and conservative properties for query languages over collection types
63 Citations1993Limsoon Wong
This work generalizes Paredaens and Van Gucht's to all i and o, providing a counterpart to the theorem of Grumbach and Vianu, and strong normalization results are obtained for a general language for collection types.
Scholarly Commons (University of Pennsylvania)Querying Nested Collections
58 Citations1994Limsoon Wong, Peter Buneman
This dissertation investigates a new approach to query languages inspired by structural recursion and by the categorical notion of a monad, which provides easy answers to several hitherto unresolved conjectures on query languages that are more realistic than the flat relational algebra.
Workshops in computingSome Properties of Query Languages for Bags
52 Citations1994Leonid Libkin, Limsoon Wong
It is proved that achieveing the power of BQL in the relational language amounts to adding simple arithmetic to the latter, and it is found that relational languages equivalent to BQL with powerbag and structural recursion/bounded loop are found.
Workshops in computingAggregate Functions, Conservative Extension, and Linear Orders
32 Citations1994Leonid Libkin, Limsoon Wong
A nested relational language NRC(=) is introduced based on monads and structural recursion that is naturally embedded in functional languages, readily extensible, and it has a compact equational theory.
Lecture notes in computer scienceOn the power of simple diagrams
13 Citations1996Roberto Di Cosmo
A set of abstract lemmas that are easy to apply and turn out to be quite valuable in order to establish confluence and/or normalization modularly, especially when adding rewriting rules for extensional equalities to various calculi are focused on.
Theoretical Computer ScienceMonads and algebras in the semantics of partial data types
12 Citations1992Philip S. Mulry
This paper focuses attention on the use of algebraic structures, particularly categories of algebras and monads, to describe partial data types and their corresponding computations to lead to greater code reuse, reliability and maintenance.
Lecture notes in computer science(Relational) programming laws in the boom hierarchy of types
10 Citations1993Paul Hoogendijk
It is demonstrated that the basic rules and calculational techniques used in two extensively documented program derivation methods can be expressed, and can be generalised within a relational theory of datatypes.