Comprehending Queries

Cite This

Files in this item

Checksum: MD5:5f0e8618497d961413ded07086fbca93

GRUST, Torsten, 1999. Comprehending Queries [Dissertation]. Konstanz: University of Konstanz

@phdthesis{Grust1999Compr-709, title={Comprehending Queries}, year={1999}, author={Grust, Torsten}, address={Konstanz}, school={Universität Konstanz} }

terms-of-use Grust, Torsten 2011-03-22T17:45:35Z 1999 Grust, Torsten Comprehending Queries application/pdf eng This text describes a world in which datatypes determine the<br />comprehension of database queries. In this world, a datatype is<br />characterized by its algebra of value constructors. These algebras<br />are principal. Query operators are secondary in the sense that they<br />simply box (recursive) programs that describe how to form a query<br />result by application of datatype constructors. Often, operators will<br />be unboxed to inspect and possibly rewrite these programs. Query<br />optimization then means to deal with the transformation of programs.<br /><br />The predominant role of the constructor algebras suggests that this<br />model understands queries as mappings between such algebras. The key<br />observation that makes the whole approach viable is that (a)<br />homomorphic mappings are expressive enough to cover declarative<br />query languages like OQL or SQL dialects, and, at the same time, (b) a<br />single program form suffices to express homomorphisms between<br />constructor algebras.<br /><br />Reliance on a single combining form, catamorphisms, renders the query<br />programs susceptible to Constructive Algorithmics, an effective and<br />extensive algebraic theory of program transformations.<br /><br />The text then takes a step towards a higher-level query representation<br />based on the categorical notion of monads, the monad comprehension<br />calculus. Built on top of the monad notion, the calculus maps a<br />variety of query constructs to few syntactic forms. The uniformity of<br />the calculus facilitates the analysis and transformation, especially<br />the normalization, of its expressions. Few but generic calculus<br />rewriting rules suffice to implement query transformations that would<br />otherwise require extensive rule sets.<br /><br />The text rediscovers well-known query optimization knowledge on<br />sometimes unusual paths that are more practicable to follow for an<br />optimizer, though. Solutions previously proposed by others can be<br />simplified and generalized mainly due to the clear account of the<br />structure of queries that the monad 2011-03-22T17:45:35Z

Downloads since Oct 1, 2014 (Information about access statistics)

312_1.pdf 27716

This item appears in the following Collection(s)

Search KOPS


My Account