Re: Help writing SQL query

From: Damjan S. Vujnovic <damjan_at_NOSPAMgaleb.etf.bg.ac.yu>
Date: Wed, 20 Nov 2002 16:52:51 -0800
Message-ID: <argb7n$eve$1@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:

Any two points in a shape can be connected (i.e. the shape can be arbitrary complex)
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 Wed Nov 20 2002 - 18:52:51 CST