Comprehending Queries

Grust, Torsten

Comprehending Queries

Dateien

312_1.pdfGröße: 1.02 MBDownloads: 27502

Datum

1999

Autor:innen

Grust, Torsten

URI (zitierfähiger Link)

http://nbn-resolving.de/urn:nbn:de:bsz:352-opus-3120

Link zur Lizenz

Urheberrechtlich geschützt

Open Access-Veröffentlichung

Open Access Green

Sammlungen

Mathematik und Statistik

Publikationstyp

Dissertation

Publikationsstatus

Published

Zusammenfassung

This text describes a world in which datatypes determine the
comprehension of database queries. In this world, a datatype is
characterized by its algebra of value constructors. These algebras
are principal. Query operators are secondary in the sense that they
simply box (recursive) programs that describe how to form a query
result by application of datatype constructors. Often, operators will
be unboxed to inspect and possibly rewrite these programs. Query
optimization then means to deal with the transformation of programs.

The predominant role of the constructor algebras suggests that this
model understands queries as mappings between such algebras. The key
observation that makes the whole approach viable is that (a)
homomorphic mappings are expressive enough to cover declarative
query languages like OQL or SQL dialects, and, at the same time, (b) a
single program form suffices to express homomorphisms between
constructor algebras.

Reliance on a single combining form, catamorphisms, renders the query
programs susceptible to Constructive Algorithmics, an effective and
extensive algebraic theory of program transformations.

The text then takes a step towards a higher-level query representation
based on the categorical notion of monads, the monad comprehension
calculus. Built on top of the monad notion, the calculus maps a
variety of query constructs to few syntactic forms. The uniformity of
the calculus facilitates the analysis and transformation, especially
the normalization, of its expressions. Few but generic calculus
rewriting rules suffice to implement query transformations that would
otherwise require extensive rule sets.

The text rediscovers well-known query optimization knowledge on
sometimes unusual paths that are more practicable to follow for an
optimizer, though. Solutions previously proposed by others can be
simplified and generalized mainly due to the clear account of the
structure of queries that the monad

Zusammenfassung in einer weiteren Sprache

Dieser Text beschreibt eine Welt, in der Datentypen das Verständnis
von Datenbankanfragen bestimmen. Innerhalb dieser Welt wird ein
Datentyp durch die Algebra seiner Konstruktoren beschrieben. Diese
Konstruktoralgebren sind zentral. Operatoren hingegen sind
zweitrangig: ein Operator ist lediglich eine Box in der ein
(rekursives) Programm eingekapselt ist, welches die Berechnung von
Anfrageergebnissen durch die Anwendung von Konstruktoren beschreibt.
Oft werden wir diese Box aufbrechen, um das Verhalten des
Operators genauer zu studieren oder sein internes Programm zu
transformieren. Anfrageoptimierung bedeutet dann vor allem, sich mit
Programmtransformationen auseinanderzusetzen.

In einer Welt, die durch Datentypen und ihre Konstruktoralgebren
charakterisiert ist, sind Anfragen Abbildungen zwischen diesen
Algebren. Zwei Beobachtungen machen diese Sicht auf Anfragen
praktikabel: (a) schon die Homomorphismen zwischen Konstruktoralgebren
sind ausdrucksstark genug, um Anfragesprachen wie OQL oder
SQL-Dialekte zu begreifen und (b) gleichzeitig ist eine Programmform
ausreichend, um diese Homomorphismen zu implementieren. Der
disziplinierte Einsatz dieser Programmform, die Catamorphismen, macht
die Programme zugänglich für die Constructive Algorithmics, eine
umfassende und effektive algebraische Theorie der
Programmtransformation.

Der nächste Schritt führt dann von Catamorphismen zu einer
Anfragedarstellung, die auf dem kategoriellen Begriff der Monade
basiert. Monaden besitzen exakt die algebraische Struktur, die für die
Interpretation eines generischen Anfragekalküls, dem Monad
Comprehension Kalkül, notwendig ist. Der Monad Comprehension Kalkül
erlaubt lediglich eine geringe Anzahl syntaktischer Formen, die jedoch
ein breites Spektrum von Anfragekonstrukten uniform abbilden können.
Die Analyse, Transformation und Normalisierung der Ausdrücke dieses
Kalküls profitiert signifikant von dieser Uniformität. Wenige
generische Transformationsr

Fachgebiet (DDC)

510 Mathematik

Schlagwörter

Programmtransformation, Anfragerepraesentation, database query optimization, query representation, program transformation, category theory, monad comprehensions

Zitieren

ISO 690

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

BibTex

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

RDF

<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/709">
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-22T17:45:35Z</dcterms:available>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
    <dcterms:title>Comprehending Queries</dcterms:title>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/709/1/312_1.pdf"/>
    <dc:format>application/pdf</dc:format>
    <dc:creator>Grust, Torsten</dc:creator>
    <dcterms:abstract xml:lang="eng">This text describes a world in which datatypes determine the&lt;br /&gt;comprehension of database queries.  In this world, a datatype is&lt;br /&gt;characterized by its algebra of value constructors.  These algebras&lt;br /&gt;are principal.  Query operators are secondary in the sense that they&lt;br /&gt;simply box (recursive) programs that describe how to form a query&lt;br /&gt;result by application of datatype constructors.  Often, operators will&lt;br /&gt;be unboxed to inspect and possibly rewrite these programs.  Query&lt;br /&gt;optimization then means to deal with the transformation of programs.&lt;br /&gt;&lt;br /&gt;The predominant role of the constructor algebras suggests that this&lt;br /&gt;model understands queries as mappings between such algebras.  The key&lt;br /&gt;observation that makes the whole approach viable is that (a)&lt;br /&gt;homomorphic mappings are expressive enough to cover declarative&lt;br /&gt;query languages like OQL or SQL dialects, and, at the same time, (b) a&lt;br /&gt;single program form suffices to express homomorphisms between&lt;br /&gt;constructor algebras.&lt;br /&gt;&lt;br /&gt;Reliance on a single combining form, catamorphisms, renders the query&lt;br /&gt;programs susceptible to Constructive Algorithmics, an effective and&lt;br /&gt;extensive algebraic theory of program transformations.&lt;br /&gt;&lt;br /&gt;The text then takes a step towards a higher-level query representation&lt;br /&gt;based on the categorical notion of monads, the monad comprehension&lt;br /&gt;calculus.  Built on top of the monad notion, the calculus maps a&lt;br /&gt;variety of query constructs to few syntactic forms.  The uniformity of&lt;br /&gt;the calculus facilitates the analysis and transformation, especially&lt;br /&gt;the normalization, of its expressions.  Few but generic calculus&lt;br /&gt;rewriting rules suffice to implement query transformations that would&lt;br /&gt;otherwise require extensive rule sets.&lt;br /&gt;&lt;br /&gt;The text rediscovers well-known query optimization knowledge on&lt;br /&gt;sometimes unusual paths that are more practicable to follow for an&lt;br /&gt;optimizer, though.  Solutions previously proposed by others can be&lt;br /&gt;simplified and generalized mainly due to the clear account of the&lt;br /&gt;structure of queries that the monad</dcterms:abstract>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
    <dc:contributor>Grust, Torsten</dc:contributor>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/709"/>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:rights>terms-of-use</dc:rights>
    <dc:language>eng</dc:language>
    <dcterms:issued>1999</dcterms:issued>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-22T17:45:35Z</dc:date>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/709/1/312_1.pdf"/>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
  </rdf:Description>
</rdf:RDF>

Prüfungsdatum der Dissertation

September 30, 1999