재귀 서브 쿼리 팩터링을 사용한 사이클 검출
https://stackoverflow.com/questions/1731889
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
Oracle SQL은 구문 별 독점 연결을 사용하여 V2 이후 계층 적 쿼리를 수행 할 수 있습니다. 최신 11G Release 2에서 그들은 재귀와의 재귀 서브 쿼리 팩터링을 추가하여 절편으로도 추가했습니다. 이것은 ANSI 표준이며, 올바르게 이해하면 다른 RDBMS 공급 업체도 구현되었습니다.
Connect-by를 재귀와 비교할 때 사이클 감지를 사용할 때 결과 세트의 차이가 있음을 알았습니다. 결과에 의한 연결은 나에게 더 직관적이므로 Oracle의 구현에 버그가 포함되어 있는지 또는 이것이 표준 ANSI 및 예상 동작인지 궁금합니다. 따라서 내 질문은 MySQL, DB2, SQL Server 및 기타와 같은 다른 데이터베이스를 사용하여 쿼리로 재귀를 확인할 수 있는지 여부입니다. 이러한 데이터베이스가 물론 재귀를 지원하는 경우.
다음은 Oracle 11.2.0.1.0에서 작동하는 방법입니다
SQL> select *
2 from t
3 /
ID PARENT_ID
---------- ----------
1 2
2 1
2 rows selected.
Syntax의 Connect를 사용한 쿼리 :
SQL> select id
2 , parent_id
3 , connect_by_iscycle
4 from t
5 connect by nocycle parent_id = prior id
6 start with id = 1
7 /
ID PARENT_ID CONNECT_BY_ISCYCLE
---------- ---------- ------------------
1 2 0
2 1 1
2 rows selected.
나에게 직관적 인 것처럼 보입니다. 그러나 새로운 ANSI 구문을 사용하면 한 줄을 더 반환합니다.
SQL> with tr (id,parent_id) as
2 ( select id
3 , parent_id
4 from t
5 where id = 1
6 union all
7 select t.id
8 , t.parent_id
9 from t
10 join tr on t.parent_id = tr.id
11 ) cycle id set is_cycle to '1' default '0'
12 select id
13 , parent_id
14 , is_cycle
15 from tr
16 /
ID PARENT_ID I
---------- ---------- -
1 2 0
2 1 0
1 2 1
3 rows selected.
이것은 확인하는 데 사용할 수있는 스크립트입니다.
create table t
( id number
, parent_id number
);
insert into t values (1, 2);
insert into t values (2, 1);
commit;
with tr (id,parent_id) as
( select id
, parent_id
from t
where id = 1
union all
select t.id
, t.parent_id
from t
join tr on t.parent_id = tr.id
) cycle id set is_cycle to '1' default '0'
select id
, parent_id
, is_cycle
from tr;
해결책
문서에서 CONNECT_BY_ISCYCLE:
그만큼
CONNECT_BY_ISCYCLE의사 콜럼이 돌아옵니다1현재 행에 조상 인 아이가 있다면
그리고 그것에 CYCLE:
조상 행 중 하나가 사이클 열에 대해 동일한 값을 갖는 경우 행은 사이클을 형성하는 것으로 간주됩니다.
당신의 예에서, 행 2 조상이기도하는 아이가 있지만 그 id 아직 반환되지 않았습니다.
다시 말해, CONNECT_BY_ISCYCLE 확인합니다 어린이들 (아직 반환되지 않은) CYCLE 확인합니다 현재 행 (이미 반환되었습니다).
CONNECT BY 재귀는 행을 기반으로합니다 CTES는 설정 기반입니다.
Oracle의 문서에 주목하십시오 CYCLE "조상 행"을 언급합니다. 그러나 일반적으로 말하면, 재귀에 "조상 행"이라는 개념은 없습니다. CTE. 트리에서 완전히 결과를 산출 할 수있는 세트 기반 작업입니다. 일반적으로 앵커 부분과 재귀 부분은 다른 테이블을 사용할 수도 있습니다.
재귀 이후 CTE입니다 대개 계층 구조 나무를 만드는 데 사용됩니다. Oracle 사이클 점검을 추가하기로 결정했습니다. 그러나 세트 기반 방식으로 인해 재귀 적 CTE"조상"주기 조건에 대한 명확한 정의 없이도 정의 할 수 없기 때문에 다음 단계가주기를 생성하는지 말하기는 일반적으로 불가능합니다.
"다음"단계를 수행하려면 전체 "현재"세트를 사용할 수 있어야하지만 현재 세트의 각 행 (사이클 열 포함)을 생성하려면 "다음"작업 결과가 필요합니다.
현재 세트가 항상 단일 행으로 구성되어 있다면 문제가되지 않습니다. CONNECT BY), 그러나 재귀 작업이 세트 전체에 정의 된 경우 문제입니다.
조사하지 않았습니다 Oracle 11 그러나 그러나 SQL Server 재귀를 구현합니다 CTE그냥 숨기는 것 CONNECT BY 그 뒤에는 수많은 제한 사항을 제한해야합니다 (모든 세트 기반 작업을 효과적으로 금지).
PostgreSQL반면에 구현은 진정으로 설정된 기반입니다. 재귀 부분에서 앵커 부분을 사용하여 모든 작업을 수행 할 수 있습니다. 그러나 사이클이 처음에 정의되지 않기 때문에 사이클을 감지하는 방법은 없습니다.
앞에서 언급했듯이 MySQL 구현되지 않습니다 CTE전혀 (구현되지 않습니다 HASH JOINS 또는 MERGE JOINs도 중첩 된 루프 만 있으므로 놀라지 마십시오).
아이러니하게도, 나는 오늘이 주제에 관한 편지를 받았는데, 나는 내 블로그에서 다룰 것이다.
업데이트:
재귀 CTEin SQL Server 그 이상은 아닙니다 CONNECT BY 변장. 충격적인 세부 사항은 내 블로그 에서이 기사를 참조하십시오.
다른 팁
PostgreSQL은 스타일의 계층 적 쿼리를 지원하지만 자동주기 감지가 없습니다. 즉, 직접 작성해야하며 반환 된 행의 수는 쿼리의 재귀 부분에 결합 조건을 지정하는 방식에 따라 다릅니다.
두 예제 모두 IF ID (All_IDS) 인 IF IF IF IF IF LOOP를 감지합니다.
WITH recursive tr (id, parent_id, all_ids, cycle) AS (
SELECT id, parent_id, ARRAY[id], false
FROM t
WHERE id = 1
UNION ALL
SELECT t.id, t.parent_id, all_ids || t.id, t.id = ANY(all_ids)
FROM t
JOIN tr ON t.parent_id = tr.id AND NOT cycle)
SELECT id, parent_id, cycle
FROM tr;
id | parent_id | cycle
----+-----------+-------
1 | 2 | f
2 | 1 | f
1 | 2 | t
WITH recursive tr (id, parent_id, all_ids, cycle) AS (
SELECT id, parent_id, ARRAY[id], false
FROM t
WHERE id = 1
UNION ALL
SELECT t.id, t.parent_id, all_ids || t.id, (EXISTS(SELECT 1 FROM t AS x WHERE x.id = t.parent_id))
FROM t
JOIN tr ON t.parent_id = tr.id
WHERE NOT t.id = ANY(all_ids))
SELECT id, parent_id, cycle
FROM tr;
id | parent_id | cycle
----+-----------+-------
1 | 2 | f
2 | 1 | t
Afaik :
- MySQL은 재귀 CTE를 지원하지 않습니다
- SQL Sever는 재귀 CTE에서 사이클 감지를 지원하지 않습니다.
MySQL Server 버전 5.0.45는 마음에 들지 않았습니다 with:
오류 1064 (42000) : SQL 구문에 오류가 있습니다. 오른쪽 구문이 Tr (id, parent_id)와 함께 사용하려면 MySQL 서버 버전에 해당하는 매뉴얼을 확인하십시오.
WITH RECURSIVE s (master, slave, all_ids, cycle) AS
(
SELECT master, slave, ARRAY[master], false FROM binding WHERE master=3477
UNION ALL
SELECT d.master, d.slave, all_ids || d.master, d.slave = ANY(all_ids)
FROM
binding AS d
JOIN
s
ON (d.master = s.slave)
WHERE NOT d.master = ANY(all_ids)
)
SELECT *
FROM s;
나는이 조건이라고 생각합니다 d.slave = ANY(all_ids)
연결 결과가 항상 직관적 일 수는 없습니다.
아래 쿼리는 id = 3 그림의 그래프.
create table graph (id, id_parent) as
(select 2, 1 from dual
union all select 3, 1 from dual
union all select 4, 3 from dual
union all select 5, 4 from dual
union all select 3, 5 from dual)
SQL> select level lvl, graph.*, connect_by_iscycle cycle
2 from graph
3 start with id = 3
4 connect by nocycle prior id = id_parent;
LVL ID ID_PARENT CYCLE
---------- ---------- ---------- ----------
1 3 1 0
2 4 3 0
3 5 4 1
1 3 5 0
2 4 3 0
3 5 4 1
6 rows selected.
SQL> select level lvl, graph.*, connect_by_iscycle cycle
2 from graph
3 start with id = 3
4 connect by nocycle prior id = id_parent
5 and prior id_parent is not null;
LVL ID ID_PARENT CYCLE
---------- ---------- ---------- ----------
1 3 1 0
2 4 3 0
3 5 4 0
4 3 5 1
1 3 5 0
2 4 3 0
3 5 4 1
7 rows selected.
SQL> with t(id, id_parent) as
2 (select *
3 from graph
4 where id = 3
5 union all
6 select g.id, g.id_parent
7 from t
8 join graph g
9 on t.id = g.id_parent)
10 search depth first by id set ord
11 cycle id set cycle to 1 default 0
12 select * from t;
ID ID_PARENT ORD C
---------- ---------- ---------- -
3 1 1 0
4 3 2 0
5 4 3 0
3 5 4 1
3 5 5 0
4 3 6 0
5 4 7 0
3 5 8 1
8 rows selected.
노드 id = 3 이 예에서 오라클이 두주기를 가로 지르는 두 부모가 있습니다.
(1, 3) -> (3, 4) -> (4, 5) -> (5, 3)
그리고
(5, 3) -> (3, 4) -> (4, 5)
Edge (5, 3)는 첫 번째 쿼리 및 첫 번째 사이클의 결과에서 누락되었습니다. 동시에 Edge (5, 3)는 세 번째 쿼리와 두 번째 사이클의 결과에 두 번 나타납니다.
왜 그렇게? Quassnoi가 제공 한 답변에서 사이클 감지 로직에 대한 설명을 확인할 수 있습니다. 평범한 영어로 그것은 그것을 의미합니다
(1)주기를 감지하여 연결하십시오 현재 행에 대한 자식 ID 지금까지 방문한 ID의 일부입니다
(2) 사이클을 감지하는 rec 현재 행의 ID 지금까지 방문한 ID의 일부입니다
두 번째 쿼리의 결과는 추가적인 술어가 있지만 가장 자연스럽게 보입니다. and prior id_parent is not null. 이 경우
(3)주기를 감지합니다 현재 행의 ID 의 일부입니다 학부모 ID지금까지 방문했습니다
이 모든 조건은 아래 쿼리의 열 CNT1, CNT2, CNT3에서 구현됩니다.
SQL> with t(id, id_parent, path_id, path_id_parent, cnt1, cnt2, cnt3) as
2 (select g.*,
3 cast('->' || g.id as varchar2(4000)),
4 cast('->' || g.id_parent as varchar2(4000)),
5 0,
6 0,
7 0
8 from graph g
9 where id = 3
10 union all
11 select g.id,
12 g.id_parent,
13 t.path_id || '->' || g.id,
14 t.path_id_parent || '->' || g.id_parent,
15 regexp_count(t.path_id || '->', '->' ||
16 (select id from graph c where c.id_parent = g.id) || '->'),
17 regexp_count(t.path_id || '->', '->' || g.id || '->'),
18 regexp_count(t.path_id_parent || '->', '->' || g.id || '->')
19 from t
20 join graph g
21 on t.id = g.id_parent
22 -- and t.cnt1 = 0
23 -- and t.cnt2 = 0
24 -- and t.cnt3 = 0
25 )
26 search depth first by id set ord
27 cycle id set cycle to 1 default 0
28 select * from t;
ID ID_PARENT PATH_ID PATH_ID_PARENT CNT1 CNT2 CNT3 ORD C
---------- ---------- --------------- --------------- ---- ---- ---- ---------- -
3 1 ->3 ->1 0 0 0 1 0
4 3 ->3->4 ->1->3 0 0 0 2 0
5 4 ->3->4->5 ->1->3->4 1 0 0 3 0
3 5 ->3->4->5->3 ->1->3->4->5 1 1 1 4 1
3 5 ->3 ->5 0 0 0 5 0
4 3 ->3->4 ->5->3 0 0 0 6 0
5 4 ->3->4->5 ->5->3->4 1 0 1 7 0
3 5 ->3->4->5->3 ->5->3->4->5 1 1 1 8 1
8 rows selected.
CNT1/CNT2/CNT3의 무관심 필터를 사용하고 "사이클 ID 세트 사이클을 1 기본 0으로 제거하십시오"를 제거하면 쿼리가 위의 해당 쿼리로 결과를 반환합니다. 다시 말해 당신은 피할 수 있습니다 cycle clause 더 직관적 인주기 감지 논리를 구현하십시오..
계층 구조 및 사이클 감지에 대한 추가 세부 사항은 책에서 찾을 수 있습니다. Oracle SQL이 공개되었습니다.
