php - 하위 - nested category mysql




효과적이고 쉬운 방법으로 계층 구조, 부모/자녀 관계 성취 (7)

나는 테이블을 좋아해.

create table site
(
site_Id int(5),
parent_Id int(5),
site_desc varchar2(100)
);

분야의 중요성 :

  • site_Id : 사이트의 ID
  • parent_Id : 사이트의 부모 ID
  • site_desc : 질문과 관련이 없지만 사이트에 대한 설명이 있습니다.

요구 사항은 입력란에 site_id가 있고 사이트 아래에 태그가있는 모든 ID가 필요한 경우입니다. 예 :

                    A
                   / \
                  B   C
                / | \ /\
               D  E F G H
              /\
             I  J

모든 노드는 site_Id입니다.

테이블에 다음과 같은 데이터가 포함되어 있습니다.

Site_id  | Parent_ID  |  site_desc
_________|____________|___________
 A       |   -1       |   
 B       |    A       |
 C       |    A       |
 D       |    B       |
 E       |    B       |
 F       |    B       |
 I       |    D       |
 J       |    D       |

......

A는 B와 C의 부모입니다.

B가 주어진 입력이면 쿼리는 D, E, I, F, J를 가져와야합니다.

현재 루프에서 여러 쿼리를 통해 달성되지만 최소한의 쿼리에서이를 달성하려고 생각했습니다.

내가 현재하고있는 것은 :

투표를 거절하다

알고리즘은 다음과 같이 진행됩니다.

Initially create a data set object which you will populate, by fetching data from the data base. 
Create a method which takes the parent id as parameter and returns its child nodes if present, and returns -1, if it doesnt have a child. 
Step1: Fetch all the rows, which doesn't have a parent(root) node. 
Step2: Iterate through this result. For example if prod1 and prod2 are the initial returned nodes, in the resultset. 
Iterating this RS we get prod1, and we insert a row in our DataSET obj. 
Then we send the id of prod1 to getCHILD method, to get its child, and then again we iterate the returned resultset, and again call the getCHILD method, till we dont get the lowest node.

내 데이터 모델 제약 내에서 최적의 최적화 된 기술이 필요합니다. 제안이 있으시면 언제든지 대답하십시오.
제발 뭐든지 제안 해주세요. 미리 감사드립니다.


