Christopher Browne wrote:
> Christopher Browne wrote
> 
>>I whiteboarded a couple of attempts at algorithms for this, this
>>afternoon.  It needs a bit more thought, I think, to come up with
>>something final...

> Here's what I have at this point...
> 
> The notion that seems to make sense, here, is to construct all of the
> possible maximum-length paths from each origin.  Note that this is a
> loose mix of C-like and pl/pgsql-like code; I'm not yet expecting it to
> be exactly right...
<snipped algorithm>

> That gives us a list of all the longest possible traversals.
Hm.. I don't really understand that algorithm (But, then, maybe
if've just been up for too long now.. ;-) ). Where is that
quantity-value coming from, and what does it do?

In the meantime I've coded up something myself. My first attempt
was to generate all traversals (not just the ones with maximum length),
and store them in a table (I used an array-valued field instead of a
second table vpath, but thats just a detail). This seems to work, basically,
but performance was horrible (For a fully-meshed graph with 10 nodes,
it would need to generate 10! (10 faktorial = 10*9*...*1) entries... :-(

Therefore, I came up with another idea. Here it is, in pseudocode.
foreach node as x
   foreach possible provider of x as y
     Temporarily remove x from the graph
     zs <- All nodes that are somehow connected to y, via one or more nodes
     foreach node in zs as z
       If x subscribes a set from z with provider != z
         do nothing
       else
         Add (receiver=x, provider=y, origin=z) to sl_listen.

The idea is that, if I want to figure out if a node x can use
a neighbour y as a provider for events from some node z, I have
to check if y can receive events from z assuming the node x doesn't even
exists. If it can, than y is used as a provider, otherwise it is not.

Attachted is a sql-script that creates a few tables, creates two functions
that implement this algorithm in plpgsql. Below the functions there a few
testcases. It uses it's own tables, with different names than slony for now,
because this made the development and testing easier.

create_listen contains the 3 nested for-loops, while the set-valued function
reachable_from(starting_node, nodes_to_ignore) check with nodes are reachable
from the starting_node when the nodes in nodes_to_ignore are, well, ignored ;-)

I used the columns src, dst and via instead of origin, receiver and provider (
Or src and dst instead of server and client in the case if sl_path).

Does anyone see a case where this would fail? If not, I'll try to
fit this into slony, and see if it workes for my case.

> *Maybe* at this point, we remove the traversals that contain cases where
> a node is subscribing to a set originating from the origin, but that
> goes around the shaping of the subscription sets.  Possibly that could
> get handled in the loop where the feasible paths were being selected...
> 
> We then walk backwards through them to generate listener entries; I'll
> not bother looking at that until proper holes have been shot in the above...

greetings, Florian Pflug

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: dolisten.sql
Url: http://gborg.postgresql.org/pipermail/slony1-general/attachments/20060303/812fcccb/dolisten-0001.ksh