Damjan and Tony, I have been involved on a project with a similar
scalability issue wrt self-joins. Of course I can't divulge the detail
but you might want to concentrate your reading on the Oracle Analytic
Functions (in particular "lead" and "lag").
Edwina Peirson
eupeirson_at_removeme.hotmail.com
"Damjan S. Vujnovic" <damjan_at_NOSPAMgaleb.etf.bg.ac.yu> wrote in message news:<argb7n$eve$1_at_news.etf.bg.ac.yu>...
> > Mike, I think you have solved the approach. I couldn't fathom how to
> > get around the 'loop' problem with the CONNECT BY PRIOR clause until
> > seeing your code. All I have to do now is code the routines in a
> > generic sense (another table with shape connectivities that may want
> > to search for) so that I can, arbitrarly, count the number of
> > triangles, rectangles, pentagons, shapes with triangles and rectangles
> > in them, shapes with rectangles and only one triangle but no
> > pentagons ...
>
> If:
>
> 1. Any two points in a shape can be connected (i.e. the shape can be
> arbitrary complex)
> 2. You want to count the number of n-agons (n=3, 4, 5, 6, ...) in a given
> shape.
>
> then you are facing the problem with "(worst case) exponential time
> complexity" (example: try finding number 20-agons in 40-agon). I hope you
> have some background knowledge about algorithms. Suppose you have to count
> (manually) number of rectangles in a given shape (you can try with 6 nodes,
> each two connected). Try to model the process in your brain when attempting
> to find all of them (rectangles), and you'll find out that it's some kind of
> backtracking.
> Next, take a look at the following query (I assume that both touples
> (node, nextnode_linkedlist), (node, nextnode_linkedlist)
> were inserted, so I'm dividing count(*) with 8):
>
> SELECT (s1.shapeID) as shapeID, (count(*)/8) as numberOfRectangles
> FROM tblshapes s1, tblshapes s2, tblshapes s3, tblshapes s4
> WHERE s1.shapeID = s2.shapeID AND
> s2.shapeID = s3.shapeID AND
> s3.shapeID = s4.shapeID AND
> s1.nextnode_linkedlist = s2.node AND
> s2.nextnode_linkedlist = s3.node AND
> s3.nextnode_linkedlist = s4.node AND
> s4.nextnode_linkedlist = s1.node AND
> NOT s1.node = s2.node AND
> NOT s2.node = s3.node AND
> NOT s3.node = s4.node AND
> NOT s4.node = s1.node
> GROUP BY s1.shapeID
>
> Those self-joins are pure simulation of backtracking in SQL and there is no
> substantially different approach, regarding time-complexity, not syntax(it
> cant't be done faster than this unless some limitations on the shape
> complexity are introduced). Generating this query programmatically is quite
> simple and you can also extend it for the general case...
>
> Regards,
> Damjan S. Vujnovic
>
> University of Belgrade
> School of Electrical Engineering
> Department of Computer Engineering & Informatics
> Belgrade, Yugoslavia
>
> http://galeb.etf.bg.ac.yu/~damjan/
>
> P.S. Btw, you can make some optimizations:
>
> SELECT (s1.shapeID) as shapeID, count(*) as numberOfRectangles
> FROM tblshapes s1, tblshapes s2, tblshapes s3, tblshapes s4
> WHERE s1.shapeID = s2.shapeID AND
> s2.shapeID = s3.shapeID AND
> s3.shapeID = s4.shapeID AND
> s1.nextnode_linkedlist = s2.node AND
> s2.nextnode_linkedlist = s3.node AND
> s3.nextnode_linkedlist = s4.node AND
> s4.nextnode_linkedlist = s1.node AND
> s1.node < s2.node AND
> s1.node < s3.node AND
> s1.node < s4.node AND
> s2.node < s4.node AND
> NOT s2.node = s3.node AND
> NOT s3.node = s4.node
> GROUP BY s1.shapeID
Received on Sun Nov 24 2002 - 10:36:22 CST
