У ZendFramework теперь есть полноценный layout

Модуль Zend_Layout перебрался из инкубатора в основную ветку. Ура! Непонятно почему создатели этого фреймворка не начали с создания именно удобной структуры самого паттерна MVC, а озаботились совершенно второстепенными вопросами. И только теперь дело дошло до правильных View. Шустрые пользователи ZendFramework уже настрочили неплохой пример использования: http://akrabat.com/2007/12/11/simple-zend_layout-example/

Построение деревьев

Небольшое введение. Весь пост написан с оглядкой на MySQL, из-за ее распространенности в web. Конечно, у Oracle возможностей больше, но хостинг с Oracle (или, например, с PostgreSQL) поискать еще надо. Нас же интересует практическое применение в веб-приложениях и обычных сайтах. Для построения сложных систем вообще надо сильно подумать над возможностью применения реляционной БД и рассмотреть другие варианты. Ведь не строчно-табличным видом все БД ограничиваются. Основным посылом к написанию этого поста послужили частые обсуждения темы хранения древовидных структур на различных форумах и комьюнити. Я с удивлением узнал, что многие люди просто не знают методов, отличных от первого, "родитель-дети". Я точно помню, что в начале 90-х видел статью, посвященную этой проблеме, но уже не помню где. Может, вPC Magazine или в Компьютерпресс? Может даже это было в безруковской Софтпанораме. Так или иначе статья я не нашел, может, плохо гуглил.

Родитель-дети

Это самый распространенный и простой паттерн для хранения деревьев. Многочисленные реализации его можно увидеть в различных форумах, системах комментирования и т.д. Суть этого паттерна видно на картинке справа — каждый элемент хранит ссылку (идентификатор) на родителя вкачестве внешнего ключа. На картинке PK — primary key, FK — foreign key. Типичное отношение один ко многим.

Добавление и изменение. Никаких проблем с добавлением и изменением, указываем ID родителя и дело сделано.

Удаление. С удалением сложнее. При простом удалении элемента возникает проблема потерянных детей, поэтому придется в приложении отслеживать удаление элемента и реализовывать логику действий с дочерними элементами удаляемого. Типичные решения:

• не удалять, а помечать как удаленный
• переносить прямых потомков в подчинение к родительскому элементу удаляемого
• переносить всех потомков (прямых и непрямых — т.е. потомков потомков) в корень.

Выборка. Это проблемное место. Возможностей простой выборки немного. По сути этот паттерн дает возможность лишь выбрать всех прямых потомков элемента. Выбор всех потомков, прямых и непрямых, постоение пути от корневого элемента (выбор всех родителей) — реализуются рекрсивными функциями в самом приложении или многочисленными JOIN'ами.

Количество элементов и уровни вложенности — практически бесконечны, зависят от размерности поля ID.

Итог. Паттерн очень удобен для добавления и перемещения элементов. Хорошо подходит для часто изменяемой структуры, часто добавляемых данных, множественного добавления. За эту производительность придется расплачиваться снижением производительности при выборке данных, причем часто весьма значительной. Как я уже написал, многие форумы и системы комментирования построены на этой схеме и владельцы сайтов часто сталкиваются с проблемой производительности именно на выборке данных. Не стоит забывать, что сайт посещают не только люди, но и поисковые машины и для каждого запроса строится дерево.

Для разработчиков, использующих этот паттерн в своих приложениях, будет полезен список частых запросов, составленный по материалам коммьюнити ru_mysql в livejournal. Изображение со схемой этого паттерна я там и взял.

Materialized Path

Несмотря на страшное английское название, это очень распространенный паттерн, наиболее близкий к общепринятой человеческой логике. С этим паттерном мы сталкиваемся постоянно, просто не знаем, что он так называется. Библиотечные списки, URL в браузере и даже Библия. Суть этого паттерна заключатся в том, что каждый элемент хранит полный путь до себя от корня. Напрмер: "УК РФ, часть 22, раздел 8, глава 21, стятья 159, параграф 2".

Добавление и изменение. Сложнее, чем в схеме "Родитель-дети". Для добавления элемента, необходимо получить путь (ID) родительского элемента и добавить к нему свой ID. С изменением сложнее, необходимо пересчитывать ID, (фактически — пути), всех дочерних элементов, прямых и непрямых.

Удаление. С удалением все гораздо интереснее, простое удаление любого элемента не влечет за собой нарушения целостности дерева. Потомки удаленного элемента все еще являются непрямыми потомками родителей удаленного. Дети мертвых родителей — не сироты, у них есть бабушки и дедушки. ;-)

Выборка. Это сильная сторона этого паттерна. Для выборки с помощью простых запросов доступны различные варианты, вызывающие головную боль при использовании метода "родитель-дети". ID всех родителей (полный путь) от корня — вообще без проблем. Все потомки, прямые и непрямые? Пожалуйста.

