sql 부모 - 관계형 데이터베이스에 계층 적 데이터를 저장하기위한 옵션은 무엇입니까?




자식 재귀 (7)

좋은 개요

일반적으로 빠른 읽기 시간 (예 : 중첩 세트) 또는 빠른 쓰기 시간 (인접성 목록)을 결정합니다. 일반적으로, 귀하는 귀하의 필요에 가장 적합한 옵션을 아래 조합으로 선택하게됩니다. 다음은 몇 가지 심도있는 독서를 제공합니다.

옵션

내가 아는 기능과 일반적인 기능 :

  1. 인접 목록 :
    • 열 : ID, ParentID
    • 쉽게 구현할 수 있습니다.
    • 저렴한 노드 이동, 삽입 및 삭제
    • 수준, 조상 및 자손, 경로를 찾는 데 비용이 많이 든다.
    • 그들을 지원하는 데이터베이스에서 공통 테이블 표현식 을 통해 N + 1 피하기
  2. 중첩 세트 (일명 수정 된 선매 트리 순회 )
    • 열 : 왼쪽, 오른쪽
    • 저렴한 조상, 자손
    • 휘발성 인코딩으로 인한 매우 비싼 O(n/2) 이동, 삽입, 삭제
  3. 브리지 테이블 (일명 클로저 테이블 / w 트리거 )
    • 별도의 조인 테이블을 다음과 함께 사용합니다 : ancestor, descendant, depth (선택 사항)
    • 싼 조상 및 자손
    • 삽입, 업데이트, 삭제에 대한 비용 O(log n) (하위 트리의 크기 O(log n) 씁니다.
    • 정규화 된 인코딩 : 조인에서 RDBMS 통계 및 쿼리 플래너에 적합
    • 노드 당 여러 행 필요
  4. 계보 열 ( 구체화 경로 , 경로 열거라고도 함)
    • 칼럼 : 혈통 (예 : / 부모 / 자식 / 손자 / etc ...)
    • 접두어 쿼리를 통한 저렴한 자손 (예 : LEFT(lineage, #) = '/enumerated/path' )
    • 삽입, 업데이트, 삭제에 대한 비용 O(log n) (하위 트리의 크기 O(log n) 씁니다.
    • 비 관계형 : Array 데이터 유형 또는 직렬화 된 문자열 형식을 사용합니다.
  5. 중첩 된 간격
    • 중첩 된 집합과 비슷하지만 real / float / decimal로 인코딩이 휘발성이 아니므로 (저렴한 이동 / 삽입 / 삭제)
    • 실수 / 부동 소수점 표현 / 정밀도 문제 있음
    • 매트릭스 인코딩 변형 은 "자유"에 대한 조상 인코딩 (실체화 된 경로)을 추가하지만 선형 대수학의 까다로운 점을 추가합니다.
  6. 플랫 테이블
    • 각 레코드에 레벨 및 순위 (예 : 순서) 열을 추가하는 수정 된 인접 목록.
    • 반복 / 페이지 매기기가 싸다.
    • 비싼 이동 및 삭제
    • 좋은 사용 : 스레드 토론 - 포럼 / 블로그 주석
  7. 여러 계보 열
    • 열 : 각 계보 수준마다 하나씩, 루트까지 모든 부모를 참조하고, 항목의 수준에서 아래쪽 수준은 NULL로 설정됩니다.
    • 저렴한 조상, 자손, 수준
    • 저렴한 삽입, 삭제, 나뭇잎의 이동
    • 값 비싼 삽입, 삭제, 내부 노드 이동
    • 계층이 얼마나 깊은 지에 대한 엄격한 제한

데이터베이스 관련 노트

MySQL

신탁

  • 인접 목록을 탐색하려면 CONNECT BY 를 사용하십시오.

PostgreSQL

SQL 서버

  • 일반 요약
  • 2008 제공 HierarchyId 데이터 형식은 리니지 컬럼 접근 방식을 지원하고 표현할 수있는 깊이를 확장합니다.

Answers

이 디자인은 아직 언급되지 않았다.

여러 계보 열

제한이 있지만, 당신이 그들을 감당할 수 있다면, 그것은 매우 간단하고 매우 효율적입니다. 풍모:

  • 열 : 각 계보 수준에 대해 하나씩, 루트까지 모든 부모를 참조하며, 현재 항목의 수준보다 낮은 수준은 NULL로 설정됩니다.
  • 계층이 얼마나 깊은 지에 대한 제한
  • 저렴한 조상, 자손, 수준
  • 저렴한 삽입, 삭제, 나뭇잎의 이동
  • 값 비싼 삽입, 삭제, 내부 노드 이동

다음은 조류의 분류 학적 트리입니다. 계층 구조는 클래스 / 순서 / 패밀리 / 속 / 종 - 종 (species)이 최하위 레벨 인 1 행 = 1 분류군 (리프 노드의 경우에 해당)입니다.

CREATE TABLE `taxons` (
  `TaxonId` smallint(6) NOT NULL default '0',
  `ClassId` smallint(6) default NULL,
  `OrderId` smallint(6) default NULL,
  `FamilyId` smallint(6) default NULL,
  `GenusId` smallint(6) default NULL,
  `Name` varchar(150) NOT NULL default ''
);

및 데이터의 예 :

+---------+---------+---------+----------+---------+-------------------------------+
| TaxonId | ClassId | OrderId | FamilyId | GenusId | Name                          |
+---------+---------+---------+----------+---------+-------------------------------+
|     254 |       0 |       0 |        0 |       0 | Aves                          |
|     255 |     254 |       0 |        0 |       0 | Gaviiformes                   |
|     256 |     254 |     255 |        0 |       0 | Gaviidae                      |
|     257 |     254 |     255 |      256 |       0 | Gavia                         |
|     258 |     254 |     255 |      256 |     257 | Gavia stellata                |
|     259 |     254 |     255 |      256 |     257 | Gavia arctica                 |
|     260 |     254 |     255 |      256 |     257 | Gavia immer                   |
|     261 |     254 |     255 |      256 |     257 | Gavia adamsii                 |
|     262 |     254 |       0 |        0 |       0 | Podicipediformes              |
|     263 |     254 |     262 |        0 |       0 | Podicipedidae                 |
|     264 |     254 |     262 |      263 |       0 | Tachybaptus                   |

이것은 내부 범주가 트리에서 레벨을 변경하지 않는 한 매우 간단한 방법으로 필요한 모든 작업을 수행하기 때문에 유용합니다.


이것은 정말로 둥근 구멍 질문입니다.

관계형 데이터베이스와 SQL이 당신이 가지고 있거나 사용하고자하는 유일한 망치라면 지금까지 게시 된 해답이 적절합니다. 그러나 계층 적 데이터를 처리하도록 설계된 도구를 사용하는 것이 좋습니다. 그래프 데이터베이스 는 복잡한 계층 적 데이터에 이상적입니다.

관계형 모델의 비효율 성과 관계형 모델에 그래프 / 계층 모델을 매핑하는 코드 / 쿼리 솔루션의 복잡성은 그래프 데이터베이스 솔루션이 동일한 문제를 해결할 수있는 용이성과 비교할 때 그만한 가치가 없습니다.

BOM을 공통의 계층 적 데이터 구조로 생각하십시오.

class Component extends Vertex {
    long assetId;
    long partNumber;
    long material;
    long amount;
};

class PartOf extends Edge {
};

class AdjacentTo extends Edge {
};

두 개의 하위 어셈블리 간의 최단 경로 : 간단한 그래프 탐색 알고리즘. 허용 가능한 경로는 기준에 따라 자격이 부여 될 수 있습니다.

유사성 : 두 어셈블리 간의 유사도는 얼마입니까? 두 하위 트리의 교차와 결합을 계산하는 두 하위 트리 모두에서 순회를 수행합니다. 비슷한 비율은 교차를 노동 조합으로 나눈 값입니다.

일시적 폐쇄 : 하위 트리를 이동하여 관심 분야 (예 : "알루미늄이 하위 어셈블리에 얼마나 있습니까?")를 합산합니다.

예, SQL 및 관계형 데이터베이스로 문제를 해결할 수 있습니다. 그러나 작업에 적합한 도구를 기꺼이 사용하려는 경우 훨씬 더 나은 방법이 있습니다.


이 질문에 대한 답변은 매우 부분적이지만 아직 유용하길 바랍니다.

Microsoft SQL Server 2008은 계층 적 데이터 관리에 매우 유용한 두 가지 기능을 구현합니다.

  • HierarchyId 데이터 형식
  • with 키워드를 사용하여 공통 테이블 표현식.

MSDN에서 Kent Tegels의 "SQL Server 2008로 데이터 계층 구조 모델링" 을 시작하십시오. 또한 내 자신의 질문을보십시오 : SQL Server 2008의 재귀 동일한 테이블 쿼리


데이터베이스가 배열을 지원하는 경우 계보 열 또는 구체화 경로를 상위 ID 배열로 구현할 수도 있습니다.

특히 Postgres를 사용하면 집합 연산자를 사용하여 계층 구조를 쿼리하고 GIN 인덱스를 사용하여 우수한 성능을 얻을 수 있습니다. 이렇게하면 단일 쿼리에서 부모, 자식 및 깊이를 찾는 것이 매우 쉽습니다. 업데이트도 꽤 관리하기 쉽습니다.

내가 궁금해하는 경우 구체화 된 경로에 대해 배열을 사용하여 전체 쓰기를했습니다.


인접 모델 + 중첩 세트 모델

트리에 새 항목을 쉽게 삽입 할 수 있으므로 (분기 항목에 새 항목을 삽입하기 만하면됩니다) 쿼리를 매우 빠르게 쿼리 할 수 ​​있기 때문에갔습니다.

+-------------+----------------------+--------+-----+-----+
| category_id | name                 | parent | lft | rgt |
+-------------+----------------------+--------+-----+-----+
|           1 | ELECTRONICS          |   NULL |   1 |  20 |
|           2 | TELEVISIONS          |      1 |   2 |   9 |
|           3 | TUBE                 |      2 |   3 |   4 |
|           4 | LCD                  |      2 |   5 |   6 |
|           5 | PLASMA               |      2 |   7 |   8 |
|           6 | PORTABLE ELECTRONICS |      1 |  10 |  19 |
|           7 | MP3 PLAYERS          |      6 |  11 |  14 |
|           8 | FLASH                |      7 |  12 |  13 |
|           9 | CD PLAYERS           |      6 |  15 |  16 |
|          10 | 2 WAY RADIOS         |      6 |  17 |  18 |
+-------------+----------------------+--------+-----+-----+
  • 부모의 모든 자식이 필요할 때마다 parent 열에 쿼리하면됩니다.
  • 부모의 자손이 모두 필요한 경우 부모의 lftrgt 사이에 lft 가있는 항목을 쿼리합니다.
  • 트리의 루트까지 모든 노드의 부모가 필요하면 노드의 rgt 보다 작은 노드와 노드의 rgt 보다 큰 항목을 쿼리하고 parent 노드 rgt 정렬합니다.

필자는 삽입물보다 빠르게 트리에 액세스하고 질의 할 필요가있었습니다. 그래서 이것을 선택했습니다.

유일한 문제는 새 항목을 삽입 할 때 leftright 열을 고정하는 것입니다. 잘 나는 그것에 대한 저장 프로 시저를 만들었고 내 케이스에서는 드문 새 항목을 삽입 할 때마다 그것을 호출했지만 정말 빠릅니다. Joe Celko의 저서에서 아이디어를 얻었습니다. 저장 프로 시저와 그 방법은 DBA SE https://dba.stackexchange.com/q/89051/41481 에서 설명합니다.


가장 좋아하는 대답은이 글의 첫 번째 문장이 제안한 바입니다. 인접 목록을 사용하여 계층 구조를 유지 관리하고 중첩 된 집합을 사용하여 계층 구조를 쿼리합니다.

지금까지 문제는 Adjacecy List에서 Nested Sets 로의 변환 방법이 너무 느 렸습니다. 왜냐하면 대부분의 사람들이 변환을 수행하기 위해 "Push Stack"이라고하는 극단적 인 RBAR 방법을 사용하고 값 비싼 방법으로 간주 되었기 때문입니다 인접 목록과 중첩 된 세트의 놀라운 성능으로 유지 보수의 단순함을 너바나에 도달하십시오. 결과적으로, 대부분의 사람들은 말하자면, 약 10 만개 이상의 노드가있는 경우에 하나 또는 다른 하나를 해결해야합니다. 푸시 스택 방법을 사용하면 MLM이 100 만개의 노드 계층 구조로 간주되는 전환을 하루 종일 수행 할 수 있습니다.

나는 Celko에게 Adjacency List를 중첩 된 세트로 변환하는 방법을 제시함으로써 경쟁을 다소 줄 것이라고 생각했다. 내 i5 노트북에서 푸시 스택 방식의 성능은 다음과 같습니다.

Duration for     1,000 Nodes = 00:00:00:870 
Duration for    10,000 Nodes = 00:01:01:783 (70 times slower instead of just 10)
Duration for   100,000 Nodes = 00:49:59:730 (3,446 times slower instead of just 100) 
Duration for 1,000,000 Nodes = 'Didn't even try this'

새로운 메소드의 지속 시간은 다음과 같습니다 (괄호 안의 푸시 스택 메소드 포함).

Duration for     1,000 Nodes = 00:00:00:053 (compared to 00:00:00:870)
Duration for    10,000 Nodes = 00:00:00:323 (compared to 00:01:01:783)
Duration for   100,000 Nodes = 00:00:03:867 (compared to 00:49:59:730)
Duration for 1,000,000 Nodes = 00:00:54:283 (compared to something like 2 days!!!)

네, 맞습니다. 1 분 미만으로 1 백만 노드가 변환되고 4 초 이내에 100,000 노드가 생성됩니다.

새로운 방법에 대해 읽고 다음 URL에서 코드 사본을 얻을 수 있습니다. http://www.sqlservercentral.com/articles/Hierarchy/94040/

나는 또한 유사한 방법을 사용하여 "사전 집계"된 계층을 개발했다. MLM의 사람들과 BMS (bill of materials)를 만드는 사람들은이 기사에 특히 관심을 가질 것입니다. http://www.sqlservercentral.com/articles/T-SQL/94570/

두 기사 중 하나를 살펴보기 위해 들르면 "토론에 참여"링크로 이동하여 내가 생각하는 것을 알려주십시오.


여러 해가 있다면 그 해를 고려해야합니다. 한 가지 방법은 다음과 같습니다.

SELECT date_part('year', author_date::date) as year,
       date_part('week', author_date::date) AS weekly,
       COUNT(author_email)           
FROM commits
GROUP BY year, weekly
ORDER BY year, weekly;

더 자연스럽게 쓰 date_trunc() .

SELECT date_trunc('week', author_date::date) AS weekly,
       COUNT(author_email)           
FROM commits
GROUP BY weekly
ORDER BY weekly;






sql database tree relational-database hierarchical-data