Меню
Что нового?

PHP+MySQL горизонтальные деревья

Elvis

Новичок
Добрый день!
Давно столкнулся с задачей построения деревьев из данных на основе базы MySQL. перечитал много разных способов, но подходящего не нашел. не нашел потому что архитектура базы данных строится на основе родитель-дети или другое название, но смысл тот же ID-PID. мне такой способ не подходит, потому что у некоторых "дети" могут быть несколько "родителей", а не один уникальный.
приведу пример чего хочу добиться.
допустим есть 3 элемента которые состоят из 3х других элементов.
первый элемент

Второй элемент

Третий элемент


есть так же еще один элемент в состав которого входят элементы "1","2" и "3"
но вывести нужно и "детей" этих элементов, причем если "дети" повторяются, то нужно их сосчитать и вывести количество. пример на рисунке:


есть еще такие детали как у родителя может быть только(!) трое детей, не меньше не больше, а у детей могут быть несколько родителей. если нужны еще подробности постараюсь описать.

подскажите как сделать архитектуру базы данных и направить на код PHP. конкретное решение задачи не прошу, прошу направить в правильное русло, подсказать, помочь.
 
~WR~

~WR~

Новичок
На PostgreSQL легко такое делается.
http://www.postgresql.org/docs/current/static/ltree.html

Несколько родителей - без проблем. Просто пишешь в базу все пути:
PHP: 
path
10.1.4
10.2.5
10.3.4 и т.д.
Далее шустро выбираешь любой кусок дерева по индексу
PHP: 
WHERE path ~ '10.*'
Далее группируешь простым GROUP BY + COUNT.
При необходимости, Ltree легко разбивается на отдельные ряды (функция unnest через массив) и так же легко собирается обратно (функция string_agg).

Не знаю, почему в MySQL ничего подобного нет. Видимо, всех устраивает геморрой и костыли.

Добавлено:
есть еще такие детали как у родителя может быть только(!) трое детей, не меньше не больше
Нажмите для раскрытия...
Тоже несложно. Самый простой способ - добавить в таблицу дополнительную колонку для каждой ноды, в которой будет хранится количество её детей. Триггер будет пересчитывать значение при любых изменениях. Всего один лишний select по индексу. Дальше все понятно. :)
 
флоппик

флоппик

promotor fidei
Команда форума
Партнер клуба
~WR~ написал(а):
Не знаю, почему в MySQL ничего подобного нет. Видимо, всех устраивает геморрой и костыли.
Нажмите для раскрытия...
Возможно потому что незачем пихать нелинейные данные в линейную бд... Но это чисто мое мнение.
 
~WR~

~WR~

Новичок
Можно я такое маркетологам, когда они в следующий раз попросят сделать дерево жанров? :)
В реальном мире спрос на сложные деревья есть, и никого не волнует, что у разработчика БД - линейная. *__*
 
флоппик

флоппик

promotor fidei
Команда форума
Партнер клуба
В реальном мире бд используются не только для вебсайтов, и есть другие хранилища кроме бд — в том числе, и нелинейные.
 
~WR~

~WR~

Новичок
Подскажите такое хранилище, подходящее для деревьев. И, главное, как его связать с другими данными, которые в БД?
Например, выбрать кусочек дерева и сделать JOIN за приемлемое время.

P.S. Не holywar, мне правда интересно.
 
флоппик

флоппик

promotor fidei
Команда форума
Партнер клуба
~WR~ написал(а):
Подскажите такое хранилище, подходящее для деревьев. И, главное, как его связать с другими данными, которые в БД?
Например, выбрать кусочек дерева и сделать JOIN за приемлемое время.

P.S. Не holywar, мне правда интересно.
Нажмите для раскрытия...
Вот например, даже удовлетворяет желаниям TC:
http://www.mongodb.org/display/DOCS/Database+References#DatabaseReferences-DBRef
 
флоппик

флоппик

promotor fidei
Команда форума
Партнер клуба
~WR~ написал(а):
В реальном мире спрос на сложные деревья есть, и никого не волнует, что у разработчика БД - линейная. *__*
Нажмите для раскрытия...
Мне просто напоминает, как некоторые требуют, чтоб nginx или лайти имел аналог .htaccess (per-direcory). Авторы лайти прямо заявляют, что этой фичи не будет никогда.) Естественно, если это там появится, половина преимуществ легких серверов пропадет, и получится еще один апач, и я как бы намекаю, что мускул держит нишу быстрой базы, а не убер-функциональной.
 

Sad Spirit

