Circular match

Question

I have a database with three tables: userid_tbl, need_tbl, have_tbl

create table userid_tbl (user_id varchar2(15) not null primary key); create table need_tbl (user_id varchar2(15) not null, have_item varchar2(100) not null, foreign key (user_id) references userid_tbl (user_id) ); create table have_tbl (user_id varchar2(15) not null, have_item varchar2(100) not null, foreign key (user_id) references userid_tbl (user_id) ); 

Each user can create an unlimited number of records of needs or services that they can provide to others in the database. Items from a given list.

After completing the connection with the need and the table, I picked up the needs and wishes and dropped the requests that cannot be fulfilled by any user in a view that looks like this:

 Item: Need: Have: 1 Bob George 2 George Herbie 3 Herbie Bob 4 Larry Wally 5 Wally Larry 6 John George 

Now I am trying to write a query where I can calculate the number of permutations of each user by completing the completed queries. For example, in the example above, Bob, George, and Herbie can do each other together, like Larry and Wally, but John cannot, so the total will be 2.

At first I started doing this with LOOP, but there should be a simpler and less resource-intensive way to do this with a single request.

Answer 1

For detailed explanations, see my blog post:

• Search for loops in a tree

If your users can be found more than once in the needs column of a table, this is a difficult NP task.

If not, specify this query in your view:

 SELECT COUNT(*) FROM v_needs CONNECT BY NOCYCLE need = PRIOR have WHERE CONNECT_BY_ISCYCLE = 1 

CONNECT BY NOCYCLE allows loops inside hierarchical queries ( NOCYCLE just stops the branch when it finds loops, no NOCYCLE returns an error).

CONNECT_BY_ISCYCLE returns true whenever it finds a loop (it returns 1 for a record that would give the root of the current branch in the next iteration).

Please note that this query will give you all users in cycles without grouping them.

To group users, run this query:

 SELECT n.*, CONNECT_BY_ROOT(have), level FROM v_needs n START WITH have IN ( SELECT MIN(have) FROM ( SELECT have, CONNECT_BY_ROOT(have) AS root FROM t_needs START WITH have IN ( SELECT have FROM t_needs n WHERE CONNECT_BY_ISCYCLE = 1 CONNECT BY NOCYCLE needs = PRIOR have ) CONNECT BY NOCYCLE have = PRIOR needs ) GROUP BY root ) CONNECT BY NOCYCLE have = PRIOR needs 

Update:

From your post, I see that you have a limit on the maximum loop length.

This greatly facilitates the solution to this problem.

Just add a loop constraint condition to each of the queries:

 SELECT n.*, CONNECT_BY_ROOT(have), level FROM v_needs n START WITH have IN ( SELECT MIN(have) FROM ( SELECT have, CONNECT_BY_ROOT(have) AS root FROM t_needs START WITH have IN ( SELECT have FROM t_needs n WHERE CONNECT_BY_ISCYCLE = 1 CONNECT BY NOCYCLE needs = PRIOR have AND level <= 5 ) CONNECT BY NOCYCLE have = PRIOR needs AND level <= 5 ) GROUP BY root ) CONNECT BY NOCYCLE have = PRIOR needs AND level <= 5 

This will stop the hierarchy tree from moving at 5th level.

If you have 1,000,000 users in your database, and 5 corresponds to each user on average, the query will have to examine the rows 1,000,000 * 5^5 = 3,125,000,000 , which is the observed number of rows.

The query will be greatly improved if you MATERIALIZE your presentation and create indexes on "need" and "have".

In this case, the request will be completed in a matter of minutes.

Answer 2

This is a great start for me. I hit my head against the wall for several days. Let me give you some more details to make this clearer. Unfortunately, the problem is the clique problem and is NP-complete because all three columns are not unique.

Here's a real-world application: I'm doing a research project on the effectiveness of negative reciprocity, i.e. barter, instead of money exchange, where it is inappropriate or illegal.

A specific example is organ transplantation. Let them say that Bob needs a kidney, and his wife is ready to donate a kidney, there is no guarantee that she will be a match. However, it may be suitable for another user in the database, which in turn can provide Bob with the appropriate kidney.

If I have a database with thousands of recipients and tens of thousands of potential donors, I can potentially complete a multi-user transaction to maximize the benefits for as many recipients as possible.

Obviously, there should be restrictions on the maximum number of levels required to close the cycle. A 5-way transaction is possible, but a 100-position transaction is simply logically impossible.

I have not even heard of Oracle Spatial until today. It looks like it might be the exact product I need to make it easier.