Re: [Help-glpk] Building set of sets from plain set - efficient implementation

[Andrew Makhorin]

>>> set T{k in K, i in I} := setof{(i,j,k,l,m) in S} (j,m,l);
>>> This is implemented in Mathprog as follows:
>>> for all k in K do
>>> {   for all i in I do
>>>    {   T[k,i] := empty;
>>>        for all (i',j,k',l,m) in S do
>>>        {   if i' = i and k' = k then
>>>               T[k,i] := T[k,i] union {(j,m,l)}
>>>        }
>>>    }
>>>}
> as you remarked this implementation is not efficient. I suggest the
> following implementation that will work in O(n log(n)) time:

> 1.) Enumerate the superset {k in K, i in I} domain and collect it into a
> list ( O(n) )
> 2.) Sort the list ( O(n log(n)) )
> 3.) Iterate through the subset domain {(i,j,k,l,m) in S} ( O(n) )
> 3a.) Find the corresponding entry in the list ( O( n log(n)) )
> 3b.) Append the subset entry to the list entry ( O(n)) )
> 4.) Insert the collected sets from the list into the superset ( O(n)) )

> Hence no special syntax is needed.

This would be easy in a programming language. However, in Mathprog
the statement:

set T{k in K, i in I} := setof{(i,j,k,l,m) in S} (j,m,l);

is translated in something like the following procedure:

procedure T(k in K, i in I)
{   find T[k,i] in T array;
    if T[k,i] is not found then
    {  T[k,i] := setof{(i,j,k,l,m) in S} (j,m,l);
       add T[k,i] to T array;
    }
    return T[k,i];
}

which is called every time on evaluating set expressions containing
references to members of T. Note that initially the T array is empty.

To evaluate all members of T efficiently it is necessary to carry
out the loop 'setof{(i,j,k,l,m) in S}' from the procedure, that is
impossible.

My idea is to use S to create fake data, i.e. as if there were the
following block in the data section:

T[...,...] = ... ... ... ;
T[...,...] = ... ... ... ... ... ;
T[...,...] = ... ... ;

and then to "read" these data into T. Of course, no actual i/o will
be performed.

Do you know if there is a similar operation in the sql language?