SQL - 계층 구조를 저장하고 탐색하는 방법은 무엇입니까?

StackOverflow https://stackoverflow.com/questions/38801

문제

데이터베이스의 계층적 정보를 모델링하고 검색하는 데 사용하는 방법은 무엇입니까?

도움이 되었습니까?

해결책

이 주제에 대한 결정적인 글은 Joe Celko가 집필했으며, 그는 그 중 다수를 작업하여 Joe Celko의 Trees and Hierarchies in SQL for Smarties라는 책을 만들었습니다.

그는 유향 그래프라는 기술을 선호합니다.이 주제에 대한 그의 작업 소개를 찾을 수 있습니다. 여기

다른 팁

나는 수정된 사전 주문 트리 순회 알고리즘을 좋아합니다.이 기술을 사용하면 트리를 쿼리하는 것이 매우 쉽습니다.

그러나 여기에 Zend Framework(PHP) 기여자 웹페이지에서 복사한 주제에 대한 링크 목록이 있습니다(게시자: Laurent Melmoux, 2007년 6월 5일 15:52).

많은 링크는 언어에 구애받지 않습니다.

데이터베이스의 계층 구조를 나타내는 두 가지 주요 표현과 알고리즘이 있습니다.

  • 수정된 선주문 트리 탐색 알고리즘이라고도 알려진 중첩 세트
  • 인접 목록 모델

여기에 잘 설명되어 있습니다.

제가 수집한 추가 링크는 다음과 같습니다.

인접 목록 모델

중첩 세트

그래프

클래스 :

중첩 세트 DB 트리 Adodb

방문 모델 ADOdb

PEAR::DB_NestedSet

배나무

nstrees

SQL 데이터베이스에서 계층 구조를 나타내는 가장 좋은 방법은 무엇입니까?일반적이고 이식 가능한 기술이요?

계층 구조가 대부분 읽혀지지만 완전히 정적이지는 않다고 가정해 보겠습니다.그것이 가계도라고 가정해 봅시다.

그렇게 하지 않는 방법은 다음과 같습니다.

create table person (
person_id integer autoincrement primary key,
name      varchar(255) not null,
dob       date,
mother    integer,
father    integer
);

그리고 다음과 같이 데이터를 삽입합니다. 

person_id   name      dob       mother father  
1           Pops      1900/1/1   null   null  
2           Grandma   1903/2/4   null   null  
3           Dad       1925/4/2   2      1  
4           Uncle Kev 1927/3/3   2      1
5           Cuz Dave  1953/7/8   null   4
6           Billy     1954/8/1   null   3

대신 노드와 관계를 두 개의 테이블로 분할하세요.

create table person (
person_id integer autoincrement primary key,
name      varchar(255) not null,
dob       date
);

create table ancestor (
ancestor_id   integer,
descendant_id integer,
distance      integer
);

데이터는 다음과 같이 생성됩니다.

person_id   name      dob       
1           Pops      1900/1/1  
2           Grandma   1903/2/4   
3           Dad       1925/4/2   
4           Uncle Kev 1927/3/3
5           Cuz Dave  1953/7/8   
6           Billy     1954/8/1   

ancestor_id  descendant_id  distance
1            1              0
2            2              0
3            3              0
4            4              0
5            5              0
6            6              0
1            3              1
2            3              1
1            4              1
2            4              1
1            5              2
2            5              2
4            5              1
1            6              2
2            6              2
3            6              1

이제 테이블 자체를 다시 조인하지 않는 임의 쿼리를 실행할 수 있습니다. 이는 노드와 동일한 행에 계층 관계가 있는 경우 발생합니다.

누가 조부모님이 계시나요?

select * from person where person_id in 
    (select descendant_id from ancestor where distance=2);

당신의 모든 후손:

select * from person where person_id in 
    (select descendant_id from ancestor 
    where ancestor_id=1 and distance>0);

삼촌은 누구입니까? 

select decendant_id uncle from ancestor 
    where distance=1 and ancestor_id in 
    (select ancestor_id from ancestor 
        where distance=2 and not exists
        (select ancestor_id from ancestor 
        where distance=1 and ancestor_id=uncle)
    )

하위 쿼리를 통해 테이블 ​​자체를 조인하는 데 따른 모든 문제를 방지할 수 있습니다. 일반적인 제한은 하위 하위 쿼리 16개입니다.

문제는 조상 테이블을 유지하는 것이 다소 어렵다는 것입니다. 저장 프로시저를 사용하는 것이 가장 좋습니다.

