Query to determine existence of infinate recursion in Access 2003

[No bother]

I have a table with two columns, one named master, the other slave.
Each column has a set of numbers. A number in one column can appear in
the other. I am trying to see if there is any infinite recursion in the
table.

E.g.:

Master Slave
1 2
2 1

Would be a simple example of infinite recursion in this context. This I
can easily detect with a simple self-join. However:

Master Slave
1 2
2 3
3 1

Is a bit harder. Of course the chain can be much longer. I am not as
concerned about the time for the query to work as I am with the accuracy
thereof. My readings on queries and infinite recursion have left me a
bit discouraged.

I don't believe I need the code spelled out for me as much as a pointer
or two.

Thanks.

[Bob Quintal]

No bother <do**@email.me> wrote in
news:sR***************@fe08.lga:

I have a table with two columns, one named master, the other
slave. Each column has a set of numbers. A number in one
column can appear in the other. I am trying to see if there is
any infinite recursion in the table.

E.g.:

Master Slave
1 2
2 1

Would be a simple example of infinite recursion in this
context. This I can easily detect with a simple self-join.
However:

Master Slave
1 2
2 3
3 1

Is a bit harder. Of course the chain can be much longer. I
am not as concerned about the time for the query to work as I
am with the accuracy thereof. My readings on queries and
infinite recursion have left me a bit discouraged.

I don't believe I need the code spelled out for me as much as
a pointer or two.

Thanks.

I coded a BOM explosion module that took an array of recordsets
whch held the slave items for the current master. if the slave
wa a master, increment the array index and load the new
recordset with the slaves of the now master.

Each time you increment the child level, loop through the
array's master field, to see if the new slave is already there.
If it is there you have infinite recursion.

basically:
Dim childs(99) as recordset
Dim pointer as integer

getchilds 1,0

