재귀 함수 정복하기

프로그래머스 SQL 문제를 풀던 중 재귀함수를 이용해야하는 문제가 생겼다.평상시에도 재귀를 어려워했어서 그런지 SQL에서도 재귀를 사용한다는 것에 겁이났지만...😭 극복하기 위해 공부한 내용을 적어보려한다!

 

WITH RECURSIVE 문

RECURSIVE 쿼리란

데이터베이스에서 재귀적으로 데이터를 조회하거나 처리하는데 사용 되는 쿼리다.

메모리 상에 가상의 테이블을 저장해서 실제로 테이블을 생성하거나 데이터 삽입을 하지 않아도 가상 테이블을 생성할 수 있다.

활용

• 계층적 데이터 조회
  • 조직도, 카테고리 트리등의 계층적 데이터를 조회할 때 유용
• 그래프 탐색
  • 그래프 구조의 데이터를 탐색하고 분석하는데 활용
• 계층적 쿼리 연산
  • 계층적 데이터를 수정하거나 계산할 때 사용될 수 있음

쿼리

WITH RECURSIVE cte_count AS(
	SELECT 1      // Anchor Member
	UNION ALL
	SELECT n + 1  // Recursive Member
	FROM cte_count
	WHERE n < 3   // Termination Condition
)
SELECT n        // Query that uses CTE
FROM cte_count;

• Anchor Member: 재귀를 시작하는 기본쿼리.
• Recursive Member: 재귀적으로 반복되는 쿼리
• Termination Condition: 재귀를 종료하는 조건

초기에는 최상위 매니저를 찾기 위한 기본 쿼리(Anchor Member)가 실행되고 그 후 재귀 쿼리(Recursive Member)가 매니저를 찾아 계속되서 실행된다.

📌 프로그래머스_멸종위기의 대장균 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/301651

문제

각 세대별 자식이 없는 개체의 수(COUNT)와 세대(GENERATION)를 출력하는 SQL문을 작성해주세요. 이때 결과는 세대에 대해 오름차순 정렬해주세요. 단, 모든 세대에는 자식이 없는 개체가 적어도 1개체는 존재합니다.

Anchor Member

SELECT ID, PARENT_ID, 1 AS GENERATION
FROM ECOLI_DATA
WHERE PARENT_ID IS NULL

기본 쿼리는 최상위 매니저(최초의 대장균 개체) 를 찾기 위해 PARENT_ID 가 null인 개체를 찾는 쿼리문이다.

Recursive Member

SELECT E.ID, E.PARENT_ID, G.GENERATION + 1 AS GENERATION
FROM ECOLI_DATA E JOIN GEN G ON E.PARENT_ID = G.ID

ECOLI_DATA 테이블과 위에서 생성한 GEN 테이블을 JOIN 해서 합친후 재귀적인 방법으로 각 세대의 자식을 찾아 계산한다.

일반 쿼리

SELECT COUNT(*) COUNT, GENERATION
FROM GEN
WHERE ID NOT IN(
    SELECT DISTINCT PARENT_ID
    FROM ECOLI_DATA
    WHERE PARENT_ID IS NOT NULL
)
GROUP BY GENERATION
ORDER BY GENERATION;

자식이 없는 개체를 찾고 세대별로 개수를 카운트한다.

전체 쿼리

WITH RECURSIVE GEN AS(
    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 AS GENERATION
    FROM ECOLI_DATA E JOIN GEN G ON E.PARENT_ID = G.ID
)
SELECT COUNT(*) COUNT, GENERATION
FROM GEN
WHERE ID NOT IN(
    SELECT DISTINCT PARENT_ID
    FROM ECOLI_DATA
    WHERE PARENT_ID IS NOT NULL
)
GROUP BY GENERATION
ORDER BY GENERATION;

 

출처
https://yermi.tistory.com/entry/MySQL-RECURSIVE-%EC%9E%AC%EA%B7%80%EC%A0%81%EC%9C%BC%EB%A1%9C-%EB%8D%B0%EC%9D%B4%ED%84%B0-%EC%A1%B0%ED%9A%8C%ED%95%98%EA%B8%B0-%EC%9E%AC%EA%B7%80-%EC%BF%BC%EB%A6%AC%EC%9D%98-%ED%99%9C%EC%9A%A9%EA%B3%BC-%EC%9D%B4%ED%95%B4
https://www.mysqltutorial.org/mysql-basics/mysql-recursive-cte/