Не знаю, с какой стороны подойти... Поэтому хотелось бы услышать мнения, пусть даже с изменением структуры БД

Введение
Пользователи, но не линейный список, а в виде дерева.
Скажем, есть краевой офис, далее городской, далее районный, потом уже конкретное здание.
Пример: почта России.
Соответственно, пользователи организованы в виде дерева (о структуре ниже).

Также есть заявки, и их можно комментировать.
Но, чтобы знать, какие сотрудники не прочитали ещё заявки...
Или чтобы сам сотрудник видел, что к заявке есть комментарий, то...
Надо отображать количество заявок с изменениями.

Пример
- Есть почта России
- Есть Дальневосточный филиал
- Сотрудница в 9-м отделе в 3 филиале пишет, что она не может выйти в админ. панель - проблема со входом.
- Заявка попадает в базу
- Эту заявку видят все вплоть до головного офиса в Москве
- Заявку читают системщики, и она отмечается как прочитанная
- Смотрят, что никто в городе это исправить не может, и пишут комментарии
- Так заявка доходит до окружных системщиков (поднялась уже на 8 уровней вверх по дереву)
- Окружные системщики поняли, что надо делать, добавили комментарий "Завтра приедем" и приняли заявку

База данных
Использую MySQL + PHP

Таблица `user`:
UserId | ParentId | Name
Подчинение не по типу групп "Бухгалтерия", "Менеджеры".
Тут вариант такой: Петров (директор филиала), у него замы (Тыров и Монетин), у каждого из замов по профилю другие сотрудники, у тех в подчинении свои и т.д.

Таблица `document`:
DocumentId | UserId | Title | Text
UserId - кто добавил заявку (документ).
Если добавил директор филиала, то нижестоящие сотрудники не видят эту заявку, а вот выше по леснице видят.

Пример дерева пользователей

1. Вложенность может быть до 200 уровней, может и больше, но не больше 1000 (я надеюсь  )
2. Ввиду, скажем, расширения фирмы, будут добавляться новые пользователи, некоторые будут удаляться (увольняться).
3. Родители в дереве меняться практически не будут (за очень-очень редким исключением)

Отображение изменений


Основным вариантом думал - это:
- Создать таблицу `document_view`: ViewId | DocumentId | UserId | ViewDate
- При просмотре документа добавлять запись в эту таблицу
- При добавлении комментария (изменении документа) удалять все записи с необходимым DocumentId
- Показывать количество через JOIN, но...

Вот тут, собственно, и начинается сложность... 
Как отобразить, сколько документов с изменениями, чтобы в дальнейшем показать список этих самых документов?
Ведь, надо показать только количество документов, которые доступны в ДВ округе, то есть как-то заиспользовать дерево пользователей (вложенность)?

P.S.:
К почте России никакого отношения не имею 
Взял просто для примера, можно взять также вариант заправки, закусочной, того же ДНС и т.д.

Это сообщение отредактировал(а) fridkaratel - 15.6.2012, 12:58

Ну первое - это сразу перестройте структуру таблицы user на использование nested set, сильно упростит жизнь в будущем.
И второе - не предусмотрена система комментирования комментария. Может, Пупкин не разобрался и фигню написал? так об этом нужно оставить комментарий, причём привязанный не к доукменту, а к комментарию именно Пупкина. Так что документы с комментариями придётся тоже хранить в виде дерева. И тоже в форме nested set, вероятно.


У них дата комментирования больше даты просмотра. Всего-то...

Akina, поправил текст поста... исправил на более соответствующий...

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

Это сообщение отредактировал(а) fridkaratel - 15.6.2012, 13:05

Nested set в полный рост


Тривиальный отбор по наличию потомка


Фильтрация по подзапросу

Akina, спасибо за ответы.

1. Ох, и так, и так пытался обойти nested sets.. Видимо, пришло время 

2. Вопросов нет, тут понятно

3. То есть через WHERE UserId IN (SELECT...)?

Как вариант - если не получится построить запрос с прямым связыванием таблиц.

Подитог...

1. Таблица пользователей через nested sets
2. Таблица заявок (документов): DocumentId | UserId (необходимый минимум)
3. Таблица комментариев к заявкам: CommentId | DocumentId | UserId | CreationDate (это минимум, будем считать, что комментарии комментировать нельзя)
4. Таблица просмотров заявок: ViewId | DocumentId | UserId | ViewDate

Akina, не совсем понял про прямое связывание...
Получить количество заявок с непрочитанными документами можно одним запросом?

Как-то не совсем понимаю, как можно организовать хранение комментариев через nested sets, ведь сама структура nested sets подразумевает как можно меньшее количество добавлений в базу, или нет?

Это сообщение отредактировал(а) fridkaratel - 15.6.2012, 16:01

Да никогда! структура предназначена для быстрой работы с древовидными данными, когда необходимо эффективно работать с ветвями/предками/потомками. Всего лишь.


Возможно. А возможно, что и нет. Это надо будет смотреть конечную структуру... а если да - то смотреть эффективность обеих версий запросов.

Akina, спасибо за все ответы! ;)

Перестроил таблицу для хранения пользователей на nested sets...
Возник вопрос - можно ли будет выбрать список пользователей вверх по дереву, но до определённого условия?

