FQL(ID:993/fql001)

Functional query language 

Functional database language.

Structures:
References:
  • Buneman, P., and Frankel, R.E. "FQL--A functional query langauge" view details Abstract: An applicative language based upon recent ideas by John Backus has been developed. The language provides a powerful formalism for the expression of complex database queries. Though currently implemented with an interface to a CODASYL system, the language employs a sufficiently general data model that use with other database management systems is possible. This paper describes the language through a number of examples and outlines its implementation.


          in [ACM SIGMOD] Proceedings of the 1979 ACM SIGMOD international conference on Management of Data, Boston, Mass., May 30-June 1, 1979 view details
  • Buneman, Peter; Frankel, Robert E.; Nikhil, Rishiyur "An Implementation Technique for Database Query Languages", ACM Trans Database Sys 7(2):164-186 (June 1982). view details
          in [ACM SIGMOD] Proceedings of the 1979 ACM SIGMOD international conference on Management of Data, Boston, Mass., May 30-June 1, 1979 view details
  • Dayal, U. review of Buneman 1982 view details Abstract: The paper describes a technique for processing database queries written in an applicative query language, FQL. (The reader requires no prior knowledge of FQL to follow the paper, since the salient features of the language are reviewed.) The technique is based on the "lazy" evaluation of operations such as selection, join, and arithmetic operations. This means that the operands of an operation are not completely materialized before the operation begins; instead, the operands are "streamed" on request, one tuple (record) at a time. Thus, one operation need not finish before the next begins. This implies that intermediate results need not be stored. (Of course, as the authors point out in a section on extensions to the basic technique, the result of evaluating a common subexpression may be stored to avoid re-evaluation.)

    The lazy evaluation technique is not entirely new. Indeed, it is very similar to the "pipelined" processing of Mary join queries in relational database management systems. The reader will find it useful to compare this technique with the techniques of tuple substitution in INGRES1, threading in QBE2, not materializing results of intermediate joins in System R3, and pipelining in ADAPLEX LDM4.

    The main contribution of the paper is that it describes the technique in generality for arithmetic and Boolean operations, and for operations on programs, in addition to database operations. It provides a set of primitive operations and functions, using which a query processing strategy can be specified as an applicative (functional) program. Not all database operations are covered by these primitives; sorting, for instance, is not. The paper does not address the problem of query optimization, i.e., the problem of finding the cheapest strategy for processing a given query. However, that is a separable problem. Once the optimal strategy is found, it can be specified and executed using the primitives defined in the paper.

    REFERENCES
    [1] WONG, E.; AND YOUSSEF I., K. Decomposition -- a strategy for query processing, ACM Trans. Database Syst. I (1976), 223-24 1.
    [2] Private communication with M. M. Zloof, IBM T. J. Watson Research center, Yorktown Heights, NY.
    [3] SELINGER, P. ET AL. Access path selection in a relational database management system, Proc. ACM-SIGMOD International Conference on Management of Data, AcM, New York, 1979, 23-34.
    [4] RlES, D. ET AL. Decompilarion, oprimizarion, and pipelining for ADAPLEX: a procedural language. Tech. Report, computer corp. Of America, Cambridge, MA, in preparation.

          in ACM Computing Reviews August 1982 view details
  • Schlageter, G.; Rieskamp, M.; Prädel, U.; Unland, R. "The network query language NOAH" view details Abstract: A non-procedural query language for network databases is described. The language is very powerful as compared to other implemented languages. It allows to formulate complex queries which, among other things, include conditions for CODASYL-sets and conditions for n:m-relationships. Cyclic database structures can be processed to some extent.Note: This report is not written for the "naive" user of NOAH, and is not meant to replace a NOAH manual. Instead, this report describes the foundations, the underlying concepts, and the structure of the language in more theoretically oriented, technical terms.This research was performed at the university of Hagen, West Germany, and was partially supported by Triumph Adler AG, Nürnberg, West Germany. Extract: Historical survey
    FQL is presented as an "applicative language" which is not restricted to CODASYL-databases. In FQL the database is seen as a set of functions over various data types. Complex queries can be formulated by the use of mechanisms to combine functions and by standard functions. The language is by far more powerful than NOAH. However, FQL is not an end-user language but is meant to be an intermediate language or a tool for those who wish to construct complex queries. An early version of FQL seems to be implemented. DAPLEX is a proposal for an end-user language based on FQL. Because of the intention of FOL and because of the fact that FQL would hardly be‘implementable on a very small computer, FQL should not be compared with NOAH.
          in Proceedings of the 1982 ACM SIGMOD International Conference on Management of Data (Orlando, Florida, June 1982) view details
  • Batory , D. S.; Leung, T. Y.; Wise, T. E. "Implementation concepts for an extensible data model and data language" TODS 13(3) Sep 1988 view details
          in Proceedings of the 1982 ACM SIGMOD International Conference on Management of Data (Orlando, Florida, June 1982) view details
  • Peter Schäuble and Beat Wüthrich "On the expressive power of query languages" ACM Transactions on Information Systems (TOIS) 12(1) January 1994 pp69-91 view details Abstract: Two main topics are addressed. First, an algebraic approach is presented to define a general notion of expressive power. Heterogeneous algebras represent information systems and morphisms represent the correspondences between the instances of databases, the correspondences between answers, and the correspondences between queries. An important feature of this new notion of expressive power is that query languages of different types can be compared with respect to their expressive power. In the case of relational query languages, the new notion of expressive power is shown to be equivalent to the notion used by Chandra and Harel. In the case of nonrelational query languages, the versatility of the new notion of expressive power is demonstrated by comparing the fixpoint query languages with an object-oriented query language called FQL. The expressive power of the Functional Query Language FQL is the second main topic of this paper. The specifications of FQL functions can be recursive or even mutually recursive, FQL has a fixpoint semantics based on a complete lattice consisting of bag functions. The query language FQL is shown to be more expressive than the fixpoint query languages. This result implies that FQL is also more expressive than Datalog with stratified negation. Examples of recursive FQL functions are given that determine the ancestors of persons and the bill of materials. DOI
          in Proceedings of the 1982 ACM SIGMOD International Conference on Management of Data (Orlando, Florida, June 1982) view details