мизантроп (Старожил PHPClub)
Команда форума
флоппик написал(а):
...и я как бы намекаю, что мускул держит нишу быстрой базы, а не убер-функциональной.
Нажмите для раскрытия...
По странному совпадению, всякие фичи (типа внешних ключей, хранимых процедур, триггеров...) мешают производительности ровно до того момента, как их реализуют в мыскле. Как только их в мыскле наконец реализуют, мешать производительности они волшебным образом перестают. "Зелен виноград", короче.
 
~WR~

~WR~

Новичок
Продолжаем. :)

Посмотрел доки MongoDB. Нашел вот это:
http://www.mongodb.org/display/DOCS/Trees+in+MongoDB

Описываются способы хранения деревьев. Все из них - костыльные. Каждый подходит только для каких-то строго определенных целей.
В Materialized paths предлагают выбирать ноды при помощи регулярного выражения. Ну и т.д.

Чем это отличается от линейной БД? В чем профит от использования Mongo? Те способы, которые они описали, можно реализовать в MySQL, и получить те же самые недостатки каждого из них.

По сути, PostgreSQL отличает всего одна единственная вещь - GIST-индекс, который позволяет без геморроя выбрать часть дерева по условию любой сложности. Пример из документации:

PHP: 
WHERE path ~ 'Top.*{0,2}.sport*@.!football|tennis.Russ*|Spain'
begins with the label Top
and next has zero to two labels before
a label beginning with the case-insensitive prefix sport
then a label not matching football nor tennis
and then ends with a label beginning with Russ or exactly matching Spain.
Нажмите для раскрытия...
Это index scan. От детей к родителям тоже можно искать.
Ничего похожего нигде не видел. В остальном ltree - это просто текстовые поля, в которых хранятся метки, разделенные точечками.
 

Elvis

Новичок
прочитал. но все равно для меня не понятно. возможно что об PostgreSQL я вчера только узнал. я не понмаю что такое path, я не пойму где тот файл который везде используют в примерах(ltreetest.sql), я не понимаю почему там некоторые команды SQL не работают, возможно они переименованы. вообщем для Вас это легко, а для меня тяжко. можно немного больше конкретики и более проще, что ли?
 
~WR~

~WR~

Новичок
ltree - внешний contrib модуль. Его нужно установить парой команд.

Относительно корневой папки с postgresql:
cd contrib/ltree
make
make install
make installcheck
Нажмите для раскрытия...
ltreetest - там же.
Успешность установки можно проверить проще. Достаточно команды:
PHP: 
SELECT '1.2.3'::ltree
path - это имя колонки с типом данных ltree. Колонку можно называть как угодно. Мне нравится path)

Создание таблицы:
PHP: 
CREATE TABLE test_tree (
  id SERIAL,
  path public.ltree
);
Добавляем специальный индекс:
PHP: 
CREATE INDEX test_tree_path_ids ON test_tree
  USING gist ("path" public.gist_ltree_ops);
Далее пишем в базу полные пути для всех узлов.
PHP: 
INSERT INTO test_tree ("path") VALUES ('10.1.4');
INSERT INTO test_tree ("path") VALUES ('10.1.5');
INSERT INTO test_tree ("path") VALUES ('10.2.5');
...
 

Elvis

Новичок
~WR~ написал(а):
ltree - внешний contrib модуль. Его нужно установить парой команд.
Нажмите для раскрытия...
ltree является дополнением PostgreSQL и входит в пакет contrib, поэтому изначально оно не включено в стандартный пакет для *nix систем. Для установки запускаем в нужной базе данных .sql-файл /usr/local/share/postgresql/contrib/ltree.sql (C:\Program Files\PostgreSQL\8.4\share\contrib\ltree.sql для Windows).
Нажмите для раскрытия...
нет у меня в папке contrib файла ltree.sql (
 
~WR~

~WR~

Новичок
Добавили.
Теперь выбираем узлы по какому-нибудь условию. Например, узел 10 со всеми детьми:
PHP: 
SELECT *
FROM test_tree
WHERE "path" ~ '*.10.*'

Обновлено: Считаем кол-во повторений для конечных узлов:
PHP: 
SELECT *, count(*) OVER (PARTITION BY subpath("path", nlevel("path")-1, 1) 
    RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING)
FROM test_tree
WHERE "path" ~ '*.10.*'
Если window-функции сложно, то могу и без них написать - с простой аггрегацией.
 
~WR~

~WR~

Новичок
Ой, про windows не знаю)