Например, автослесарь согласовал с директором и сказал, что все вопросы касаемо автомобилей не поднимать выше меня.
Я - конечная инстанция.
В базе бы вводим доп. столбец "Breaker", ставим туда true (1).
Если директор смотрит заявки, то он не видит заявок, которые от автослесаря (breaker'а и ниже по лестнице).
Такое получится сделать одним запросом?


Касаемо моего вопроса, реализовал так (на тестовых таблицах):

Может, есть какие замечания?

Это сообщение отредактировал(а) fridkaratel - 16.6.2012, 07:55

Подумал, подумал, и отказался от nested sets...
Ввиду возможного перемещения веток дерева, добавления новых элементов, удаления отдельных нодов, решил оставить таблицу с пользователями на Materialized Path.

Вот такой запрос на выборку измененённых заявок:


Всё же, nested sets больше подходит для статичного дерева...
Если надо переместить элемент в другую ветку или же удалить родителя и сместить детей вверх к над-родителю, то надо та-а-кое нагородить, что ###... 

Поэтому, как было materialized path, пусть так и останется...
Да и администрировать это дело легче нежели NS - глянул в phpmyadmin - и всё понятно, что и где.

Не знаю, насколько быстрый мой вариант выборки, может будут советы/замечания?
А то, как-то LIKE мне не нравится, но думаю, что он лучше, чем IN, т.к. в IN может быть и 40 элементов 

Это сообщение отредактировал(а) fridkaratel - 17.6.2012, 07:49

хранимую процедуру? скопировать, откорректировать под свою структуру, отладить и забыть? конечно, это очень сложно...


В общем случае это неверно.

Читал про хранимые процедуры... Читал про триггеры...
Минус: Большие и сложные конструкции
Плюс: Уже всё готово - заменяй поля и вставляй 

Попутно, пока изучал, наткнулся на страницу, где подробно рассказывается о трёх методах хранения деревьев и прилагаются результаты тестирования скорости...
Как-то NS не очень-то и быстро работает...
Да и... для меня в понимании NS сложноват - а MP открыл в phpmyadmin, и всё сразу видно...


То есть? Расскажи поподробней, пожалуйста.
Конечно, я могу всего не знать, т.к. MySQL у меня не по профилю, я не специалист по БД... ;)

Примечание
У меня будет довольно часто меняться структура пользователей (дерева карьерной лестницы, как в моём примере).
Основной кастет (директора, замы) меняться практически не будут, но вот подчинённые ноды (работники) могут добавляться (70%), удаляться (10%) и перемещаться (20%).
Если использовать MP, то всё сводится к REPLACE WHERE LIKE %...
Единственное, что вижу плохого в MP - это то, что надо хранить весь путь предков в TEXT, что увеличивает размер БД, но... ну и ладно, пусть увеличивает 

К тому же, я могу в MP (как писал выше) сделать breaker'а без особых проблем - просто обрезать ему список предков до него самого (и всем дочерним нодам соответственно)...
Во-от...

Здесь важен не столько сам факт возможности модификации дерева, сколько важно отношение количества модификаций к количеству чтений.

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

Лайк с "%" в начале лайкпаттерна исключает возможность использования индекса. In вполне может использовать индекс. MP позволит сэкономить вам трошку ресурса на реорганизации струтуры, что у вас будет происходить весьма редко, но существенно замедлит отбор, который, вероятно, будет весьма част.

Zloxa, большое спасибо за ответы!

На скольки записях будет чувствоваться превосходство NS перед MP?
Планируется, что пользователей будет не больше 100 000, вложенность - максимум 300 уровней.

Отбор
Да, редактироваться будет куда меньше раз, чем считываться 
Вставка записей: ~100 раз в месяц
Удаление: ~10 раз в месяц
Перемещение: ~10 раз в месяц

1. То есть, всё же заиспользовать NS?

2. Перейти с LIKE на IN?
Есть на уме вариант такой:
- Выбрать Parents у пользователя
- На PHP разложить в массив
- Задействовать IN вместо LIKE

Сейчас же использует реализация одним запросом через JOIN ... LIKE %.

P.S.:
Кстати, думал сделать отдельную таблицу, в которой был бы список всех родителей, относящихся к элементу по типу UserID => ParentId.
Например, путь ":1:2:3:4:5:13:" выглядел бы в таблице так:
13 - 5
13 - 4
13 - 3
13 - 2
13 - 1

Но потом прикинул, сколько же записей будет, если будет 100 000 пользователей с 300 уровнями вложенности... 

Это сообщение отредактировал(а) fridkaratel - 18.6.2012, 09:05

Если я правильно понял, это реаляционная реализация материализованного пути.
Ее преимущество - возможность использования индекса при отборе.
Недостаток - объем.

3 млн? Что вас пугает? Вы же не собираетесь постоянно сканировать эти 3млн. Я так понимаю вам из этих 3млн единоразово, редко придется отбирать более 300 записей. Индексы придуманы как раз для таих случаев.

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


У всех разные пороги чувствительности.  В ряде задач и двух часовой отклик вполне приемлем, и оптимизация его до часа, полутора  может оказаться не обоснованной. 
Здесь вам решать. 
В конце концов нагенерить 100к суррогатных данных, чтобы померить таймигни - задача не выглядит тяжело реализуемой, как если бы вам требовалось бы нагенерить десятки миллиардов.

Добавлено через 8 минут и 27 секунд

=3 раза в день.
Фирма действительно нанимает по три сотрудника в день?
А увольняет раз в три дня?

Хорошая, динамично растущая фирма.   

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