Re: Yet another relational programming language

From: Tegiri Nenashi <tegirinenashi_at_gmail.com>
Date: Wed, 26 Aug 2009 06:56:47 -0700 (PDT)
Message-ID: <0f4abfd6-0227-4bf2-b6e3-01807b286656_at_z4g2000prh.googlegroups.com>


On Aug 25, 11:05 pm, Troels Arvin <tro..._at_arvin.dk> wrote:
> I think that a
> link to an accessible relational lattice introduction (which many
> examples!) would be good.

I tweaked the link so that the most accessible article (http:// arxiv.org/pdf/cs/0501053v3) shows up at the top, thank you. Perhaps, QBQL itself would be the best introduction to RL with many examples...

> Can SQL table functions handle infinity?

It could be handled via pipelined execution. Here is exert from "SQL Design patterns book":

Table Function
^^^^^^^^^^^^^

Either way, the previous solution looks ridiculous to anybody with little programming background. Integers can be created on the fly so easily, why does one have to refer to some stored relation, let alone a view over several tables? The idea of relations which can be manufactured with code as opposed to stored relations leads to the concept of Table Function. A table function is a piece of procedural code that can produce a result which can be understood by the SQL engine -- that is, a relation! Table function can have a parameter, so that the output relation depends on it. For all practical purposes it looks like a Parameterized View, and it is even called this way in the SQL Server world. The Integers view is naturally parameterized with an upper bound value.

The Table Function concept evolved further to embrace the idea of pipelining. From logical perspective, pipelining doesn’t change anything: the table function output is still a relation. The function, however, doesn’t require materializing the whole relation at once; it supplies rows one by one along with consumer’s demand. This implementation difference, however, have a significant implication in our case. The integers relation is infinite! By no means can one hope materializing it in all entirety, hence the upper bound parameter in non-pipelined version mentioned in the previous paragraph.

The size of the pipelined table function output, however, doesn’t necessarily have to be controlled by purely logical means. A row’s producer (table function) is in intricate relationship with a row’s consumer (the enclosing SQL query), and there is a way for the consumer to tell the producer to stop.

Figure 2.1: A producer generates integers in an infinite loop. As soon as an integer is built, it is shipped to a consumer. After digesting 5 integers the consumer decides that it had enough.

Let’s write such table function producing infinite list of integers and see what happens:
CREATE TYPE IntSet AS TABLE OF Integer;

CREATE or replace FUNCTION Integers
  RETURN IntSet PIPELINED IS
BEGIN
    loop

       PIPE ROW(0);
    end loop;
END;
/
Each table function is required to define the shape of the output it produces as an object type. We declared IntSet as a list of integers. The function implementation is unbelievably simple: the flow of control enters infinite loop, where it creates a new output row during each iteration. Since the function is capable producing a list of 0s only, it is the calling SQL query’s responsibility to have a pseudo column expression that assigns integers incrementally. Alternatively, we could have a slightly more verbose Integers table function with a counter variable incremented during each loop iteration which pipes that integer to the output.

How do we use the Integers table function? Just select rownum from Table(Integers)
would do, although we have to be careful. A typical client programmatic interface allows opening a cursor, and fetching the result set row by row. Normally, the client would stop when it exhausts the result set. In this case, the result set is infinite, so that the client has to decide by itself when to stop. Of course, the decision when to stop can be moved to server side, and made explicit select rownum from Table(Integers)
where rownum < 1000

When designing a pipelined Integers function we neglected a rather popular alternative. Many would find it natural for the Integers function to have an argument which specifies an upper limit in the range of generated integers. For example, Integers(5) returns the list 1,2,3,4,5. Then, the last could be reformulated in terms of this new function without the predicate
select rownum from Table(Integers(1000)) Which style is better?

Suppose somebody unfamiliar with the Integers function implementation asks:
What is the maximum number in the list of integers produced by this query?
Predicate rownum <= 1000 makes the answer to the question immediate, while with the function parameter it might be 1000, 999, or even 21000 – it is impossible to tell for sure without examining the Integers function implementation.

The case when one would need raw or only slightly cooked list of integers is relatively simple. If the integers relation is a part of more complex query, it would require a more elaborate analysis to decide whether the query would terminate without explicit server-side stop condition. Received on Wed Aug 26 2009 - 15:56:47 CEST

Original text of this message