나는 조쉬의 의견에 동의하지 않습니다.회사 조직과 같은 거대한 계층 구조를 사용한다면 어떻게 될까요?사람들은 회사에 입사/퇴사하고, 보고 라인을 변경하는 등의 작업을 할 수 있습니다."거리"를 유지하는 것은 큰 문제가 되며 두 개의 데이터 테이블을 유지해야 합니다.

이 쿼리(SQL Server 2005 이상)를 사용하면 모든 사람의 전체 행을 볼 수 있으며 계층 구조에서 해당 위치를 계산할 수 있으며 사용자 정보가 포함된 단일 테이블만 필요합니다.하위 관계를 찾기 위해 수정될 수 있습니다.

--Create table of dummy data
create table #person (
personID integer IDENTITY(1,1) NOT NULL,
name      varchar(255) not null,
dob       date,
father    integer
);

INSERT INTO #person(name,dob,father)Values('Pops','1900/1/1',NULL);  
INSERT INTO #person(name,dob,father)Values('Grandma','1903/2/4',null);
INSERT INTO #person(name,dob,father)Values('Dad','1925/4/2',1);
INSERT INTO #person(name,dob,father)Values('Uncle Kev','1927/3/3',1);
INSERT INTO #person(name,dob,father)Values('Cuz Dave','1953/7/8',4);
INSERT INTO #person(name,dob,father)Values('Billy','1954/8/1',3);

DECLARE @OldestPerson INT; 
SET @OldestPerson = 1; -- Set this value to the ID of the oldest person in the family

WITH PersonHierarchy (personID,Name,dob,father, HierarchyLevel) AS
(
   SELECT
      personID
      ,Name
      ,dob
      ,father,
      1 as HierarchyLevel
   FROM #person
   WHERE personID = @OldestPerson

   UNION ALL

   SELECT
    e.personID,
      e.Name,
      e.dob,
      e.father,
      eh.HierarchyLevel + 1 AS HierarchyLevel
   FROM #person e
      INNER JOIN PersonHierarchy eh ON
         e.father = eh.personID
)

SELECT *
FROM PersonHierarchy
ORDER BY HierarchyLevel, father;

DROP TABLE #person;

참고:SQL Server 2008에는 새로운 기능이 도입되었습니다. 계층 ID 이런 종류의 상황에 대한 데이터 유형입니다."트리"에서 행이 위치하는 위치(수평 및 수직)를 제어할 수 있습니다.

신탁:선택하다 ...시작 ...연결 방법

Oracle에는 트리 기반 검색을 쉽게 할 수 있는 SELECT 확장 기능이 있습니다.아마도 SQL Server에도 비슷한 확장 기능이 있습니까?

이 쿼리는 중첩 관계가 저장된 테이블을 순회합니다. 부모의 그리고 어린이 열.

select * from my_table
    start with parent = :TOP
    connect by prior child = parent;

http://www.adp-gmbh.ch/ora/sql/connect_by.html

나는 Josh와 Mark Harrison이 사용하는 기술의 혼합을 선호합니다.

두 개의 테이블, 즉 하나는 Person의 데이터가 있고 다른 하나는 계층 정보(person_id, parent_id [, mother_id])가 있는 테이블입니다. 이 테이블의 PK가 person_id인 경우 노드별로 상위가 하나만 있는 간단한 트리가 있습니다. 이 경우에는 회계 계정과 같은 다른 경우에는 해당되지 않음)

이 계층 구조 테이블은 재귀 프로시저를 통해 또는 DB가 SELECT...와 같은 문장으로 이를 지원하는 경우 통과될 수 있습니다.이전(오라클) 기준.

다른 가능성은 관리하려는 계층 구조 데이터의 최대 깊이가 계층 구조 수준당 열 집합이 있는 단일 테이블을 사용하는 것입니다.

다음에 대한 트리 구성 요소를 구현할 때도 동일한 문제가 발생했습니다. [fleXive] 그리고 tharkun이 언급한 중첩된 집합 트리 모델 접근 방식을 사용했습니다. MySQL 문서.

속도를 (극적으로) 높이는 것 외에도 우리는 퍼진 이는 단순히 모든 왼쪽 및 오른쪽 값을 다시 계산하지 않고도 노드를 삽입하고 이동할 수 있도록 최상위 오른쪽 경계에 대해 최대 Long 값을 사용했음을 의미합니다.왼쪽과 오른쪽의 값은 노드의 범위를 3으로 나누어 계산됩니다. 안의 세 번째는 새 노드의 경계입니다.

Java 코드 예제를 볼 수 있습니다. 여기.

SQL Server 2005를 사용하고 있다면 이 링크 계층적 데이터를 검색하는 방법을 설명합니다.

CTE(Common Table Expressions)는 익숙해지면 친구가 될 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top