SELECT * FROM ... WHERE ID LIKE '00010001%'

Это очень удобно для построения различных каталогов — например запрос "первые три подраздела с наибольшим количеством элементов, с учетом вложенных" реализуется гораздо проще, без множества рекурсивных вызовов.

Количество элементов и уровни вложенности. Проектирование этих параметров целиком на совести разработчика. На самом деле бесконечное количество уровней вложенности нужно не так уж часто — если вложенность разделов на сайте приближатся к 20-ти, надо подумать о перепланировке сайта, а не об увеличении уровней.

Реализации этого метода различаются. Поле с ID-путем может быть битовым или текстовым. Текстовое поле может содержать элементы, разделенные каким-нибудь символом, например точка (1.1.2.5) или обратный слэш ('\program files\warez\dowload'). Для простоты работы с текстовым полем обычно используют фиксированное количество символов для каждого уровня, дополненные, например, нулями (0001000100020005 — четвертый уровень, по 4 символа на каждый). Это позволяет просто по длине строки определить уровень, получить ID родителя и т.д. Кроме того, кто сказал, что для нумерации нужно использовать только цифры? Добавив в схему латинский алфавит, получим нумерацию в 36-ричной системе (10 цифр+26 букв).

Итог. Для частых выборок и добавлений, минимальнымх изменений структуры. Необходимо тщательное планирование системы идентификаторов, невозможно применять автоинкрементные поля, т.е. формирование ID ложится на плечи программиста. ID типа VARCHAR(255) тоже не вдохновляет, особенно любителей семантики — ведь текстовое поле, о ужас (!), хранит вовсе не текстовые данные. :-)

Немного сумбурное описание реализации, зачем-то совместно с паттерном "родитель-дети", можно найти на сайте PHPClub.

Nested Sets — вложенные наборы.

Паттерн, несколько более сложный для понимания. Оставим в стороне рассуждения о том, что делали программисты LAMP, когда в школе проходили тему множеств. Будем считать, что они знали, но забыли. Или еще не проходили эту тему. :-) Тем не менее, в популярных скриптах этот метод используется гораздо реже, чем первые два. Идея паттерна аналогична предыдущему — упростить выборку дочерних элементов. Однако в отличие от Materialized Path, элемент в явном виде не хранит информацию о пути. Зато позволяет вычислить путь, основываясь на ID элемента. Для этого элемент хранит не только свой номер, но и ID соседей того же уровня. Если соседа того же уровня нет, то хранится ID элемента уровня выше.

На рисунке выше, элемент 1 знает, что его сосед "слева" — 0, "справа" — 3. У элемента с номером 3 — соседи 1 и 9, у элемента 6 — 5 и 9.

• Сколько элементов, дочерних элементу 3? 9-3=6 (включая сам элемент 3). Или 9-3-1=5 (исключая сам элемент номер 3).
• Каковы родители элемента 7? Все элементы, чьи "соседи слева" меньше 7 (ID) и "соседи справа" больше 7 (ID). Под этот запрос попадают элемент 3 и 6.

Рисунок у меня получился немного не наглядный. "Лево" и "право" получились "верх" и "низ". Зато для людей, мыслящих строками таблиц привычнее. ;-)

Добавление и изменение. Крайне затратные процедуры, требующие пересчета как своего ID,  так и номеров соседей, а также пересчет соответствующих полей у соседей и родителей. В среднем пересчет затронет половину (sic!) записей в таблице.

Удаление. Удаление, по идее, тоже затратная процедура, также требущая пересчета границ и ID. Однако это возможно отложить и выполнять фоновым заданием или делать по расписанию. Простое удаление элемента не влечет выпадения из дерева дочерних элементов, они все также попадают в границы родителей и становятся подчиненными родителям родителя. Так, при удалении элемента 6, элементы 7 и 8 будут принадлежать элементу 3.

Выборка. Ради этого и были все навороты. Как написано выше, ID дочерних, прямых и непрямых, элементов (и их количество) можно вообще просто высчитать, не обращаясь к БД. При условии, конечно, что удалялись элементы правильно, с пересчетом границ. Ну и ID элементов должны быть целочисленными. Построение пути до корня также описано выше.

Количество элементов и уровни вложенности. Это также сильная сторона паттерна. Количество элементов и уровней вложенности, как и в первом случае с "родителем-детьми" зависит от реализации целочисленного типа поля у БД и может не заботить проектировщика. Ну, до известных пределов, конечно.

Итог. Подходит для частых выборок и редких добавлений или изменений. Ограничение по вложенности не давит на мозг :-) и не требует предварительных расчетов. Вполне подойдет для различных каталогов. Например, каталогов товаров.

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