나는 또한 자신에게 재귀 적으로 관계를 쿼리하는 방법을 물었고, 나의 뇌는이 솔루션을 생성했다. (:

SELECT * FROM
(
    SELECT t2.* FROM table t1, table t2 where t2.parent = t1.id OR t2.parent 0 GROUP BY t2.id, t2.parent
) as all_relations
WHERE all_relations.parent >= '_the_id_'

# if you dont want a subtree use only the inner select

나는 100 % 확신하지는 않지만, id가 자동으로 증가하고 자식이 부모로 작은 ID를 갖지 않는다면 (정상적인 경우 여야 함), 이것이 해결책 일 수 있다고 생각합니까?


다른 사람들은 이미 테이블 구조를 약간 수정하여이를 수행하는 방법을 제안했습니다.

구조체를 수정하고 싶지 않다면 (이것이 최상일지라도) 다음과 같이 할 수 있습니다 :

  • SELECT * FROM 사이트 ORDER BY Parent_ID, Site_id;

일반적으로 일단 할당되면 ID가 변경되지 않는다고 안전하게 가정 할 수 있습니다. ID가 바뀌지 않는 경우, 즉 노드 C가 노드 B 아래로 이동하지 않으면 자식 노드가 부모보다 항상 높은 ID를 갖는 것은 사실이며 위의 정렬은 모든 부모가 자식보다 먼저 가져온다는 것을 보장합니다 .

그래서 이것들은 가설입니다 :

- we prefer not to change the table layout
- we never change the IDs once assigned
- we never reorder the tree, moving IDs around

따라서 트리를 메모리에 만들 수 있습니다 (쿼리 자체를 줄여 Where_ Site_ID> = B를 추가 할 수도 있습니다).

첫 번째 노드는 B가되고 트리에 놓입니다.

모든 후속 노드는 이전에 반드시로드 된 Parent_ID-th 노드에 저장 될 수 있습니다.

이것은 (부모 노드를 직접 수정하는) Python에서 아주 잘 될 것입니다.

"B의 모든 자손 얻기"요청은 PHP에서 다음과 같이 응답 할 수 있습니다.

$nodes  = array( $parent_id );

$cursor = SQLQuery("SELECT * FROM site WHERE Site_ID > ? "
        .  "ORDER BY Parent_ID, Site_Id ;", $parent_id);

while ($tuple = SQLFetchTuple($cursor))
    if (in_array($tuple['Parent_ID'], $nodes))
        $nodes[] = $tuple['Site_Id'];
SQLFree($cursor);

// The first node is the global parent, and may be array_shift'ed away
    // if desired.

또 다른 방법
상당히 무차별 한 힘

또 다른 가능성은 "descendant_of"관계를 재귀 적으로 다른 테이블에 저장하는 것입니다.

    TRUNCATE descendants;
    INSERT INTO descendants ( node, of ) VALUES ( -1, NULL );

    INSERT INTO descendants SELECT SiteId, ParentId FROM site JOIN
           descendants ON ( site.ParentId = descendants.of );

그리고 삽입 된 행 수가 0이 될 때까지 INSERT를 반복하십시오 (또는 자손의 전체 행 수가 증가하지 않는 경우, 대부분의 DB에서 쿼리 크기가 매우 빠름).

이 시점에서 모든 1 레벨 관계를 저장하게됩니다. 지금:

INSERT IGNORE INTO descendants SELECT s1.node, s2.of FROM
           descendants AS s1 JOIN descendants AS s2 ON (s1.of = s2.node);

자손이 늘어날 때까지 다시합니다 (최대 수와 같은 수의 삽입이 필요합니다). 총 JOIN 수는 레벨 수의 두 배가됩니다.

이제 노드 16의 모든 자손을 가져 오려면 쿼리 만하면됩니다.

SELECT node FROM descendants WHERE of = 16;

어제, 나는 당신이 묘사 한 문제와 정확히 관련이있는이 question answered question . 주어진 adjacency 목록에서 특정 부모의 모든 자식 노드를 얻고 싶다. 그리고 아마도 일차원 배열에서 쉽게 반복하다.

데이터베이스 호출을 하나만 사용하여이 작업을 수행 할 수 있지만 일종의 캐치가 있습니다. 테이블의 모든 행을 반환 해야 합니다. MySQL은 재귀 쿼리를 지원하지 않으므로, 대신에 애플리케이션 코드에서 SELECT 를 수행해야한다.

필자는 위의 링크에 대한 답을 간단히 말하면되지만 기본적으로 PDOStatement->fetchAll(PDO::FETCH_ASSOC) 또는 다른 메소드의 결과 집합을 다음과 같은 형식으로 반환하면 기본적으로 다음과 같이됩니다.

Array
(
    [0] => Array
    (
        [site_id] => A
        [parent_id] => -1
        [site_desc] => testtext
    )
    [1] => Array
    (
        [site_id] => B
        [parent_id] => A
        [site_desc] => testtext
    )
    [2] => Array
    (
        [site_id] => C
        [parent_id] => A
        [site_desc] => testtext
    )
    [3] => Array
    (
        [site_id] => D
        [parent_id] => B
        [site_desc] => testtext
    )
    [4] => Array
    (
        [site_id] => E
        [parent_id] => B
        [site_desc] => testtext
    )
    [5] => Array
    (
        [site_id] => F
        [parent_id] => B
        [site_desc] => testtext
    )
    [6] => Array
    (
        [site_id] => I
        [parent_id] => D
        [site_desc] => testtext
    )
    [7] => Array
    (
        [site_id] => J
        [parent_id] => D
        [site_desc] => testtext
    )
)

이 재귀 함수를 사용하여 site_id 의 모든 자식 / 손자 / greatgrandchildren / so-on (사용자가 id를 알고있는 경우)을 검색 할 수 있습니다.

function fetch_recursive($src_arr, $id, $parentfound = false, $cats = array())
{
    foreach($src_arr as $row)
    {
        if((!$parentfound && $row['site_id'] == $id) || $row['parent_id'] == $id)
        {
            $rowdata = array();
            foreach($row as $k => $v)
                $rowdata[$k] = $v;
            $cats[] = $rowdata;
            if($row['parent_id'] == $id)
                $cats = array_merge($cats, fetch_recursive($src_arr, $row['site_id'], true));
        }
    }
    return $cats;
}

예를 들어 site_id D 의 모든 하위 항목을 검색하려는 경우 다음과 같은 함수를 사용합니다.

$nodelist = fetch_recursive($pdostmt->fetchAll(PDO::FETCH_ASSOC), 'D');
print_r($nodelist);

출력 :

[0] => Array
(
    [site_id] => D
    [parent_id] => B
    [site_desc] => testtext
)
[1] => Array
(
    [site_id] => I
    [parent_id] => D
    [site_desc] => testtext
)
[2] => Array
(
    [site_id] => J
    [parent_id] => D
    [site_desc] => testtext
)

부모, 자녀, 손주 등의 정보를 보유하고 있음을 유의하십시오 (그러나 중첩은 깊음).


여기에 귀하의 의견을 바탕으로 나는 수백 가지 응용 프로그램이이를 사용하고 있기 때문에 기존 데이터 모델을 변경하기를 꺼리고 있다고 가정하고 있습니다.

문제의 근원은 모든 사이트에 대해 직접 부모 만 알기 때문에 루트 사이트를 찾을 때까지 해당 부모의 부모를 재귀 적으로 조회해야합니다.

사이트가 중첩 될 수있는 깊이 / 레벨의 한계를 벗어날 수있는 경우, 모든 작업을 수행하고 부팅 속도가 느려지 지 않은 멋진 쿼리를 작성할 수 있습니다. 쿼리를 실행하는 데 발생하는 대부분의 오버 헤드는 연결, 네트워크 대역폭 등을 설정하면 발생합니다. MySQL은 매우 빠릅니다.

여러 쿼리를 실행하면 모든 오버 헤드가 증가하므로 필요하지 않습니다. SELECT *를 수행 한 다음 응용 프로그램 논리에서 계산할 때마다 매번 모든 데이터를 가져와 네트워크 오버 헤드를 최대화하므로 필요하지 않습니다.

트리의 깊이에 제한이 있으면 허용되는 여러 쿼리를 하나의 거대한 쿼리로 결합하여 모든 작업을 수행하고 필요한 정확한 결과 세트를 반환 할 수 있습니다. 예를 들어 데이터를 사용했지만 A, B, C 등이 1, 2, 3으로 바뀌 었습니다 (열이 int 인 경우).

루트 노드의 모든 직접 자식 (site_id = 1)을 얻으려면 다음을 수행하십시오.

select site_id from site where parent_id = 1

루트 노드의 손자를 얻으려면 다음과 같이하십시오.

select grandchild.site_id 
from site grandchild, site child 
where grandchild.parent_id = child.site_id 
and child.parent_id = 1

루트 노드의 증손자를 얻으려면 다음과 같이하십시오.

select greatgrandchild.site_id 
from site greatgrandchild, site grandchild, site child 
where greatgrandchild.parent_id = grandchild.site_id 
and grandchild.parent_id = child.site_id 
and child.parent_id = 1

루트 노드의 모든 자손을 얻으려면 위의 쿼리를 하나의 거대한 쿼리로 결합하면됩니다.

select site_id
from site
where site_id in (
    select site_id 
    from site 
    where parent_id = 1
)
or site_id in (
    select grandchild.site_id 
    from site grandchild, site child 
    where grandchild.parent_id = child.site_id 
    and child.parent_id = 1
)
or site_id in (
    select greatgrandchild.site_id 
    from site greatgrandchild, site grandchild, site child 
    where greatgrandchild.parent_id = grandchild.site_id 
    and grandchild.parent_id = child.site_id 
    and child.parent_id = 1
)

나는 이것이 어떻게 작동하는지 보았다고 생각합니다. 각각의 추가 레벨에 대해, 자손을 검색하는 사이트에서 많은 레벨 떨어진 노드를 찾아 추가 '또는 site_id in ()'을 사용하여 수퍼 쿼리에 해당 쿼리를 추가하는 쿼리를 작성하십시오.

이제 알 수 있듯이, 3 단계만으로도 큰 쿼리가되었습니다. 말하자면, 10 개의 레벨을 지원해야한다면,이 쿼리는 거대해질 것이며 모든 OR과 IN은 속도를 떨어 뜨릴 것입니다. 그러나 모든것을 얻거나 여러 쿼리를 사용하는 것이 더 빠를 것입니다. 이 쿼리보다 가능한 수준의 임의의 양을 지원해야하는 경우에는 도움이 될 수 없습니다. 그것은 무한히 커야 만 할 것입니다. 그 경우 남아있는 것은 더 나은 방법을 사용하는 것입니다 ...

즉, 붙여 넣기를 복사하여 코딩을 시작하기 전에 임의의 깊이를 지원하고 이전 버전과의 호환성을 유지하면서 이러한 거대한 쿼리를 피할 수있는 방법이 있습니다. 데이터 모델을 변경해야하지만이 데이터 모델을 사용하는 다른 프로그램에 해를 끼치 지 않는 작은 데이터 모델입니다. 짧게는 ...

더 좋은 방법

그 답에 언급 된 ravnur와 같은 것을 사용하여 parent_paths라는 추가 열을 추가하여 각 노드에서 루트까지의 전체 경로를 인코딩합니다.

삽입, 업데이트 및 삭제시 triggers 를 사용하여 해당 열을 동적으로 채 triggers . 이제 중복 데이터를 유지 관리하고 있습니다. 다른 프로그램에 피해를주지는 않지만 귀하에게 상당한 성과 이득을 줄 수 있습니다. 여분의 열에있는 데이터가 항상 테이블의 일반 데이터와 항상 동기화되어야하므로 (아마도 가장 어려운 부분 일 것입니다) 트리거가 방탄인지 확인하십시오

ravnur가 보여준 것과 같은 짧고 달콤한 쿼리를 사용하면 parent_paths 열의 모든 위치에서 site_id의 발생을 찾아 재귀없이 해당 site_id를 사용하여 사이트의 모든 자손을 직접 가져올 수 있습니다.


유감스럽게도 데이터 모델을 변경할 수없고 MySQL을 사용하는 경우 재귀 쿼리가 필요하고 재귀 쿼리를 지원하지 않는 DBMS를 사용하고 있습니다.

Quassnoi는 흥미로운 일련의 블로그 기사를 작성하여 계층 적 데이터를 쿼리하는 기술을 보여주었습니다. 그의 솔루션은 매우 똑똑하지만 매우 복잡합니다. http://explainextended.com/2009/03/17/hierarchical-queries-in-mysql/

PostgreSQL은 재귀 쿼리를 지원 하는 또 다른 오픈 소스 RDBMS이므로 사용자가 표시하는 방식으로 저장된 전체 트리를 가져올 수 있습니다. 그러나 데이터 모델을 변경할 수 없다면 다른 RDBMS로 전환 할 수 없다고 가정합니다.

임의적으로 깊은 나무를 훨씬 쉽게 가져올 수있는 몇 가지 대체 데이터 모델이 있습니다.

  • 클로저 테이블
  • 중첩 세트 일명 수정 된 선매 트리 순회
  • 경로 열거 형화 경로

필자 는 SQL, PHP를 사용하여 계층 적 데이터를위한 모델 및 저서 인 SQL Antipatterns : 데이터베이스 프로그래밍의 함정을 피할 때이 내용을 다룹니다.

마지막으로 Slashdot 의 코드에서 주석 계층 구조에 사용 된 다른 솔루션이 있습니다. 인접 목록과 같이 "parent_id"를 저장하지만 "root_id"열도 저장합니다. 주어진 트리의 모든 구성원은 해당 트리에서 가장 높은 조상 노드 인 root_id와 동일한 값을 갖습니다. 그런 다음 하나의 쿼리에서 전체 트리를 가져 오는 것이 쉽습니다.

SELECT * FROM site WHERE root_id = 123;

그런 다음 응용 프로그램은 데이터베이스에서 배열로 다시 모든 노드를 가져오고이 배열을 반복하는 코드를 작성하여 노드를 메모리의 트리 데이터 구조에 삽입해야합니다. 많은 수의 분리 된 트리가 있고 각각의 트리가 비교적 적은 수의 엔트리를 가지고 있다면 이것은 좋은 해결책입니다. Slashdot의 경우에 좋습니다.


이를 위해 저장 프로 시저를 생성 할 수 있습니다.

다음은 mysql에서 구현 한 내용입니다.

DROP PROCEDURE IF EXISTS SearchTree;
DELIMITER go

CREATE PROCEDURE SearchTree( IN root CHAR(1) )
BEGIN
  DECLARE rows SMALLINT DEFAULT 0;
  DROP TABLE IF EXISTS reached;
  CREATE TABLE reached (
    site_Id CHAR(1) PRIMARY KEY
  ) ENGINE=HEAP;
  INSERT INTO reached VALUES (root);
  SET rows = ROW_COUNT();
  WHILE rows > 0 DO
    INSERT IGNORE INTO reached 
      SELECT DISTINCT s.site_Id 
      FROM site AS s 
      INNER JOIN reached AS r ON s.parent_Id = r.site_Id;
    SET rows = ROW_COUNT();
    DELETE FROM reached 
      WHERE site_Id = root;
  END WHILE;
  SELECT * FROM reached;
  DROP TABLE reached;
END;
go
DELIMITER ;
CALL SearchTree('B');

예상 된 결과를 반환합니다.


클로저 테이블 패턴을보고 싶을 수도 있습니다. 나는이 site 유익하다는 것을 알았다. 지금까지 내가 본 것처럼,이 개념에 대한 몇 가지 질문도 있습니다 (예 : here .





hierarchical-data