3

I have a database table like following:

column 1 | column 2

x | Y

y | z

z | x

So basically x->y->z->x.

Now I have to detect such entries in the DB. One solution could be take these entries and make a graph in memory and then detect the cycle with a cycle finding algorithm. I would rather do it with an SQL query if possible though.

Bill Karwin
  • 538,548
  • 86
  • 673
  • 828
xtrmcode
  • 61
  • 5
  • 1
    What RDBMS are you on? Different ones have different abilities to deal with a tree structure in the first place. The ones that support recursive queries, though, tend to throw exceptions if they encounter cyclic behavior, so you may be looking at some form of stored procedure. – Clockwork-Muse Dec 07 '12 at 17:33
  • 1
    sqlite is not very good in understanding that stuff. I would aim using the application layer above for that. – Najzero Dec 07 '12 at 17:53
  • how would you suggest to do that ? – xtrmcode Dec 07 '12 at 17:58

1 Answers1

1

SQLite does not support recursive queries, so the best you can do is to detect cycles of fixed length using self-joins. You can't detect cycles of arbitrary length.

Here's an example of a join that finds cycles of length 2, like the example you showed in your question.

SELECT ...
FROM t AS t0
JOIN t AS t1 ON t0.column2 = t1.column1
JOIN t AS t2 ON t1.column2 = t2.column1
WHERE t2.column2 = t0.column1

Re your comment:

If you need to detect cycles of arbitrary length, all I can suggest is that you must store more than the direct links. You must also store the transitive closure, i.e. every path through your graphs. That's the best way to make this search efficient. Of course it takes a lot more storage space to do that, but there's your tradeoff. And it takes less extra space than you think.

I've done a transitive closure design for trees, but not acyclic graphs. See my answer to What is the most efficient/elegant way to parse a flat table into a tree? or my presentation Models for Hierarchical Data with SQL.

Community
  • 1
  • 1
Bill Karwin
  • 538,548
  • 86
  • 673
  • 828
  • ok I got your point. but i need to detect arbitrary length cycles. any suggestion on how i can do it efficiently ? – xtrmcode Dec 07 '12 at 18:02