Second-Order Signature: A Tool for Specifying Data Models, Query Processing, and Optimization

Ralf Hartmut Güting

Praktische Informatik IV, FernUniversität Hagen, Postfach 940, D-5800 Hagen, Germany


Institut für Informationssysteme, Departement Informatik, ETH Zürich, Switzerland

Abstract: We propose a framework for the specification of extensible database systems. A particular goal is to implement a software component for parsing and rule-based optimization that can be used with widely varying data models and query languages as well as representation and query processing systems. The key idea is to use second-order signature (and algebra), a system of two coupled many-sorted signatures, where the top-level signature offers kinds and type constructors and the bottom-level signature provides polymorphic operations over the types defined as terms of the top level. Hence the top level can be used to define a data or representation model and the bottom level to describe a query algebra or a query processing algebra. We show the applicability of this framework by examples drawn from relational modeling and query processing.

Keywords: Type system, algebra, signature, polymorphism, functional programming, extensibility, data model, query processing, optimization

This work was done during a sabbatical stay at the Institut für Informationssysteme, ETH Zürich.

Published: Proc. ACM SIGMOD Conf. (Washington, May 1993), 277-286.