getchilds ( master as integer, level as integer)
childs(level)= currentdb.openrecordset("select slave from table
Where `Master = " & master & ",dbopensnapshot)
with childs(level)
do until .eof
'check for recursion
for pointer = level to 0 step -1
if childs(pointer).master = .slave then
msgbox "We have recursion"
'back out of the loop
end if
next
getchilds slave, (level +1)
loop
end with
childs(level).close
end sub

Ill try to post some of the real code tomorrow from the office.

--
Bob Quintal

PA is y I've altered my email address.

[Matthias Klaey]

No bother <do**@email.me> wrote:

I have a table with two columns, one named master, the other slave.
Each column has a set of numbers. A number in one column can appear in
the other. I am trying to see if there is any infinite recursion in the
table.

E.g.:

Master Slave
1 2
2 1

Would be a simple example of infinite recursion in this context. This I
can easily detect with a simple self-join. However:

Master Slave
1 2
2 3
3 1

Is a bit harder. Of course the chain can be much longer. I am not as
concerned about the time for the query to work as I am with the accuracy
thereof. My readings on queries and infinite recursion have left me a
bit discouraged.

I don't believe I need the code spelled out for me as much as a pointer
or two.

Thanks.

I don't know if you can solve this problem in general with a query. If
you want to check out, google for "CELKO trees BOM" (BOM = Bill of
Materials).

If you want to use code, google for "directed graph strongly connected
component" or "Kosaraju's algorithm".

HTH
Matthias Kläy
--
www.kcc.ch

----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

[Lyle Fairfield]

No bother <do**@email.me> wrote in news:sR***************@fe08.lga:

I have a table with two columns, one named master, the other slave.
Each column has a set of numbers. A number in one column can appear in
the other. I am trying to see if there is any infinite recursion in the
table.

I'd start with something like this. I haven't tested it extensively and
don't know it it will always succeed. I'm not sure about a lot of things.
Would it be faster if the data is loaded into an array? Don't know. If I
were serious about it I would probably use some language which had sparse
arrays, that it where all the elements don't have to contain something
(without any memory being reserved for those empty elements).

Public Sub FindRecursives()
Dim r As ADODB.Recordset
Set r = CurrentProject.Connection.Execute( _
"SELECT Master, Slave, " _
& "IsRecursive(Master, Master) FROM MasterSlave")
Debug.Print
With r
While Not .EOF
Debug.Print .Fields(0).Value, _
.Fields(1).Value, _
CBool(.Fields(2).Value)
.MoveNext
Wend
End With
End Sub

Public Function IsRecursive(Master As Long, Optional Begin As Long) As
Boolean
Static Iterations As Long
Static MaximumIterations As Long
Static Start As Long
If Begin = Master Then
Iterations = 0
MaximumIterations = CurrentProject.Connection.Execute( _
"SELECT COUNT(*) FROM MasterSlave") _
.Fields(0).Value
Start = Master
End If
If Iterations > MaximumIterations Then Exit Function
Master = CurrentProject.Connection.Execute( _
"SELECT Slave FROM MasterSlave " _
& "WHERE Master = " & Master).Fields(0).Value
If Master = Start Then
IsRecursive = True
Else
Iterations = Iterations + 1
IsRecursive = IsRecursive(Master)
End If
End Function

Three runs on slightly different data are given here:
---
1 2 True
2 3 True
3 1 True
---
1 2 True
2 3 True
3 1 True
4 3 False
---
1 3 True
2 3 False
3 1 True
4 3 False

When would this finish for 100 000 records? Probably not in my lifetime.

Interesting Problem. Thanks for sharing it.

And yes, one could use DAO just as well.

--
Lyle Fairfield

[No bother]

Thanks for the help!

I ended up making a little change from:
Master = CurrentProject.Connection.Execute( _
"SELECT Slave FROM MasterSlave " _
& "WHERE Master = " & Master).Fields(0).Value
to
dim r as recordset
r = CurrentProject.Connection.Execute( _
"SELECT Slave FROM MasterSlave " _
& "WHERE Master = " & Master)
if r.recordcount > 0 then
master = r.fields(0).value
....

I also converted this to DAO, but I won't bore the group with the details.

I also found that when executing this that after about five minutes I
would get a message complaining about not being able to open more
databases. I may try again when:
1. I get access (no pun intended) to a Cray or a big iron
2. Access is ported to one of these, either when XP is ported or Access
is ported directly to an OS that runs on one of these

I'm not holding my breath.

On the other hand, maybe Cobol would be up to the task...
Lyle Fairfield wrote:

No bother <do**@email.me> wrote in news:sR***************@fe08.lga:

I have a table with two columns, one named master, the other slave.
Each column has a set of numbers. A number in one column can appear in
the other. I am trying to see if there is any infinite recursion in the
table.

I'd start with something like this. I haven't tested it extensively and
don't know it it will always succeed. I'm not sure about a lot of things.
Would it be faster if the data is loaded into an array? Don't know. If I
were serious about it I would probably use some language which had sparse
arrays, that it where all the elements don't have to contain something
(without any memory being reserved for those empty elements).

Public Sub FindRecursives()
Dim r As ADODB.Recordset
Set r = CurrentProject.Connection.Execute( _
"SELECT Master, Slave, " _
& "IsRecursive(Master, Master) FROM MasterSlave")
Debug.Print
With r
While Not .EOF
Debug.Print .Fields(0).Value, _
.Fields(1).Value, _
CBool(.Fields(2).Value)
.MoveNext
Wend
End With
End Sub

Public Function IsRecursive(Master As Long, Optional Begin As Long) As
Boolean
Static Iterations As Long
Static MaximumIterations As Long
Static Start As Long
If Begin = Master Then
Iterations = 0
MaximumIterations = CurrentProject.Connection.Execute( _
"SELECT COUNT(*) FROM MasterSlave") _
.Fields(0).Value
Start = Master
End If
If Iterations > MaximumIterations Then Exit Function
Master = CurrentProject.Connection.Execute( _
"SELECT Slave FROM MasterSlave " _
& "WHERE Master = " & Master).Fields(0).Value
If Master = Start Then
IsRecursive = True
Else
Iterations = Iterations + 1
IsRecursive = IsRecursive(Master)
End If
End Function

Three runs on slightly different data are given here:
---
1 2 True
2 3 True
3 1 True
---
1 2 True
2 3 True
3 1 True
4 3 False
---
1 3 True
2 3 False
3 1 True
4 3 False

When would this finish for 100 000 records? Probably not in my lifetime.

Interesting Problem. Thanks for sharing it.

And yes, one could use DAO just as well.

[Lyle Fairfield]

No bother <do**@email.me> wrote in news:iq************@fe10.lga:

Thanks for the help!

I ended up making a little change from:
Master = CurrentProject.Connection.Execute( _
"SELECT Slave FROM MasterSlave " _
& "WHERE Master = " & Master).Fields(0).Value
to
dim r as recordset
r = CurrentProject.Connection.Execute( _
"SELECT Slave FROM MasterSlave " _
& "WHERE Master = " & Master)
if r.recordcount > 0 then
master = r.fields(0).value
...

I also converted this to DAO, but I won't bore the group with the
details.

I also found that when executing this that after about five minutes I
would get a message complaining about not being able to open more
databases.

I wonder if ADO uses enough of JET and DAO that it too opens Databases?
Perhaps it does not.

If both DAO and ADO open too many databases then one could pretty easily
map the recordset to an array and do the recursion with it. Probably I
would want to do this with some language which allowed for sparse arrays.
VBA isn't it.

Of course, like everything, too many records would be too much.

[kaniest]

"No bother" <do**@email.me> schreef in bericht
news:sR***************@fe08.lga...

I don't believe I need the code spelled out for me as much as a pointer or
two.

If the recursive version is impracatical, you may try the
traditional iterative way of proving a graph is acyclic, basically:

1. count the number of masters for each node
2. remove all nodes with count = 0
3. decrement count for each slave of each removed node
4. repeat from 2. until al nodes are removed (graph is acyclic)
or no node has count = 0 (graph has at least one cycle)

--
Paul

[kaniest]

Kaniest schreef:

If the recursive version is impracatical, you may try the
traditional iterative way of proving a graph is acyclic, basically:

1. count the number of masters for each node
2. remove all nodes with count = 0
3. decrement count for each slave of each removed node
4. repeat from 2. until al nodes are removed (graph is acyclic)
or no node has count = 0 (graph has at least one cycle)

For nitpickers: of course this applies to directed graphs.

[kaniest]

No bother wrote:

On the other hand, maybe Cobol would be up to the task...

This approach works nicely in Cobol (VBA/DAO version):

'Check the graph in table or query Arrows(tail,head) for cycles
'strategy: remove sinks (work head to tail)
With CurrentDb 'use temp table H1(head)

'make H1 the subset of distinct tails
.Execute _
"SELECT DISTINCT tail AS head INTO H1 FROM Arrows;"

Do While .RecordsAffected
'remove sinks from subgraph A1 with heads in H1
#If Not JET_antics Then
.Execute _
"DELETE * FROM H1 WHERE head NOT IN " & _
"(SELECT tail FROM Arrows WHERE head IN " & _
"(SELECT head FROM H1));"
#Else
.Execute _
"DELETE DISTINCTROW H1.* FROM H1 LEFT JOIN " & _
"[SELECT tail FROM Arrows INNER JOIN " & _
"H1 ON Arrows.head = H1.head]. AS T1 ON H1.head = T1.tail " & _
"WHERE tail Is Null;"
#End If
Loop
'leaves subgraph A1 without sinks (empty or having cycles)

Debug.Print "Cycle(s) present:"; .TableDefs!H1.RecordCount > 0

.Execute _
"DROP TABLE H1;"
End With