Одним из перспективных направлений развития компьютерных систем является создание баз данных третьего поколения. Требования к ним сформулированы в Манифесте Комитета по развитию функциональных возможностей СУБД [1]. Содержание Манифеста свидетельствует о существовании некоторого разрыва (несогласованности) между реляционным и объектно-ориентированным подходами к описанию данных. Указанную несогласованность можно устранить при помощи теории паттернов.
В период с 1960 по 1970 годы известный американский математик Ульф Гренандер создал основы теории паттернов. К сожалению, автору не удалось придать теории законченную форму, и он был вынужден опубликовать изложение результатов своих многолетних исследований только в виде трех томов своих лекций [2]. Выход в свет работы Гренандера привлек внимание специалистов в области распознавания образов, информатики и программирования. Однако со временем, ввиду отсутствия эффективных практических применений, интерес к теории паттернов значительно уменьшился. Известно, что практическое применение математические теории обычно находят не сразу, например, использование теории графов началось более чем через сто лет после решения Эйлером знаменитой задачи о Кенигсбергских мостах. Теория паттернов в этом смысле не является исключением. В то же время, поскольку эта теория обладает большой гибкостью, оригинальностью, глубиной математических и философских идей, она может быть использована в различных областях знаний. Особый интерес представляет ее применение в системах, обладающих памятью. В России был выполнен комплекс фундаментальных и прикладных исследований в области теории паттернов и ее применений, результаты которых позволяют предположить, что теория Гренандера в ближайшем будущем найдет широкое применение в проектировании компьютерных систем и информатике.
Теория паттернов
Слово паттерн означает образец, шаблон, шаблонную модель. В теории Гренандера используются объекты или паттерны четырех уровней. Первый уровень составляют объекты, называемые образующими. Они моделируют относительно простые объекты реального мира, обладающиесвязями, которые могут соединяться со связями других объектов. Из образующих, путем соединения их связей, конструируются регулярные конфигурации, относящиеся к объектам второго уровня. Объектами третьего уровня теории служат изображения, получаемые следующим образом: сходные между собой регулярные конфигурации объединяются в множество, на котором определяются классы эквивалентности. Отношение эквивалентности, определяющее класс эквивалентности на множестве регулярных конфигураций, называется изображением. Четвертый уровень объектов составляют образы. В теории паттернов образом называется множество изображений, инвариантных относительно преобразований подобия. Если на некотором множестве регулярных конфигураций существует только одно изображение, то оно представляет собой единственный образ этого множества. Образующие, регулярные конфигурации, изображения и образы являются соответственно паттернами первого, второго, третьего и четвертого уровней. Формальные методы теории паттернов, применяемые на каждом из четырех уровней, отличаются высокой степенью гибкости и позволяют моделировать связи, соединения и преобразования подобия логических объектов реального мира.
Применение теории паттернов
Ульф Гренандер охарактеризовал свой подход следующим образом: "Любая математическая теория представляет собой набор частных случаев, трактуемых с единых позиций". Теория паттернов остается незавершенной. Существует ряд причин, препятствующих приданию ей законченной формы. Одна из них заключается в отсутствии примеров эффективного практического применения теории Гренандера, обобщение которых привело бы к ее уточнению и дальнейшему развитию. В этой связи теория паттернов была применена в нашей стране при создании инструментальных программных гипертекстовых и гипермедиа-систем. В результате удалось получить весьма интересные решения и макеты программных продуктов, не имеющих пока аналогов на мировом рынке [3,4]. Вместе с тем исследования показали, что паттерновые модели можно с успехом применить к текстовым редакторам, базам данных, издательским и другим системам обработки данных. Теория паттернов была также использована в целях формализованного описания сетевых, иерархических и линейных структур данных [5]. Обычно такие структуры изображают графами. Наглядно представляя структуры систем, графы, тем не менее, мало пригодны для описания связей и соединений объектов. Графы, в отличие от паттерновых моделей, не эффективны, когда нужно описать операции преобразования данных, видимых на экране дисплея или представляемых в памяти компьютера. Теория паттернов позволяет решать подобные задачи, поскольку она обеспечивает описание связей и соединений и имеет в своем арсенале преобразования подобия объектов, обладающих одинаковой структурой, но разным содержанием.
Использование паттерновых моделей в целях проектирования компьютерных систем привело, с одной стороны, к расширению сферы практического применения теории паттернов. С другой стороны, в результате обобщения конкретных примеров паттернового моделирования компьютерных систем, наметились пути уточнения основополагающих принципов теории паттернов и придания ей завершенной формы. Теоретические и прикладные исследования свидетельствуют, что наиболее реальный путь дальнейшего развития теории паттернов заключается в увеличении набора трактуемых с единых математических позиций конкретных примеров ее практического применения. Второе направление совершенствования теории заключается в интеграции теории паттернов с теориями реляционных баз данных и графов в целях создания общей теории шаблонов (паттернов).
Паттерновые и реляционные модели данных
Известно, что реляционные базы данных имеют надежный математический фундамент в виде алгебры отношений и реляционной модели. Иная ситуация сложилась в области сетевых и иерархических баз данных, структуры которых обычно представляют графами. При помощи теории Гренандера удалось построить обобщенную паттерновую модель сетевых, иерархических, линейных и табличных структур данных и показать, что реляционную модель можно получить как частный случай обобщенной паттерновой модели данных.
Паттерны и нейрокомпьютеры
Теорию паттернов целесообразно применить к нейрокомпьютерным моделям. Как показали исследования, нейронную сеть можно представить моделью в виде регулярной конфигурации, составленной из образующих, каждая из которых имеет одну выходную и произвольное число входных связей. Выходная связь образующей моделирует аксон нерона, а ее входные связи - дендриды. Показатели входных и выходных связей образующих имитируют синапсы нейронов. Тот факт, что аксон может иметь множество синапсов, отображается в паттерновой модели копиями выходных связей образующей. Для более углубленного исследования нейронных сетей можно применить рассмотренные Гренандером процессоры образов.
Перспективы
По поводу перспектив дальнейших фундаментальных и прикладных исследований в области теории паттернов можно высказать следующие соображения.
По нашему мнению наиболее важной является проблема уточнения и обобщения теории паттернов. Для ее решения следует расширить область практических применений теории и рассмотреть теорию паттернов совместно с другими родственными теориями. В первую очередь необходимо выявить взаимосвязи теории паттернов с теориями графов и реляционных баз данных.
Другая важная проблема заключается в определении роли и места теории паттернов в информатике.
С практической точки зрения наибольший интерес представляют применения теории паттернов к компьютерным и нейрокомпьютерным системам.
Литература
[1] Меморандум NUCB/ERL v90/28, 9 апреля 1990 года.
[2] Grenander U. Lectures in Pattern Theory, Springer-Verlag, New York Heidelberg Berlin, vol. I (1976) Pattern Synthesis, vol. II (1978) Pattern Analysis, vol. III (1981) Regular Structures. (Русский перевод: Гренандер У. Лекции по теории образов. Перевод с ангийского И. Гуревича под редакцией Ю. Журавлева. - М. Мир, Т. 1. (1979) Синтез образов., Т. 2. (1981) Анализ образов., Т. 3. (1983) Регулярные структуры.).
[3] Шуткин Л.В. Применение теории паттернов к гипермедиа системам // НТИ, Сер.2 - год 1995. - # 7, стр. 19-23.
[4] Шуткин Л.В. Паттерновое моделирование гипертекстов // НТИ, Сер.2 - год 1995, # 9.
[5] Шуткин Л.В. Паттерновая модель данных // НТИ, Сер.2 - год 1995, # 11.
