Технические науки



бет43/79
Дата10.12.2016
өлшемі8,18 Mb.
#3601
1   ...   39   40   41   42   43   44   45   46   ...   79
А.А. Абдурахманова, А.Е. Бакирбаева

(КГУТиИ им. Ш.Е. Есенова, г. Актау)
СПОСОБЫ ХРАНЕНИЯ ИЕРАРХИЧЕСКИХ СТРУКТУР В РЕЛЯЦИОННОЙ БАЗЕ ДАННЫХ
Проблема хранения иерархических структур довольно часто встречается на практике. Реляционные базы данных являются наиболее проверенным и распространенным средством представления данных на дисковых накопителях, однако задача отображения деревьев в реляционной БД может иметь несколько интересных решений.

Список смежных вершин

Дерево, как мы знаем, является особой формой направленного ацикличного графа. Приведем одним из способов представления такого графа:



create table fruit (

parent varchar (100),

title varchar (100)

;

Каждая запись данной таблицы с идентификатором в поле title ссылается на своего непосредственного родителя, указанного в поле parent.

Этот наиболее, пожалуй, элегантный простой, и распространенный способ хранения деревьев в реляционной базе данных называется «список смежных вершин» или метод рекурсии.

Данное дерево отобразится в следующую таблицу:

+----------+---------+

| parent | title |

+----------+---------+

| | Food |

| Food | Fruit |

| Fruit | Green |

| Green | Pear |

| Fruit | Red |

| Red | Cherry |

| Fruit | Yellow |

| Yellow | Banana |

| Food | Meat |

| Meat | Pork |

+---------+----------+

Используя данный метод, невозможно стандартными средствами SQL сделать рекурсивную выборку, поэтому обычно такие выборки выполняются не на стороне сервера БД. Приведем пример PHP кода по обходу такого дерева:

function traverse_children($parent, $level) {

$result = query('SELECT title FROM tree '. 'WHERE

parent="'.$parent.'";');

while ($row = fetch_array($result))

traverse_children($row['title'], $level+1);
С другой стороны, задачи модификации структуры такого дерева являются тривиальными и быстрыми.

Некоторые базы данных поддерживают такой метод представления деревьев на внутреннем уровне, с помощью различных SQL расширений. К примеру, в СУБД Oracle рекурсивный запрос реализуется следующим образом:



select 'TRUE' from (

select title from fruit

connect by prior parent = title

start with title = 'Banana'

) where title = 'Food';

Резюмируя, можно отметить, что данный способ подходит для систем с малым количеством выборок и «толстым» клиентом, хранящим, состояние дерева в памяти и является неэффективным в системах с частными рекурсивными выборками.

Плюсы:

  • Очень быстрые операции изменения структуры дерева, не зависящие от размера дерева

Минусы:

  • Медленные рекурсивные выборки


Полный путь

Следующим по распространенности является метод полного пути. Он заключается в том, что мы сохраняем некоторый путь, описывающий уникальное положения элемента в дереве. В качестве такого пути обычно выбирается строка, состоящая из идентификаторов всех родителей данного элемента, разделенных некоторым символом, скажем «/».


/1/

/1/2/

/1/2/3/

/1/2/3/4/

/1/2/5/

/1/2/5/6/

/1/7/

/1/7/8/

/1/7/9/
Таблица выглядит следующим образом:

+----+----------+--------+----------------+



| id | title | parent | path |

+----+----------+--------+----------------+

| 1 | Food | 0 | /1/ |

| 2 | Fruit | 1 | /1/2/ |

| 3 | Red | 2 | /1/2/3/ |

| 4 | Cherry | 3 | /1/2/3/4/ |

| 5 | Yellow | 2 | /1/2/5/ |

| 6 | Banana | 5 | /1/2/5/6/ |

| 7 | Meat | 1 | /1/7/ |

| 8 | Beef | 7 | /1/7/8/ |

| 9 | Pork | 7 | /1/7/9/ |

+----+----------+--------+-----------------+

Пример SQL выборки из такого дерева:

SELECT * FROM fruit WHERE path NOT LIKE ‘1/2/%’ ORDER BY path

Результат:

+----+--------+--------+-----------------+

| id | title | parent | path |

+----+--------+--------+-----------------+

| 1 | Food | 0 | /1/ |

| 2 | Fruit | 1 | /1/2/ |

| 7 | Meat | 1 | /1/7/ |

| 8 | Beef | 7 | /1/7/8/ |

| 9 | Pork | 7 | /1/7/9/ |

+----+--------+--------+-----------------+


Этот метод является чисто практическим, и его формализация непростая задача:

Плюсы:

  • Быстрые выборки

  • Достаточно быстрые операции изменения структуры дерева

Минусы:

  • Возможное ограничение глубины дерева, диктуемое лимитом длины поля пути конкретной базы данных

  • Слишком «практический» способ, не поддающийся формализации.



Вложенные множества

Еще одним способом представления деревьев, предложенным Джо Селко в своей книге «SQL for Smarties», являются вложенные множества. Корень дерева является множеством, содержащим в себе все остальные множества, и отношение родитель – потомок выражается вложением одного множества в другое.



Каждому элементу дерева назначается два целых числа: «правое» и «левое», именно с помощью этих чисел формируются вложенные множества.

Основное правило вложенности элемента звучит так: узел [clft, crgt] является (косвенным) потомком узла [plft, prgt], если выполняется условие:

plft < clft && prgt > crgt

Ориентированный на работу с множествами, данный метод является одним самых естественных по отношению к SQL.



Представим данное дерево в виде таблицы:

+--------+-------- +-----+-----+

| parent | title | lft | rgt |

+--------+---------+-----+-----+

| | | 1 | 18 |

| Food | Fruit | 2 | 11 |

| Fruit | Red | 3 | 6 |

| Red | Cherry | 4 | 5 |

| Fruit | Yellow | 7 | 10 |

| Yellow | Banana | 8 | 9 |

| Food | Meat | 12 | 17 |

| Meat | Beef | 13 | 14 |

| Meat | Pork | 15 | 16 |

+--------+--------+-----+------+

Приведем пример типичной выборки:

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;

Результат:

+--------+------- +-----+-----+

| parent | title | lft | rgt |

+--------+--------+-----+-----+

| Food | Fruit | 2 | 11 |

| Fruit | Red | 3 | 6 |

| Red | Cherry | 4 | 5 |

| Fruit | Yellow | 7 | 10 |

| Yellow | Banana | 8 | 9 |

+--------+--------+-----+-----+

Примечательной особенностью данного метода является также его математическая обоснованность. Скажем, количество потомков вычисляется простой формулой:

descendants = ( rgt – lft - 1) / 2

Можно с уверенностью сказать, что данный метод идеально подходит для статических, мало изменяемых иерархических структур и что, он начинает «проседать» в больших динамических структурах, так как приходится пересчитывать «правые» и «левые» числа практически у всех элементов при малейшем структурном изменении.

Плюсы:


  • Быстрые выборки

  • Естественное представление дерева с помощью SQL

  • Вычисление количества потомков без лишних обращений к базе данных.

Минусы:

  • Очень медленные операции изменения структуры дерева, возрастающие по времени с увеличением дерева.



Достарыңызбен бөлісу:
1   ...   39   40   41   42   43   44   45   46   ...   79




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет