Lv5 멸종위기의 대장균 찾기(SQL)

문제 설명

대장균들은 일정 주기로 분화하며, 분화를 시작한 개체를 부모 개체, 분화되어 나온 개체를 자식 개체라고 한다. 이 문제는 각 세대별로 자식이 없는 대장균 개체의 수를 구하고, 세대별로 오름차순으로 출력하는 것이다.

 

테이블 구조

대장균들의 정보를 담고 있는 ECOLI_DATA 테이블의 구조는 다음과 같다.

• ID: 대장균 개체의 ID (PRIMARY KEY)
• PARENT_ID: 부모 대장균의 ID (최초 대장균은 NULL 값을 가짐)
• SIZE_OF_COLONY: 대장균 집단의 크기
• DIFFERENTIATION_DATE: 분화된 날짜
• GENOTYPE: 대장균의 형질

문제 요구사항

각 세대별로 자식이 없는 대장균의 수를 구하고, 결과는 세대에 대해 오름차순으로 정렬해야 한다. 모든 세대에는 자식이 없는 개체가 적어도 1 개체는 존재한다.

 

예시

다음과 같은 데이터가 있을 경우

• 1세대는 ID 1, 2
• 2세대는 ID 3, 4, 5
• 3세대는 ID 6, 7
• 4세대는 ID 8이다.
• 이 중 자식이 없는 대장균은 각각 ID 1, (3, 5), 7, 8이다.

따라서, 출력 결과는 다음과 같아야 한다.

 

해결 과정

1. 서브쿼리 방식

처음에는 서브쿼리를 통해 각 세대의 자식이 없는 대장균 개체들을 계산했으나, 이 방식은 비효율적이고 확장성이 부족했다.

SELECT COUNT(*) AS COUNT, GENERATION 
  FROM (
    SELECT e.ID,
    CASE 
        WHEN e.PARENT_ID IS NULL THEN 1
        WHEN p1.PARENT_ID IS NULL THEN 2
        WHEN p2.PARENT_ID IS NULL THEN 3
        WHEN p3.PARENT_ID IS NULL THEN 4
        WHEN p4.PARENT_ID IS NULL THEN 5
        WHEN p5.PARENT_ID IS NULL THEN 6
        WHEN p6.PARENT_ID IS NULL THEN 7
        WHEN p7.PARENT_ID IS NULL THEN 8
        WHEN p8.PARENT_ID IS NULL THEN 9
        WHEN p9.PARENT_ID IS NULL THEN 10
        WHEN p10.PARENT_ID IS NULL THEN 11
        WHEN p11.PARENT_ID IS NULL THEN 12
        WHEN p12.PARENT_ID IS NULL THEN 13
        WHEN p13.PARENT_ID IS NULL THEN 14
        WHEN p14.PARENT_ID IS NULL THEN 15
        ELSE 16
    END AS GENERATION
    FROM ECOLI_DATA e
    LEFT JOIN ECOLI_DATA p1 ON e.PARENT_ID = p1.ID
    LEFT JOIN ECOLI_DATA p2 ON p1.PARENT_ID = p2.ID
    LEFT JOIN ECOLI_DATA p3 ON p2.PARENT_ID = p3.ID
    LEFT JOIN ECOLI_DATA p4 ON p3.PARENT_ID = p4.ID
    LEFT JOIN ECOLI_DATA p5 ON p4.PARENT_ID = p5.ID
    LEFT JOIN ECOLI_DATA p6 ON p5.PARENT_ID = p6.ID
    LEFT JOIN ECOLI_DATA p7 ON p6.PARENT_ID = p7.ID
    LEFT JOIN ECOLI_DATA p8 ON p7.PARENT_ID = p8.ID
    LEFT JOIN ECOLI_DATA p9 ON p8.PARENT_ID = p9.ID
    LEFT JOIN ECOLI_DATA p10 ON p9.PARENT_ID = p10.ID
    LEFT JOIN ECOLI_DATA p11 ON p10.PARENT_ID = p11.ID
    LEFT JOIN ECOLI_DATA p12 ON p11.PARENT_ID = p12.ID
    LEFT JOIN ECOLI_DATA p13 ON p12.PARENT_ID = p13.ID
    LEFT JOIN ECOLI_DATA p14 ON p13.PARENT_ID = p14.ID
    WHERE NOT EXISTS (
        SELECT 1 FROM ECOLI_DATA child 
        WHERE child.PARENT_ID = e.ID
    )
) result
GROUP BY GENERATION
ORDER BY GENERATION;

 

2. 재귀 쿼리로 리팩토링

보다 효율적으로 해결하기 위해, 재귀적인 방법으로 세대(GENERATION)를 계산하고 자식이 없는 대장균을 찾는 방식으로 리팩토링했다

-- 임시테이블 생성
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
    INNER JOIN generations g 
    ON e.PARENT_ID = g.ID
)
-- 자식이 없는 개체들을 찾고 세대별로 카운트
SELECT COUNT(*) AS COUNT, g.GENERATION
FROM generations g
WHERE NOT EXISTS (
    SELECT 1 
    FROM ECOLI_DATA child 
    WHERE child.PARENT_ID = g.ID
)
GROUP BY g.GENERATION
ORDER BY g.GENERATION;

결과

재귀 쿼리를 사용하여 세대별로 자식이 없는 대장균 개체들을 효율적으로 찾고, 원하는 결과를 출력할 수 있다.