Важная часть любого информационного проекта — это представление данных, в частности, формирование каталога. Сегодня появляется большое количество систем, основной задачей которых является каталогизация данных, причем в каждой из них заложены свои принципы формирования каталога, методы реализации которых часто уникальны и представляют собой «ноу-хау» разработчиков. В статье рассказывается об одном из методов создания каталога данных, который может быть интересен тем, кто впервые столкнулся с такой проблемой. Приводится пример проектирования Internet-каталога, а также разбираются основные приемы работы с ним средствами СУБД Oracle.

Перед человеком часто в том или ином виде встает задача определения порядка в хаосе окружающего мира, поиска свойств и закономерностей в поведении предметов (объектов). Другая, не менее важная задача, — классификация объектов путем их объединения по схожести свойств, поведению, строению в некие классы или категории, с дальнейшим построением из них иерархически зависимой структуры [1]. Благодаря этому картина мира становится более четкой и понимаемой. Например, в биологии — это царство, затем, в порядке уточнения, тип (отдел), класс, отряд (порядок), семейство, род и, наконец, вид. Место каждого организма в этой структуре определяется на основании внешнего и внутреннего строения тела. Немаловажной задачей, теперь уже для разработчиков информационных систем, является создание программного эквивалента подобной структуры, с которой было бы удобно и эффективно работать.

Сегодня появляется большое количество таких систем, основной задачей которых является классификация (каталогизация) данных: каталог информационных ресурсов Сети, электронная библиотека, Internet-магазин, законодательная база данных и т.п. В каждой из них заложены свои принципы формирования каталога, методы реализации которых представляют собой «ноу-хау» разработчиков. Рассмотрим один из методов создания каталога данных, который, быть может, и не уникален, но интересен и доступен для тех, кто впервые столкнулся с такой проблемой.

Принципы построения каталога

В основе любого каталога лежат три сущности: тематические разделы (категории), образующие иерархически зависимую структуру; связи, которые существуют между отдельными тематическими разделами; объекты рассматриваемой области, принадлежащие соответствующим разделам.

Объекты — любые предметы рассматриваемой области, обладающие определенными свойствами, поведением и т.п. Например, если речь идет о классификации Internet-ресурсов, то объектами можно считать сайты, посвященные той или иной теме, которая в данном случае является его свойством: скажем, www.gov.ru — органы государственной власти; www.culture.ru — новости культуры и искусства; www.movies.ru — кинофильмы; www.itar-tass.com — Информационное телеграфное агентство России.

Рис.1. Пример каталога
Все обладающие общими свойствами объекты можно выделить в группу. Объекты внутри этой группы можно разделить на подгруппы, определяемые другими свойствами, еще более конкретизирующими объект. Таким образом, можно выделять подгруппы вплоть до полного исчерпания известных свойств объектов или до нужного уровня конкретизации (абстракции). Тематический раздел — это некий уровень абстракции, классифицирующий объект, а совокупность тематических разделов образует иерархическую систему. На рис. 1 приведен пример простой иерархической структуры Web-ресурсов.

На самом верхнем уровне иерархии находится раздел «Интернет», который в данном случае является рассматриваемой областью. Он содержит такие разделы, как «Культура», «Политика», «СМИ». Те, в свою очередь, содержат другие подразделы и т.д.

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

Рис. 2. Пример каталога со связями
Некоторые группы объектов могут быть по смыслу связаны с другими группами, находящимися на других ветвях иерархии. Как это видно из рис. 1, такими связями могут обладать подразделы «Политика» и «Культура» раздела «СМИ», которые образуют смысловые связи с разделами «Политика» и «Культура». На рис. 2 эти связи указаны в виде ссылок на соответствующие разделы «СМИ».

Другими словами, все объекты, принадлежащие, например, разделу «Интернет/СМИ/Информационные агентства/Политика», могут быть отнесены в виртуальный подраздел «Политические новости» раздела «Интернет/Политика».

Основные атрибуты, которыми должны обладать связи, — это идентификатор раздела, содержащий объекты; идентификатор раздела, к которому привязывают эти объекты и псевдоним виртуального подраздела.

