db-derby-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From david myers <david.myers.scibearsp...@gmail.com>
Subject Re: Getting transitive closure?
Date Sun, 14 Oct 2012 14:31:51 GMT
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,


Mime
View raw message