관계형 데이터베이스에 계층 데이터를 저장하는 옵션은 무엇입니까?

programing

관계형 데이터베이스에 계층 데이터를 저장하는 옵션은 무엇입니까?

topblog 2023. 5. 18. 20:38

관계형 데이터베이스에 계층 데이터를 저장하는 옵션은 무엇입니까?

좋은 개요

일반적으로 빠른 읽기 시간(예: 중첩 집합) 또는 빠른 쓰기 시간(인접 목록) 중에서 결정합니다.일반적으로 필요에 가장 적합한 아래 옵션의 조합을 선택할 수 있습니다.다음은 몇 가지 심층적인 내용을 제공합니다.

하나 더 중첩된 구간 대 인접 목록 비교: 내가 찾은 인접 목록, 구체화된 경로, 중첩 집합 및 중첩 간격의 최상의 비교.
계층형 데이터 모델: 트레이드오프 및 사용 예에 대한 설명이 잘 포함된 슬라이드
MySQL에서 계층 구조 표현: 특히 중첩 집합에 대한 매우 좋은 개요
RDBMS의 계층적 데이터: 내가 본 가장 포괄적이고 잘 구성된 링크 세트이지만 설명 방식으로는 많지 않습니다.

옵션들

제가 알고 있는 일반적인 특징은 다음과 같습니다.

인접 목록:

열: ID, 부모아이디
구현이 용이합니다.
저렴한 노드가 이동, 삽입 및 삭제됩니다.
수준, 조상 및 후손, 경로를 찾는 데 비용이 많이 듭니다.
N+1을 지원하는 데이터베이스의 공용 표 식을 통해 N+1 사용 안 함

중첩 집합(수정된 사전 순서 트리 순회)

열:왼쪽, 오른쪽
값싼 조상들, 후손들
비싼 매우비다니쌉.O(n/2), 이동, 삽입, 삭제가 가능합니다.

브리지 테이블(일명: Bridge Table).폐쇄 테이블 /w 트리거)

상위, 하위, 깊이가 있는 별도의 조인 테이블 사용(선택 사항)
값싼 조상과 후손들
비용 기용O(log n)) , 삭제(하트의크기리트), 삭제(위이업삽삭제), 삭제(데입)에 대한
정규화된 인코딩: 조인에서 RDBMS 통계 및 쿼리 플래너에 적합합니다.
노드당 여러 행 필요

계보 열(일명: Lineage Column.구체화된 경로, 경로 열거)

