You are viewing a plain text version of this content. The canonical link for it is here.
Posted to derby-user@db.apache.org by John English <jo...@gmail.com> on 2012/10/14 13:52:44 UTC
Getting transitive closure?
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,
--
John English
Re: Getting transitive closure?
Posted by david myers <da...@gmail.com>.
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,
AW: Getting transitive closure?
Posted by Ma...@de.equens.com.
Hi John,
Well I would prefer a structure, that I could put into a Nasi-Schneidermann-Diagramm.
So instead of using while (true) and fleeing out of it like hell with a break or a return I would do something like this:
PreparedStatement stat;
try
{
stat = connection.prepareStatement(
"SELECT * FROM " + tableName +
" WHERE " + keyCol + " NOT IN (" + parentList + ")" +
" AND " + parentCol + " IN (" + parentList + ")"
while(res.next())
{
//
// Process the current row
//
processRow(res);
//
// Add the ID of the current row to
// the list of parent rows
//
parentList += "," + res.getInt(keyCol);
}
catch (exception ex)
{
...
}
finally
{
stat.close();
}
Best regards,
Malte
-----Ursprüngliche Nachricht-----
Von: John English [mailto:john.foreign@gmail.com]
Gesendet: Montag, 15. Oktober 2012 12:02
An: derby-user@db.apache.org
Betreff: Re: Getting transitive closure?
Best solution I've been able to come up with is this, which does N selects where N is the path length from the start to the furthest leaf. Can anyone suggest anything better?
/**
* Process all descendants of a specified row in a table
* with a recursive key relationship. A method "processRow"
* is called to process each row as it is found in some
* unspecified manner.
*
* @param connection
* the database connection to use.
* @param tableName
* the name of the recursive table.
* @param keyCol
* the name of the primary key column. This is assumed
* to be an integer.
* @param parentCol
* the name of the column identifying the parent row.
* This row should be a foreign key to "keyCol" in
* the same table.
* @param keyCol
* the name of the primary key column.
* @param start
* the number of the row to start the descent from.
*/
public void processDescendants (Connection connection,
String tableName,
String keyCol,
String parentCol,
int start)
throws SQLException {
String parentList = "" + start;
//
// Loop until there are no more results,
// then return from inside the loop
//
while (true) {
try (PreparedStatement stat = connection.prepareStatement(
"SELECT * FROM " + tableName +
" WHERE " + keyCol + " NOT IN (" + parentList + ")" +
" AND " + parentCol + " IN (" + parentList + ")"
)) {
try (ResultSet res = stat.execute()) {
if (res.next()) {
//
// Results found, so process them
//
do {
//
// Process the current row
//
processRow(res);
//
// Add the ID of the current row to
// the list of parent rows
//
parentList += "," + res.getInt(keyCol);
}
while (res.next());
}
else {
//
// No unprocessed rows found, so return
//
return;
}
}
}
}
}
--
John English
Re: Getting transitive closure?
Posted by John English <jo...@gmail.com>.
Best solution I've been able to come up with is this, which
does N selects where N is the path length from the start
to the furthest leaf. Can anyone suggest anything better?
/**
* Process all descendants of a specified row in a table
* with a recursive key relationship. A method "processRow"
* is called to process each row as it is found in some
* unspecified manner.
*
* @param connection
* the database connection to use.
* @param tableName
* the name of the recursive table.
* @param keyCol
* the name of the primary key column. This is assumed
* to be an integer.
* @param parentCol
* the name of the column identifying the parent row.
* This row should be a foreign key to "keyCol" in
* the same table.
* @param keyCol
* the name of the primary key column.
* @param start
* the number of the row to start the descent from.
*/
public void processDescendants (Connection connection,
String tableName,
String keyCol,
String parentCol,
int start)
throws SQLException {
String parentList = "" + start;
//
// Loop until there are no more results,
// then return from inside the loop
//
while (true) {
try (PreparedStatement stat = connection.prepareStatement(
"SELECT * FROM " + tableName +
" WHERE " + keyCol + " NOT IN (" + parentList + ")" +
" AND " + parentCol + " IN (" + parentList + ")"
)) {
try (ResultSet res = stat.execute()) {
if (res.next()) {
//
// Results found, so process them
//
do {
//
// Process the current row
//
processRow(res);
//
// Add the ID of the current row to
// the list of parent rows
//
parentList += "," + res.getInt(keyCol);
}
while (res.next());
}
else {
//
// No unprocessed rows found, so return
//
return;
}
}
}
}
}
--
John English
Re: Getting transitive closure?
Posted by Katherine Marsden <km...@sbcglobal.net>.
On 10/14/2012 6:34 AM, John English wrote:
> On 14/10/2012 14:45, José Ventura wrote:
>> I might be mistaken, but I think Derby does not support this
>> out-of-the-box. There are, however, a few interesting solutions
>> suggested in this (2009) thread:
>>
>> http://old.nabble.com/Recursive-query-on-common-table-td25819772.html
>
> Thanks! I'm now in the process or recursively trying to construct the
> transitive closure of all the possible approaches that this page links
> to... :-)
>
Doesn't help right now, but you may also wish to vote for
https://issues.apache.org/jira/browse/DERBY-11. This was an early
request but I think pretty hard to implement and I am not sure if there
is a SQL standard syntax.
Re: Getting transitive closure?
Posted by John English <jo...@gmail.com>.
On 14/10/2012 14:45, José Ventura wrote:
> I might be mistaken, but I think Derby does not support this
> out-of-the-box. There are, however, a few interesting solutions
> suggested in this (2009) thread:
>
> http://old.nabble.com/Recursive-query-on-common-table-td25819772.html
Thanks! I'm now in the process or recursively trying to construct the
transitive closure of all the possible approaches that this page links
to... :-)
--
John English
Re: Getting transitive closure?
Posted by José Ventura <st...@gmail.com>.
I might be mistaken, but I think Derby does not support this
out-of-the-box. There are, however, a few interesting solutions suggested
in this (2009) thread:
http://old.nabble.com/Recursive-query-on-common-table-td25819772.html
On Sun, Oct 14, 2012 at 8:52 AM, John English <jo...@gmail.com>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,
> --
> John English
>
Re: Getting transitive closure?
Posted by John English <jo...@gmail.com>.
On 14/10/2012 14:37, John I. Moore, Jr. wrote:
> John,
>
> I suggest that you take a look at Warshall's Algorithm.
Thanks, I'm familiar with Warshall's algorithm. What I'm trying to avoid
is issuing gazillions of selects; I thought there might be a clever
tricky SQL way of doing this that I haven't been able to think of.
--
John English
RE: Getting transitive closure?
Posted by "John I. Moore, Jr." <so...@att.net>.
John,
I suggest that you take a look at Warshall's Algorithm. See, for example,
http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm. Google Warshall's Algorithm for
additional links.
_________________________________________
John I. Moore, Jr.
SoftMoore Consulting
email: jmoore@softmoore.com
web: www.softmoore.com
cell: 843-906-7887
> -----Original Message-----
> From: John English [mailto:john.foreign@gmail.com]
> Sent: Sunday, October 14, 2012 7:53 AM
> To: Derby Discussion
> Subject: Getting transitive closure?
>
> 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,
> --
> John English