Есть еще интересная модификация этого метода, основанная на том, что ID могут быть не целочисленными, а границы не соприкасаться. Ведь если на моем рисунке представить, что у элемента 1 "правая" (нижняя) граница не 3, а 2,3 (две целых три десятых) то у нас остается место для безболезненной вставки элементов. Главное при этом, рассчитывать границы добавляемого элемента с "зазором", т.е. вставляя элемент между 1 и 3, установить ему границы 2,4 слева и 2,8 справа, т.е. все время оставлять некий свободный интервал. При использовании этого метода могут получиться элементы с ID бесконечно малыми :-)

Итого

Конечно, это только наиболее частые решения, наверняка есть методики, о которых я не потрудился узнать. Идеальных решений нет. :-) Реляционные БД (RDBMS) вообще не очень хорошо приспособлены для хранения древовидных структур, но это уже совсем другая тема. Приходится выбирать с учетом планируемых действий и мириться с теми или иными недостатками в каждом конкретном случае. Главное, что есть из чего выбирать.

Ссылки на материалы использованные и неиспользованные.

CakePHP l10n

Собственно этот пост скорее всего лучше было бы не писать, а просто положить ссылку в del.icio.us. А вдруг еще кому-нибудь пригодится? :-) На данный момент это, пожалуй, самое подробное описание локализации CakePHP 1.2.

Добавить совершенно нечего. :-)

Такая вот история

8 мая 1886 года в небольшом тогда американском городе Атланта, на заднем дворе дома, фармацевт Джон Пембертон сварил в медном тазу не совсем обычный сироп. Джон позвал своего бухгалтера Френка Робинсона и поделился с ним открытием:

— Френк, друг, попробуй, что у меня здесь вышло!
— А в этом что-то есть, Джон! Запиши быстрее рецепт, а то забудешь!

Сироп, был сладким и густым. Джон отнес его в самую крупную в городе "Аптеку Джекобса". В тот же день первые порции сиропа, по пять центов за стакан, были проданы посетителям. Вскоре продавцы в "Джейкобсе" стали смешивать сироп с газированной водой. На протяжении своего первого года существования "Кока-Колу" раскупали в количестве девяти стаканов в день.

Pagination в CakePHP 1.2. Небольшая хитрость

Как уже писал, Containable behaivior, который отлично справляется с задачей выборки только нужных для данного действия (action). И при небольшой модификации отлично работает с методом pagination. Однако есть одна неприятная вещь, опять же связанная с тем, что pagination вызывает последовательно 2 метода модели — сначала для подсчета количества записей, а потом для выборки.

При попытке подсчитать количество записей у модели с большим количеством связей, paginator делает SQL запрос SELECT COUNT(*) со всеми положенными JOIN'ами, что при больших объемах данных существенно увеличивает время выполнения запроса. Особенно, если при этом еще и сортировку делать надо. Этот факт сильно раздражает, если в итоге нужно всего-лишь количество записей в основной модели.

Выход есть. Разглядывая код метода paginate, обнаружил, что Cake пытается сначала вызвать метод paginateCount, а если его нет, то вызывает findCount.

Ура! Определяем в модели метод paginateCount:

function paginateCount($conditions, $recursive)
{
   return $this->findCount($conditions, -1);
}

и готово!

Теперь paginate считает записи только в нужной нам модели, не вызывая JOIN'ов, а возвращает записи со всеми нужными дополнительными данными.

В общественном парижском туалете есть надписи на русском языке

В 70 годах у советских военных, да и не только у них, были очень популярны американские компьютеры. Покупка такого компьютера была настоящей спецоперацией, возможно с участием КГБили ГРУ, потому, что эти компьютеры было запрещено экспортировать в СССР. Понятно, что в промышленных количествах получать американские компьютеры было невозможно и советские инженеры вовсю копировали импортную технику. Продукция компании Digiatal (PDP, VAX), если не путаю, вдохновила на создание серии СМ ЭВМ, а продукция IBM — ЕС ЭВМ.

Американские разработчики, конечно, были в курсе, что их компьютеры пользуются повышенным спросом за "железным занавесом" и активно там копируются. Создатели процессора CVAX, который использовался в компьютерах VAX 3000 и VAX 6200 даже оставили на кристалле послание для русских инженеров, которые будут копировать их чип.

Написано: «СВАКС... Когда вы забатите довольно воровать настоящий лучший»

У известной компании Hallmark, выпускающей открытки, есть слоган: «When You Care Enough to Send the Very Best» («Когда вы заботитесь о том, что бы послать самое лучшее»). Американские инженеры немного переделали его и, как могли, перевели на русский. В английском варианте это должно было выглядеть так: «CVAX — when you care enough to steal the very best», а на русском: «CVAX — когда вы заботитесь о том, что бы украсть самое лучшее». Ну, плохое знание языка американцам простительно. :-)

Ругайтесь по-русски

Картинка из раздела "юмор" бортового журнала испанской авиакомпании Vueling Airlines. Взято у schreibikus.