CONNECT BY application - Oracle SQL - DFS search without repeating lines

Question

CONNECT BY application - Oracle SQL - DFS search without repeating lines

Navigation

#1 by (0 votes)
#2 by (0 votes)
#3 by (0 votes)

0

Dear, Suppose a graph is registered in two ways:

TABELA_A:

T | V1 | V2

1 | 1  | 2

2 | 2  | 3

3 | 2  | 4

4 | 4  | 5

TABELA_B:

T | V1 | V2

1 | 1  | 2

2 | 2  | 3

3 | 4  | 2 <====OBSERVEM QUE AQUI INVERTI OS VÉRTICES

4 | 4  | 5

That said, I need to read so that I scan all the "T" edges, but without looping or even reading a portion more than once.

For table A, the solution is simple:

SELECT v1, 
       v2 
FROM   tabela_a 
CONNECT BY NOCYCLE PRIOR b2 = b1

On the other hand, the solution to TABLE_B becomes a bit more complex. Especially for analogous situations but with an excessively large amount of edges. For this reason, I stress the need to read each section only once ("edge"). A "grotesque" but effective solution for cases with few edges that it proposes, it is summarized as:

SELECT DISTINCT <== observe que tentei o   DISTINCT, 
                mas sem efeitos eficientes v1, 
                v2 
FROM tabela_a connect BY nocycle (prior b2 = b1) 
OR prior b2 = b2 ) 
OR prior b1 = b2 ) 
OR (prior b1 = b1 )

The example presented is merely illustrative. The case in my hands consists of more than 10,000 lines and with these cases of "inversion". Nothing less, I need to scan the graph following the logic of the DFS (depth first search) algorithm, similar to what happens in reading TABLE_A, but with possible inversions as presented. The solution to read TABLE_B is bad, because it reads the same passage countless times and then filters the singles (through DISTINCT). This is bad as it makes the process very slow.

sql

asked by anonymous 31.08.2018 / 23:23

3 answers

Shopping cart with a value less than 1 I can not load a js file from a child theme -Wordpress

score 0 · Answer 1

SELECT DISTINCT a1.v1, 
                a1.v2 
  FROM tabela_a a1
 WHERE NOT EXISTS (SELECT 1
                    FROM tabela_a a2
                   WHERE a1.v1 = a2.v2
                     AND a1.v2 = a2.v1
                     AND a2.T < a1.T);

score 0 · Answer 2

@MarcosMessias:

Interesting the solution. But each table requires a particular solution. Both describe a same graph, where the "T" column names the edges and the columns "V1" and "V2" name the vertices of each edge. In the table "TABLE_A", using the solution presented (my first solution), navigation will occur as follows: (1 - 2) = > (2-4) = > (4-5) = > (2 - 3) - Search in Depth. The same solution to the table "TABLE_B" will be: (1 - 2) = > (2 - 3) - will stop here, because "PRIOR V2 = V1" is used, that is, for there to be a connection in this logic, the next step must have its vertex "V1" equal to the vertex "V2" of its sum. But, if you observe, excerpt (4-2) is connected, but the logic initially proposed is not able to identify. I need a solution that performs the following reading without repeating bits (edges): (1-2) = > (4-2) = > (4-5) = > (2-3) - Search in Depth. If possible, I advise you to draw the tree described in the tables (which is the same) and how navigation occurs, I think this will help to understand the problem proposed. Thanks for the availability.

score 0 · Answer 3

Good afternoon, David.

I've created the following table to test the select you need:

CREATE TABLE TABELA_TESTE_DAVID (
   T  NUMBER(4) NOT NULL,
   V1 NUMBER(4) NOT NULL,
   V2 NUMBER(4) NOT NULL
);

And I've put the following query to solve your question:

SELECT DISTINCT t.t, t.v1, t.v2
  FROM TABELA_TESTE_DAVID t
 WHERE t.t in (SELECT t3.t
                 FROM TABELA_TESTE_DAVID t3
                WHERE NOT EXISTS (SELECT 1
                         FROM TABELA_TESTE_DAVID t2
                        WHERE t3.v1 = t2.v2
                          AND t3.v2 = t2.v1
                          AND t2.T < t3.T))
CONNECT BY NOCYCLE PRIOR t.v2 = t.v1
        OR t.v2 = t.v2
        OR t.v1 = t.v2
        OR t.v1 = t.v1

I do not know if I understand your problem exactly, but see if the solution I've created meets your need. The sub-select within WHERE filters only the unique combinations of v1 and v2 and the main select connects them.

I hope I have helped.