Помимо описания связей между разделами может возникнуть необходимость описать связи между отдельными объектами и разделами. Например, в разделе «Интернет/СМИ/Информационные агентства» может находиться сайт информационного агентства, который освещает события как политики, так и культуры. Было бы желательно, чтобы этот сайт был также виден из раздела «Интернет/Политика», не привязывая к нему целый раздел «Информационные агентства». Для описания такой связи («раздел-объект») можно определить новую сущность с атрибутами: идентификатор раздела, к которому нужно привязать данный объект и идентификатор этого объекта.

Представление каталога в базе данных

Рис. 3. Схема базы данных
Определив три основные сущности каталога и его атрибуты, мы тем самым определили три таблицы базы данных и отношения между ними [2]. На примере проектирования Web-каталога, схема базы данных в нотациях UML [3] будет иметь вид, представленный на рис. 3.

Схема описывает три типа таблиц.

  • OBJECTS - таблица, содержащая объекты: id - идентификатор объекта; category_id - идентификатор раздела, к которому принадлежит объект; title - название объекта; url - адрес в Internet; description - описание объекта.
  • CATEGORIES - таблица, содержащая тематические разделы: category_id - идентификатор тематического раздела; parent_id - идентификатор родительского раздела; title - название раздела; description - описание раздела.
  • LINKS - таблица, содержащая описание связей между тематическими разделами: id - идентификатор связи; source_id - идентификатор раздела-источника; destination_id - идентификатор раздела, содержащего ссылку на источник; alias - псевдоним ссылки.

На языке SQL эти таблицы со всеми ограничениями целостности создаются следующими командами [4]:

Основная идея построения дерева заключена в соответствующей структуре таблицы CATEGORIES, в которой есть два поля: category_id и parent_id. Первое содержит уникальный идентификатор тематического раздела, а второе идентификатор родительского раздела, к которому принадлежит данный раздел (таблица 1). Причем одному и тому же родительскому разделу может принадлежать сколь угодно много дочерних разделов.

Допустим, таблица LINKS выглядит, как указано на таблице 2, а OBJECTS — как указано на таблице 3.

Для наглядности рассмотрим некоторые примеры SQL-запросов с использованием синтаксиса Oracle 9i. Добавление таких конструкций как START WITH и CONNECT BY в предложение SELECT позволяет делать различные выборки в каталоге одним запросом, избавляя разработчиков писать громоздкие хранимые процедуры. Эти конструкции являются внутренним стандартом Oracle, но реализация показанных далее запросов возможна и для других СУБД, в которых имеется возможность использования процедурного языка запросов.

Пример 1. Вывод заданной ветви каталога
сверху вниз
SELECT category_id, parent_id, title
FROM categories
START WITH category_id = 4
CONNECT BY PRIOR category_id = parent_id;

Конструкция START WITH указывает, с какого раздела следует начать движение по дереву, CONNECT BY связывает номера разделов поля category_id, с соответствующими номерами разделов поля parent_id. PRIOR, стоящий перед category_id, указывает на то, что поле category_id идентифицирует тематические разделы.

Результатом запроса будет вывод заданной ветви каталога, начиная с раздела ?СМИ? и заканчивая всеми ее подразделами (таблица 4).

Пример 2. Вывод заданной ветви каталога
снизу вверх
SELECT category_id, parent_id, title
FROM categories
START WITH category_id = 5
CONNECT BY category_id = PRIOR parent_id;

В этом запросе PRIOR стоит перед parent_id. Это означает, что поле parent_id идентифицирует тематические разделы, а поле category_id наоборот как бы становится ссылкой на родительский раздел. Благодаря этому, движение по дереву будет осуществляться снизу вверх. Результатом запроса будет вывод ветви каталога, начиная с раздела ?Музыка? и заканчивая самым верхним разделом ?Интернет? (таблица 5).

Заключение

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

Литература
  1. Г. Буч, "Объектно-ориентированный анализ и проектирование с примерами приложений на C++", 2-е издание. "Невский диалект", 1998
  2. К. Дж. Дейт, "Введение в системы баз данных", 7-е издание. "Вильямс", 2001
  3. Г. Буч, Д. Рамбо, А. Джекобсон, "Язык UML. Руководство пользователя". ДМК, 2000
  4. Д. Грофф, П. Вайнберг, "SQL: полное руководство", 2-е издание. "BHV-Киев" диалект", 2001

C Максимом Рябенко (МФТИ) можно связаться по электронной почте по адресу maxy@rt.mipt.ru.