열: 혈통(예: /부모/자녀/손자/기타)
쿼리 ▁(항▁via:목(ants)를 통한 저렴한 하위 항목(예:LEFT(lineage, #) = '/enumerated/path')
비용 기용O(log n)) , 삭제(하트의크기리트), 삭제(위이업삽삭제), 삭제(데입)에 대한
비관계형: 어레이 데이터 유형 또는 직렬화된 문자열 형식에 의존합니다.

내포된 구간

중첩 집합과 비슷하지만 인코딩이 불안정하지 않도록 실제/부동/소수점을 사용합니다(저렴한 이동/삽입/삭제).
실제/부동/소수점 표현/정밀도 문제가 있음
행렬 인코딩 변형은 "자유"에 대한 조상 인코딩(물질화된 경로)을 추가하지만 선형 대수학의 까다로움이 추가됩니다.

플랫 테이블

각 레코드에 수준 및 순위(예: 순서 지정) 열을 추가하는 수정된 인접 목록입니다.
반복/페이지 비용이 저렴
비용이 많이 드는 이동 및 삭제
유용한 사용: 스레드화된 토론 - 포럼/블로그 주석

다중 계보 열

열: 각 계보 수준에 대해 하나씩, 루트까지의 모든 부모를 참조하며 항목 수준에서 아래쪽 수준은 NULL로 설정됩니다.
값싼 조상들, 후손들, 수준
저렴한 잎 삽입, 삭제, 이동
내부 노드의 삽입, 삭제, 이동에 많은 비용이 소요됨
계층의 깊이에 대한 제한이 있음

데이터베이스 관련 참고 사항

MySQL/MariaDB

~~인접 목록에 세션 변수 사용~~
MySQL 8.0 또는 MariaDB 10.2에서 CTE 사용

오라클

CONNECT BY를 사용하여 인접 목록 이동

PostgreSQl

materialized 경로에 대한 tree 데이터 유형

SQL 서버

일반 요약
2008은 Lineage Column 접근 방식에 도움이 되고 표현할 수 있는 깊이를 확장하는 것으로 보이는 HierarchyId 데이터 유형을 제공합니다.

제가 가장 좋아하는 대답은 이 스레드의 첫 번째 문장이 제안한 것과 같습니다.인접 목록을 사용하여 계층을 유지 관리하고 중첩 집합을 사용하여 계층을 쿼리합니다.

지금까지 문제는 대부분의 사람들이 변환을 수행하기 위해 "푸시 스택"이라고 알려진 극단적인 RBAR 방법을 사용하고 인접 목록과 Nested Sets에 의해 유지보수의 단순성이라는 Nirvana에 도달하기에는 비용이 너무 많이 든다고 여겨졌기 때문에 인접 목록에서 Nested Sets로의 적용 방법이 매우 느렸다는 것입니다.놀라운 성능의 중첩 세트입니다.결과적으로 대부분의 사람들은 하나 또는 다른 하나에 만족해야 합니다. 특히 노드 수가 100,000개 이상인 경우에는 더욱 그렇습니다.푸시 스택 방법을 사용하면 MLM 사용자가 작은 백만 개 노드 계층으로 간주하는 변환을 수행하는 데 하루가 걸릴 수 있습니다.

불가능해 보이는 속도로 인접 목록을 네스트 세트로 변환하는 방법을 생각해냄으로써 Celko에게 약간의 경쟁을 줄 것이라고 생각했습니다.이것은 제 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분 이내에 100만 개의 노드가 변환되고 4초 이내에 100,000개의 노드가 변환됩니다.

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

저는 또한 유사한 방법을 사용하여 "사전 집계" 계층 구조를 개발했습니다.MLM'ers와 재료 청구서를 만드는 사람들은 이 기사에 특히 관심을 가질 것입니다.http://www.sqlservercentral.com/articles/T-SQL/94570/

두 기사 중 하나를 보려면 "토론 참여" 링크로 이동하여 어떻게 생각하는지 알려주십시오.

인접 모형 + 내포 집합 모형

트리에 새 항목을 쉽게 삽입할 수 있고(새 항목을 삽입하려면 지점의 ID만 있으면 됨) 쿼리도 상당히 빠르게 수행할 수 있기 때문에 그렇게 했습니다.

+-------------+----------------------+--------+-----+-----+
| 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기둥.
부모의 자식이 .lftlft그리고.rgt친부모의
의▁having▁up▁for다▁if▁items니▁parents가 있는 항목을 .lft노의값다낮보다 lft그리고.rgt노의크다보다 큼rgt 를 으로정렬로 합니다.parent.

트리에 액세스하고 쿼리하는 속도를 삽입하는 속도보다 빠르게 만들어야 했기 때문에 이것을 선택했습니다.

유일한 문제는 그것을 고치는 것입니다.left그리고.right새 항목을 삽입할 때 열을 누릅니다.글쎄요, 저는 그것을 위한 저장 프로시저를 만들었고 제 경우에는 드문 새로운 항목을 삽입할 때마다 그것을 불렀지만 그것은 정말 빠릅니다.Joe Celko의 책에서 아이디어를 얻었으며, 저장 절차와 방법은 여기 DBASE https://dba.stackexchange.com/q/89051/41481 에 설명되어 있습니다.

이 솔루션을 사용하면 하위 항목을 신속하게 검색할 수 있지만 이러한 작업에서 성능이 느리기 때문에 삽입 또는 삭제가 자주 필요한 대규모 데이터 세트를 처리하는 데는 적합하지 않습니다.따라서 자주 변경되지 않는 테이블에 가장 적합합니다.

이 설계는 아직 언급되지 않았습니다.

다중 계보 열

비록 한계가 있지만, 여러분이 그것들을 견딜 수 있다면, 그것은 매우 간단하고 효율적입니다.특징:

열: 각 계보 수준에 대해 하나씩, 루트까지의 모든 부모를 참조하며, 현재 항목 수준보다 낮은 수준은 0(또는 NULL)으로 설정됩니다.
계층의 깊이에 대한 고정된 제한이 있습니다.
값싼 조상들, 후손들, 수준
저렴한 잎 삽입, 삭제, 이동
내부 노드의 삽입, 삭제, 이동에 많은 비용이 소요됨

다음은 새의 분류학적 트리의 예입니다. 따라서 계층 구조는 Class/Order/Family/Genus/종입니다. 종들은 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 서버 2008은 계층 데이터 관리에 매우 유용한 두 가지 기능을 구현합니다.

HierarchyId 데이터 유형.
키워드와 함께 사용하는 일반적인 테이블 식입니다.

시작은 MSDN에서 Kent Tegels의 "Model Your Data Hierarchies With SQL Server 2008"을 참조하십시오.내 질문도 참조:SQL Server 2008의 동일한 테이블 재귀 쿼리

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

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

궁금하시다면 구체화된 경로를 위해 어레이를 사용하는 것에 대해 자세히 알고 있습니다.

이것은 정말로 네모난 문제입니다. 둥근 구멍의 문제가 있습니다.

관계형 데이터베이스와 SQL이 유일한 해머이거나 사용할 의향이 있는 경우 지금까지 게시된 답변으로 충분합니다.그러나 계층적 데이터를 처리하도록 설계된 도구를 사용하는 것은 어떨까요?그래프 데이터베이스는 복잡한 계층 데이터에 적합합니다.

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

재료 명세서를 공통 계층 데이터 구조로 간주합니다.

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

class PartOf extends Edge {
};

class AdjacentTo extends Edge {
};

두 횡단구성요소 사이의 최단 경로:간단한 그래프 통과 알고리즘입니다.허용 가능한 경로는 기준에 따라 한정될 수 있습니다.

유사성:두 어셈블리의 유사성 정도는 어느 정도입니까?두 하위 트리의 교차점과 결합을 계산하는 두 하위 트리에 대해 횡단을 수행합니다.유사한 백분율은 교차로를 조합으로 나눈 값입니다.

과도적 폐쇄:하위 트리를 걷고 관심 분야(예: "하위 어셈블리에 알루미늄이 얼마나 들어 있습니까?")를 요약합니다.

예, SQL과 관계형 데이터베이스로 문제를 해결할 수 있습니다.그러나 작업에 적합한 도구를 사용할 의사가 있다면 훨씬 더 나은 접근법이 있습니다.

나는 Postgre를 사용하고 있습니다.내 계층에 대한 폐쇄 테이블이 있는 SQL.전체 데이터베이스에 대해 하나의 범용 저장 프로시저가 있습니다.

CREATE FUNCTION nomen_tree() RETURNS trigger
    LANGUAGE plpgsql
    AS $_$
DECLARE
  old_parent INTEGER;
  new_parent INTEGER;
  id_nom INTEGER;
  txt_name TEXT;
BEGIN
-- TG_ARGV[0] = name of table with entities with PARENT-CHILD relationships (TBL_ORIG)
-- TG_ARGV[1] = name of helper table with ANCESTOR, CHILD, DEPTH information (TBL_TREE)
-- TG_ARGV[2] = name of the field in TBL_ORIG which is used for the PARENT-CHILD relationship (FLD_PARENT)
    IF TG_OP = 'INSERT' THEN
    EXECUTE 'INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) 
        SELECT $1.id,$1.id,0 UNION ALL
      SELECT $1.id,ancestor_id,depth+1 FROM ' || TG_ARGV[1] || ' WHERE child_id=$1.' || TG_ARGV[2] USING NEW;
    ELSE                                                           
    -- EXECUTE does not support conditional statements inside
    EXECUTE 'SELECT $1.' || TG_ARGV[2] || ',$2.' || TG_ARGV[2] INTO old_parent,new_parent USING OLD,NEW;
    IF COALESCE(old_parent,0) <> COALESCE(new_parent,0) THEN
      EXECUTE '
      -- prevent cycles in the tree
      UPDATE ' || TG_ARGV[0] || ' SET ' || TG_ARGV[2] || ' = $1.' || TG_ARGV[2]
        || ' WHERE id=$2.' || TG_ARGV[2] || ' AND EXISTS(SELECT 1 FROM '
        || TG_ARGV[1] || ' WHERE child_id=$2.' || TG_ARGV[2] || ' AND ancestor_id=$2.id);
      -- first remove edges between all old parents of node and its descendants
      DELETE FROM ' || TG_ARGV[1] || ' WHERE child_id IN
        (SELECT child_id FROM ' || TG_ARGV[1] || ' WHERE ancestor_id = $1.id)
        AND ancestor_id IN
        (SELECT ancestor_id FROM ' || TG_ARGV[1] || ' WHERE child_id = $1.id AND ancestor_id <> $1.id);
      -- then add edges for all new parents ...
      INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) 
        SELECT child_id,ancestor_id,d_c+d_a FROM
        (SELECT child_id,depth AS d_c FROM ' || TG_ARGV[1] || ' WHERE ancestor_id=$2.id) AS child
        CROSS JOIN
        (SELECT ancestor_id,depth+1 AS d_a FROM ' || TG_ARGV[1] || ' WHERE child_id=$2.' 
        || TG_ARGV[2] || ') AS parent;' USING OLD, NEW;
    END IF;
  END IF;
  RETURN NULL;
END;
$_$;

그런 다음 계층이 있는 각 테이블에 대해 트리거를 만듭니다.

CREATE TRIGGER nomenclature_tree_tr AFTER INSERT OR UPDATE ON nomenclature FOR EACH ROW EXECUTE PROCEDURE nomen_tree('my_db.nomenclature', 'my_db.nom_helper', 'parent_id');

기존 계층에서 폐쇄 테이블을 채우는 경우 다음 저장 프로시저를 사용합니다.

CREATE FUNCTION rebuild_tree(tbl_base text, tbl_closure text, fld_parent text) RETURNS void
    LANGUAGE plpgsql
    AS $$
BEGIN
    EXECUTE 'TRUNCATE ' || tbl_closure || ';
    INSERT INTO ' || tbl_closure || ' (child_id,ancestor_id,depth) 
        WITH RECURSIVE tree AS
      (
        SELECT id AS child_id,id AS ancestor_id,0 AS depth FROM ' || tbl_base || '
        UNION ALL 
        SELECT t.id,ancestor_id,depth+1 FROM ' || tbl_base || ' AS t
        JOIN tree ON child_id = ' || fld_parent || '
      )
      SELECT * FROM tree;';
END;
$$;

폐쇄 테이블은 3개의 열 - EORSTEAR_ID, DENSENT_ID, DEEPTH로 정의됩니다.OESTORE와 DEEPRINT에 대해 동일한 값, DEEPH에 대해 0의 값으로 레코드를 저장하는 것이 가능합니다.이렇게 하면 계층 검색을 위한 쿼리가 간소화됩니다.그리고 그것들은 정말로 매우 간단합니다.

-- get all descendants
SELECT tbl_orig.*,depth FROM tbl_closure LEFT JOIN tbl_orig ON descendant_id = tbl_orig.id WHERE ancestor_id = XXX AND depth <> 0;
-- get only direct descendants
SELECT tbl_orig.* FROM tbl_closure LEFT JOIN tbl_orig ON descendant_id = tbl_orig.id WHERE ancestor_id = XXX AND depth = 1;
-- get all ancestors
SELECT tbl_orig.* FROM tbl_closure LEFT JOIN tbl_orig ON ancestor_id = tbl_orig.id WHERE descendant_id = XXX AND depth <> 0;
-- find the deepest level of children
SELECT MAX(depth) FROM tbl_closure WHERE ancestor_id = XXX;

언급URL : https://stackoverflow.com/questions/4048151/what-are-the-options-for-storing-hierarchical-data-in-a-relational-database

'programing' 카테고리의 다른 글

UI 레이블 텍스트 여백 (0)	2023.05.18
배열에서 빈 요소를 제거하려면 어떻게 해야 합니까? (0)	2023.05.18
Swift의 정밀 문자열 형식 지정자 (0)	2023.05.13
기본 유형 생성자를 호출하기 전에 VB.NET이 인스턴스 변수를 초기화하도록 강제할 수 있습니까? (0)	2023.05.13
MEF 플러그인 프로젝트에 참조를 추가할 때 경고 아이콘이 표시되는 이유는 무엇입니까? (0)	2023.05.13

현재글관계형 데이터베이스에 계층 데이터를 저장하는 옵션은 무엇입니까?

각종 프로그래밍 정보를 다루는 블로그입니다.

wordpress, Git, asp.net, PowerShell, json, C, mysql, python, Oracle, Android, angularJS, Excel, MongoDB, CSS, Spring-boot, jQuery, Ajax, reactjs, MariaDB, sql-server,

Today :
Yesterday :

topblog

관계형 데이터베이스에 계층 데이터를 저장하는 옵션은 무엇입니까?

관계형 데이터베이스에 계층 데이터를 저장하는 옵션은 무엇입니까?

인접 모형 + 내포 집합 모형

다중 계보 열

'programing' 카테고리의 다른 글

'programing'의 다른글

티스토리툴바

« 2025/02 »
일	월	화	수	목	금	토
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28

관계형 데이터베이스에 계층 데이터를 저장하는 옵션은 무엇입니까?

관계형 데이터베이스에 계층 데이터를 저장하는 옵션은 무엇입니까?

인접 모형 + 내포 집합 모형

다중 계보 열

'programing' 카테고리의 다른 글

'programing'의 다른글

관련글

티스토리툴바