[WITH RECURSIVE] 멸종위기의 대장균 찾기

cleanUrl: /WITH-RECURSIVE-멸종위기의-대장균-찾기

문제 설명

• 각 세대별 자식이 없는 개체의 수(COUNT)와 세대(GENERATION)를 출력하는 문제

예제 출력

ECOLI_DATA

출력

문제 풀이

• 접근 재귀적 CTE (Common Table Expression)
• 재귀적인 방법으로 세대(GENERATION)를 계산하고 자식이 없는 대장균을 찾는 방법
 
• 표현식

WITH RECURSIVE 뷰_이름 AS
(
	SELECT ...      -- 초기 SQL
	UNION ALL
	SELECT ...      -- 반복할 SQL (반복을 멈출 WHERE절 포함)
)

 
• 예시

WITH RECURSIVE cte (n) AS
(
  SELECT 1
  UNION ALL
  SELECT n + 1 FROM cte WHERE n < 5
)
SELECT * FROM cte;

• 이 명령문을 실행하면 다음 결과가 생성 된다.

+------+
| n    |
+------+
|    1 |
|    2 |
|    3 |
|    4 |
|    5 |
+------+

 
• 동작 과정
• SELECT 1

+------+
| n    |
+------+
|    1 |
+------+

• UNION ALL
• 앞으로 반복문을 실행하면서 나온 결과를 모두 합친다.
• SELECT n + 1 FROM cte WHERE n < 5
• n이 가지고 있는 직전 row set 값이 5보다 작을 때, n+1인 row set을 하나 만든다는 뜻
• 첫번째 반복문에서는 n = 1이므로 반복문을 통해 아래의 row set이 생성

+------+
| n    |
+------+
|    2 |
+------+

• 이를 UNION ALL 하면 다음과 같아진다.

+------+
| n    |
+------+
|    1 |
|    2 |
+------+

• 이걸 직전 row set 값이 4일때까지 반복하므로, 결과적으로 1~5값이 담긴 cte 뷰가 생성된다.

풀이 코드

-- 세대 계산 테이블
WITH RECURSIVE generations AS (
    -- 최초 부모가 없는 대장균 개체는 1세대
    SELECT ID, PARENT_ID, 1 AS GENERATION
    FROM ECOLI_DATA
    WHERE PARENT_ID IS NULL
    
    UNION ALL
    
    -- 재귀적으로 각 개체의 자식을 찾아 세대 계산
    SELECT e.ID, e.PARENT_ID, g.GENERATION + 1
    FROM ECOLI_DATA e
    JOIN generations g
    ON e.PARENT_ID = g.ID
)
SELECT COUNT(*) AS COUNT, G.GENERATION
FROM generations AS G
WHERE NOT EXISTS (
    -- 자식이 없는 개체들 탐색
    SELECT 1
    FROM ECOLI_DATA AS E
    WHERE E.PARENT_ID = G.ID
)
GROUP BY GENERATION
ORDER BY GENERATION

참고 자료

MySQL :: MySQL 8.0 Reference Manual :: 15.2.20 WITH (Common Table Expressions)

MySQL :: MySQL 8.0 Reference Manual :: 15.2.20 WITH (Common Table Expressions)

A common table expression (CTE) is a named temporary result set that exists within the scope of a single statement and that can be referred to later within that statement, possibly multiple times. The following discussion describes how to write statements that use CTEs.