Пишут такое:
On Windows the contrib modules are located somewhere in the installation folder of PostgreSQL whether you select them in the installation wizard or not. So you can still install the modules by manually importing the SQL script in the database you want.
Нажмите для раскрытия...
Возможно, при инсталляции можно выбрать модули. Сам не сталкивался.
 

Sad Spirit

мизантроп (Старожил PHPClub)
Команда форума
Ваще-то ltree тут особо не нужен, в достаточно свежем Постгресе (9.0+) можно просто использовать рекурсивные запросы.

Схема:
Код: 
create table items (
    id integer not null,
    name text,
    primary key (id)
);

create table relationships (
    parent integer not null,
    child integer not null,
    constraint relationships_pkey primary key (parent, child),
    constraint relationships_parent_fkey foreign key (parent)
        references items (id)
        on delete cascade on update restrict,
    constraint relationships_child_fkey foreign key (child)
        references items (id)
        on delete cascade on update restrict
);
Данные (с картинок наверху):
Код: 
insert into items values (1, 'адын');
insert into items values (2, 'дыдва');
insert into items values (3, 'тыри');
insert into items values (4, 'чатыре');
insert into items values (5, 'пьят');
insert into items values (6, 'шешть');
insert into items values (7, 'сем');
insert into items values (8, 'восем');
insert into items values (9, 'девьят');
insert into items values (10, 'много');

insert into relationships values (1, 4);
insert into relationships values (1, 5);
insert into relationships values (1, 6);
insert into relationships values (2, 7);
insert into relationships values (2, 5);
insert into relationships values (2, 8);
insert into relationships values (3, 4);
insert into relationships values (3, 9);
insert into relationships values (3, 6);
insert into relationships values (10, 1);
insert into relationships values (10, 2);
insert into relationships values (10, 3);
Выбираем дерево:
Код: 
with recursive tree (id, name, level, path) as (
    select id, name, 1, array[id]
    from items as i
    -- либо выбирать такие, которые не встречаются в relationships как child
    where id = 10
    union all
    select i.id, i.name, t.level + 1, t.path || i.id
    from items as i, relationships as r, tree as t
    where t.id = r.parent and
          i.id = r.child
)
select * from tree order by path;
Получаем в результате:
Код: 
 id |  name  | level |   path
----+--------+-------+----------
 10 | много  |     1 | {10}
  1 | адын   |     2 | {10,1}
  4 | чатыре |     3 | {10,1,4}
  5 | пьят   |     3 | {10,1,5}
  6 | шешть  |     3 | {10,1,6}
  2 | дыдва  |     2 | {10,2}
  5 | пьят   |     3 | {10,2,5}
  7 | сем    |     3 | {10,2,7}
  8 | восем  |     3 | {10,2,8}
  3 | тыри   |     2 | {10,3}
  4 | чатыре |     3 | {10,3,4}
  6 | шешть  |     3 | {10,3,6}
  9 | девьят |     3 | {10,3,9}
(13 rows)
Выбираем потомков на третьем уровне с подсчётом количества:
Код: 
with recursive tree (id, name, level, path) as (
    select id, name, 1, array[id]
    from items as i
    -- либо выбирать такие, которые не встречаются в relationships как child
    where id = 10
    union all
    select i.id, i.name, t.level + 1, t.path || i.id
    from items as i, relationships as r, tree as t
    where t.id = r.parent and
          i.id = r.child
)
select id, name, count(id) from tree
where level = 3
group by id, name
order by 3 desc, 1;
Получаем в результате:
Код: 
 id |  name  | count
----+--------+-------
  4 | чатыре |     2
  5 | пьят   |     2
  6 | шешть  |     2
  7 | сем    |     1
  8 | восем  |     1
  9 | девьят |     1
(6 rows)

Триггеры на то, чтобы
а) Предотвратить циклы
б) Ограничить число детей тремя
оставим в качестве упражнения для читателей.

И да, я думаю не стоит это ссылать в "PHP + PostgreSQL", остальным тоже мойшет быть интересно.
 

Elvis

Новичок
хм... довольно интересно.
Код: 
select id, name, count(id) from tree
where level = 3
group by id, name
order by 3 desc, 1;
я так понял что в строчке "where level = 3" мы устанавливаем какой уровень нам показать.
протестировал и убрав в коммент эту строчку стало выводить так как я и задумывал, то есть всю ветку, включая самого корневого родителя! спасибо огромное!
осталось поставить на сервер PostgreSQL вместо MySQL
 
Войдите или зарегистрируйтесь для ответа.
Сверху