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

Question

---

Dear Members, 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 perform the reading so that I scan all the "T" edges, but without looping or even if it occurs reading a stretch 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 for TABELA_B becomes a little more complex. Mainly for analogous situations but with an excessively larger amount of edges. That is why I emphasize the need to read only once each passage ("edge"). A "grotesque" but effective solution for cases with few edges that I proposed, boils down to:

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 I have at hand 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 search algorithm (Depth first search), similar to what occurs in reading TABELA_A, but with possible inversions as shown. The solution to read TABELA_B is bad, because it reads the same stretch numerous times and then filters the singular (through DISTINCT). This is bad because it makes the process too slow.

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);

Answer 2

@Marcosmessias:

Interesting solution. However, each table requires a particular solution. Both describe the same graph, in which the column "T" names the edges and the columns "V1" and "V2" name the vertices of each edge. In table "TABELA_A", using the solution presented ( my first solution ), the navigation will occur as follows : (1 - 2) => (2 - 4) => (4 - 5) => (2 - 3) - Depth Search. The same solution for the table "TABELA_B" will be : (1 - 2) => (2 - 3) - will stop here, because it is used "PRIOR V2 = V1", that is, for there to be connection in this logic the next section must have its vertex "V1" equal to the vertex "V2" of its amount. But, if observed, the passage (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 excerpts (edges) :(1-2) => ( 4-2) => (4-5) => (2-3) - Depth Search. If possible, I advise you to draw the tree described in the tables ( which is the same) and how the navigation occurs, I think this will help to understand the proposed problem. Thank you for your time.

Answer 3

Good afternoon, David.

I 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 put together the following query to try 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 don’t know if I understand exactly your problem, but see if the solution I 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’ve helped.