Mailing-List: contact derby-user-help@db.apache.org; run by ezmlm
Precedence: bulk
Reply-To: "Derby Discussion" <derby-user@db.apache.org>
Received-SPF: pass (athena.apache.org: domain of
 david.myers.scibearspace@gmail.com designates 74.125.83.44 as permitted
 sender)
Message-ID: <507ACCD7.9010200@gmail.com>
Date: Sun, 14 Oct 2012 16:31:51 +0200
From: david myers <david.myers.scibearspace@gmail.com>
User-Agent: Mozilla/5.0 (X11; Linux x86_64;
 rv:15.0) Gecko/20120912 Thunderbird/15.0.1
MIME-Version: 1.0
To: Derby Discussion <derby-user@db.apache.org>
Subject: Re: Getting transitive closure?
References: <507AA78C.7050003@gmail.com>
In-Reply-To: <507AA78C.7050003@gmail.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

Hi all,

I learnt something today. COOL.

So I had a quick look to understand what a weighted graph was see: 
http://www.informatics.susx.ac.uk/courses/dats/notes/html/node130.html

Then I had a look at the 
http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm link 
provided by John Moore.

My line is in Gene / Protein analysis / bioinformatics, and both of 
these seem to have a sort of a relation to the BLAST (Basic Local 
Alignment Search Tool) algorithm (see 
http://www.ebi.ac.uk/2can/tutorials/protein/blast.html).

I wonder if the result of a Warshall Algorithm can give more than one 
result with the same "score" If the use of the BLAST could be 
interesting to find the common paths, which could then be treated as 
"single" nodes, with the intention of rerunning the Warshall using these 
common nodes more often.

I only add this in as I thought other may find it interesting, I 
certainly did.

Thanks for an interesting thread.

David


On 14/10/12 13:52, John English wrote:
> If I have a table defined like so:
>
>   create table COMPONENTS (
>     ID          integer       generated always as identity,
>     COMPONENT   varchar(255)  not null,
>     PARENT      integer,
>     constraint COMPONENTS_PK  primary key (ID),
>     constraint COMPONENTS_1   foreign key (PARENT)
>                               references COMPONENTS(ID)
>                               on delete cascade
>   );
>
> with (for example):
>
>   insert into COMPONENTS(COMPONENT,PARENT) values
>      ('IC package',null),    -- ID = 1
>      ('Flip-flop',1),        -- ID = 2
>      ('D-type',2),           -- ID = 3
>      ('JK flip-flop',2),     -- ID = 4
>      ('7474 dual D-type flip-flop',3),
>      ('4013 dual CMOS D-type flip-flop',3),
>      ('7476 dual JK flip-flop with preset and clear',4),
>      ('4027 dual CMOS JK flip-flop',4);
>
> Is there a clever an efficient way to get the set of all flip-flop 
> packages, i.e. ID=2, all items with parent=2, and so on down the chain 
> of descendants? Or in other words, the transitive closure of the set?
>
> TIA,