내포 집합 모형
Nested set model중첩 집합 모델은 관계형 데이터베이스에서 중첩 집합(트리 또는 계층 구조라고도 함)을 나타내는 기법이다.null
동기
표준 관계 대수 및 관계 미적분학, 그리고 그것들에 기반한 SQL 연산은 계층에 관한 모든 바람직한 연산을 직접적으로 표현할 수 없다.내포된 집합 모델은 그 문제에 대한 해결책이다.null
대안적 해결책은 계층을 부모-자녀 관계로 표현하는 것이다.셀코는 이것을 인접 목록 모델이라고 불렀다.계층 구조가 임의의 깊이를 가질 수 있는 경우, 인접 목록 모델에서는 두 요소의 계층 구조 내용을 비교하거나 요소가 다른 요소의 하위 계층 구조 내에 있는지 여부를 결정하는 등의 연산 표현을 허용하지 않는다.계층의 깊이가 고정되어 있거나 경계가 있는 경우, 레벨당 하나의 관계 연결을 수행해야 하기 때문에 운영이 가능하지만 비용이 많이 든다.이것은 종종 재료비 문제로 알려져 있다.[citation needed]null
계층 구조는 그래프 데이터베이스로 전환하여 쉽게 표현할 수 있다.또는 관계형 데이터베이스 관리 시스템에서는 다음과 같은 해결책으로 관계형 모델에 대한 몇 가지 관계형 데이터베이스 관리 시스템:
- SQL의 계층 조회 기능과 같은 전용 계층 데이터 유형 지원
- 중첩된 관계 대수에서와 같이 계층적 조작으로 관계 언어를 확장한다.
- SQL의 CONNECT 문과 같은 타동적 폐쇄성으로 관계 언어 확장. 부모-자녀 관계를 사용할 수 있지만 실행 비용이 많이 든다.
- 쿼리는 반복을 지원하는 언어로 표현될 수 있으며 PL/SQL, T-SQL 또는 범용 프로그래밍 언어와 같은 관계형 연산을 중심으로 표현된다.
이러한 해결책을 사용할 수 없거나 실현 불가능할 경우, 다른 접근법을 취해야 한다.null
테크닉
중첩된 집합 모델은 각 노드를 두 번 방문하여 방문 순서와 두 방문 순서에 따라 번호를 매기는 것이다.이렇게 하면 각 노드에 대해 두 개의 숫자가 남는데, 이 숫자는 두 개의 속성으로 저장된다.쿼리 비용이 저렴해짐: 계층 구성원은 이러한 수치를 비교하여 테스트할 수 있다.업데이트를 하려면 번호를 다시 매겨야 하므로 비용이 많이 든다.정수 대신 합리적인 숫자를 사용하는 세분화는 번호를 다시 매기는 것을 피할 수 있고, 따라서 훨씬 더 복잡하지만 업데이트하는 것이 더 빠르다.[1]null
예
의류 상점 카탈로그에서 의류는 왼쪽에 제시된 계층 구조에 따라 분류할 수 있다.
| 노드. | 왼쪽 | 맞다 |
|---|---|---|
| 옷 | 1 | 22 |
| 남성용 | 2 | 9 |
| 여성용 | 10 | 21 |
| 슈트 | 3 | 8 |
| 슬랙스 | 4 | 5 |
| 재킷 | 6 | 7 |
| 드레스 | 11 | 16 |
| 스커트 | 17 | 18 |
| 블라우스 | 19 | 20 |
| 이브닝 가운스 | 12 | 13 |
| 선 드레스 | 14 | 15 |
계층에서 가장 높은 위치를 가진 "클로팅" 범주는 모든 종속 범주를 포함한다.따라서 왼쪽과 오른쪽 도메인 값인 1과 22가 주어지며, 후자의 값은 표현되는 총 노드 수의 두 배가 된다.다음 계층적 수준에는 "남성"과 "여성"이 포함되는데, 둘 다 설명되어야 할 수준을 그들 안에 포함하고 있다.각 레벨의 데이터 노드에는 표 데이터에 나타난 바와 같이, 그 안에 포함된 하위 레벨의 수에 따라 좌우 도메인 값이 할당된다.null
퍼포먼스
중첩 집합을 사용하는 쿼리는 인접 목록을 통과하기 위해 저장 프로시저를 사용하는 쿼리보다 빠를 것으로 예상할 수 있으며, MySQL 5.x와 같은 기본 재귀 쿼리 구조가 없는 데이터베이스의 경우 더 빠른 옵션도 있다.[2]그러나, 재귀 SQL 쿼리는 '직접 하위 항목 찾기' 쿼리에 대해 비교적으로, 그리고 다른 깊이 검색 쿼리에 대해서는 훨씬 더 빨리 수행될 것으로 예상할 수 있으며, Postgre와 같이 이를 제공하는 데이터베이스에 대해서는 더 빠른 옵션도 있다.SQL,[3] Oracle [4]및 Microsoft SQL Server.[5]MySQL은 재귀적 쿼리 구문이 부족했지만 버전 8에 이러한 기능을 추가했다.[6]
단점
동적 끝없는 데이터베이스 트리 계층 구조 사용 사례는 드물다.내포된 집합 모형은 트리 요소와 하나 또는 두 개의 속성이 유일한 데이터인 경우에 적합하지만, 트리의 요소에 대해 더 복잡한 관계형 데이터가 존재하는 경우 좋지 않은 선택이다.'차량'의 범주와 '자동차'의 아동이 '메르세데스'인 경우 임의의 시작 깊이를 부여할 경우, 트리 테이블이 원래 비정규화되지 않는 한 외국의 키 테이블 관계를 설정해야 한다.새로 생성된 트리 항목의 속성은 부모, 자식 또는 형제와 모든 속성을 공유할 수 없다.'식물' 속성 표에 대해 외래 키 테이블을 설정하면 '나무'와 그 자식 '오크'의 자식 속성 데이터에 무결성이 부여되지 않는다.따라서 트리에 삽입된 각 항목의 경우 가장 사소한 사용 사례를 제외한 모든 사용 사례에 대해 항목 속성의 외래 키 테이블을 생성해야 한다.null
트리가 자주 변경될 것으로 예상되지 않는 경우, 시스템의 초기 설계에서 적절히 정규화된 속성 테이블의 계층 구조가 생성되어 보다 단순하고 이동성이 높은 SQL 문, 특히 트리 변경을 위해 임의의 수의 런타임이 필요하지 않으며 프로그래밍 방식으로 생성되거나 삭제된 테이블을 생성할 수 있다.보다 복잡한 시스템의 경우, 계층 구조는 암묵적인 숫자 트리 구조보다는 관계형 모델을 통해 개발될 수 있다.항목의 깊이는 DB 아키텍처 전체의 기초가 아닌 다른 속성에 불과하다.SQL Antiatatters에 명시된 바와 같이:[7]
중첩된 세트는 영리한 해결책이다. 어쩌면 너무 영리할 수도 있다.또한 참조 무결성을 지원하지 않는다.트리를 수정하는 것보다 더 자주 쿼리해야 할 때 가장 잘 사용된다.[8]
이 모델은 여러 상위 범주를 허용하지 않는다.예를 들어, '오크'는 '나무형'의 아이일 수 있지만, '나무형'의 아이일 수도 있다.이를 수용하기 위해 추가적인 태그 지정 또는 분류법이 수립되어야 하며, 다시 단순한 고정 모델보다 더 복잡한 설계로 이어진다.null
삽입 후 표의 모든 레코드에 대해 왼쪽 및 오른쪽 도메인 값을 업데이트해야 하기 때문에 삽입물의 중첩 집합은 매우 느리다.이것은 많은 행이 다시 작성되고 인덱스가 다시 작성되기 때문에 많은 데이터베이스 스트레스를 유발할 수 있다.그러나 큰 나무 한 그루가 아닌 작은 나무의 숲을 테이블에 저장할 수 있다면 작은 나무 한 그루를 업데이트해야 하기 때문에 오버헤드가 크게 줄어들 수도 있다.null
내포된 구간 모형은 이 문제를 겪지 않지만 구현이 더 복잡하고 잘 알려져 있지 않다.그것은 여전히 관계형 외래어 키 테이블 문제로 골머리를 앓고 있다.내포된 구간 모델은 노드의 위치를 인용 부호(n/d)로 표현되는 합리적인 숫자로 저장한다.[1]
변형
위에서 설명한 대로 중첩된 세트 모델을 사용하면 특정 트리 트래버설 작업 중에 몇 가지 성능 제한이 있다.예를 들어 상위 노드가 부여된 즉시 하위 노드를 찾으려면 다음 SQL 코드 예와 같이 하위 트리를 특정 수준으로 정리해야 한다.
선택 아이.노드., 아이.왼쪽, 아이.맞다 From 나무 로서 부모, 나무 로서 아이 어디에 아이.왼쪽 사이 부모.왼쪽 AND 부모.맞다 AND NOT 존재한다 ( -- 중간 노드 없음 선택 * From 나무 로서 중앙의 어디에 중앙의.왼쪽 사이 부모.왼쪽 AND 부모.맞다 AND 아이.왼쪽 사이 중앙의.왼쪽 AND 중앙의.맞다 AND 중앙의.노드. NOT 인 (부모.노드., 아이.노드.) ) AND 부모.왼쪽 = 1 -- 지정된 상위 노드 왼쪽 색인 또는 동등하게:
선택 구별됨 아이.노드., 아이.왼쪽, 아이.맞다 From 나무 로서 아이, 나무 로서 부모 어디에 부모.왼쪽 < 아이.왼쪽 AND 부모.맞다 > 아이.맞다 -- Child Node를 조상들과 연결 그룹 BY 아이.노드., 아이.왼쪽, 아이.맞다 하고 있다 맥스.(부모.왼쪽) = 1 -- 지정된 상위 노드를 가장 가까운 상위 노드로 가진 사용자를 위한 하위 집합 한 단계 이상의 깊이를 가진 아이들을 찾을 때 질의가 더 복잡해질 것이다.이러한 한계를 극복하고 트리 횡단을 단순화하기 위해 모델에 추가 열을 추가하여 트리 내의 노드 깊이를 유지한다.null
| 노드. | 왼쪽 | 맞다 | 깊이 |
|---|---|---|---|
| 옷 | 1 | 22 | 0 |
| 남성용 | 2 | 9 | 1 |
| 여성용 | 10 | 21 | 1 |
| 슈트 | 3 | 8 | 2 |
| 슬랙스 | 4 | 5 | 3 |
| 재킷 | 6 | 7 | 3 |
| 드레스 | 11 | 16 | 2 |
| 스커트 | 17 | 18 | 2 |
| 블라우스 | 19 | 20 | 2 |
| 이브닝 가운스 | 12 | 13 | 3 |
| 선 드레스 | 14 | 15 | 3 |
이 모델에서 부모 노드가 부여된 직계 자식 찾기는 다음과 같은 SQL 코드를 사용하여 수행할 수 있다.
선택 아이.노드., 아이.왼쪽, 아이.맞다 From 나무 로서 아이, 나무 로서 부모 어디에 아이.깊이 = 부모.깊이 + 1 AND 아이.왼쪽 > 부모.왼쪽 AND 아이.맞다 < 부모.맞다 AND 부모.깊이 = 1 -- 지정된 상위 노드 왼쪽 색인 참고 항목
참조
- ^ Hazel, Daniel (2008). "Using rational numbers to key nested sets". arXiv:0806.3115 [cs.DB].
- ^ Quassnoi (29 September 2009), "Adjacency list vs. nested sets: MySQL", Explain Extended, retrieved 11 December 2010
- ^ Quassnoi (24 September 2009), "Adjacency list vs. nested sets: PostgreSQL", Explain Extended, retrieved 11 December 2010
- ^ Quassnoi (28 September 2009), "Adjacency list vs. nested sets: Oracle", Explain Extended, retrieved 11 December 2010
- ^ Quassnoi (25 September 2009), "Adjacency list vs. nested sets: SQL Server", Explain Extended, retrieved 11 December 2010
- ^ "MySQL :: MySQL 8.0 Reference Manual :: 13.2.15 WITH (Common Table Expressions)". dev.mysql.com. Retrieved 2021-09-01.
- ^ Bill, Karwin (2010-06-17). SQL Antipatterns. p. 328.
- ^ Bill, Karwin. SQL Antipatterns. p. 44.
외부 링크
- RDBMS의 계층적 데이터에 대한 트로엘의 링크
- 관계형 데이터베이스의 계층 데이터 관리
- 중첩된 세트에 대한 PHP PEE 구현 - Daniel Khan에 의한
- MySQL 저장 프로시저를 사용하여 인접 목록을 중첩 집합으로 변환
- 중첩된 집합에 대한 PHP 독트린 DBAL 구현 - PreviousNext별
- R 중첩 집합 – R의 중첩 집합 예제
