Об алгебраических и прикладных аспектах задачи поиска информации тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

На правах рукописи

Об алгебраических и прикладных аспектах задачи поиска информации

01.01.06 - математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Екатеринбург-2005

Работа выполнена на кафедре алгебры и дискретной математики Уральского государственного университета им. А. М. Горького

Научный руководитель:

кандидат физико-математических наук, профессор Е. В. Суханов

Официальные оппоненты: доктор физико-математических

наук, профессор А. В. Рожков,

кандидат физико-математических наук, доцент А. С. Лахтин

Ведущая организация:

Московский государственный университет им. М. В. Ломоносова

Защита состоится " 28 " июня 2005 г. в 15 часов на заседании диссертационного совета Д 004.006.03 в Институте математики и механики УрО РАН по адресу: ул. С. Ковалевской 16, 620219, г. Екатеринбург.

С диссертацией можно ознакомиться в библиотеке Института математики и механики УрО РАН.

/ Р

Автореферат разослан " й " _2005 г.

Ученый секретарь /УТУ/ ^

диссертационного совета, у/ъ&с ¿¿/с^ т

доктор физико-математических наук: В. В. Кабане®

2006-У \ 462.0

Общая характеристика работы

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

В общем виде эту задачу можно сформулировать следующим образом. Есть некоторый (обычно конечный) набор данных. Требуется выяснить, присутствует ли в этом наборе информация, удовлетворяющая определенным критериям. И если информация присутствует, извлечь ее в удобном для потребителя виде.

В работе рассматриваются два аспекта этой задачи:

• Исследование свойств символьных последовательностей комбинаторными методами с целью выявления характерных свойств последовательностей. позволяющих упростить задачу поиска В данной работе изучаются свойства так называемых бесповторных символьных последовательностей.

• Описание универсальной модели программы, занимающейся поиском информации в базе данных при помощи языка запросов SQL. Разработка подобных моделей позволяет упростить и стандартизовать процесс создания программ, занимающихся поиском и обработкой информации.

Каждому из названных аспектов общей задачи посвящена отдельная глава данной работы.

В первой главе рассматриваются вопросы, связанные с выявлением комбинаторных и алгебраических свойств бесповторных последовательностей. Данная тематика в настоящее время активно развивается целым рядом исследователей (см., напр., [7, 9]), поскольку имеет очень широкий спектр применения- в биологии для выявления свойств ДНК, в алгебре для построения специального сорта объектов в теории алгебраических систем, в информатике для построения алгоритмов поиска и сжатия информации.

Вторая глава посвящена рассмотрению вопросов, связанных с принципами построения программных систем, ориентированных на поиск и извлечение информации средствами языка запросов SQL. Данная тематика интересна по нескольким причинам: во-первых, подобного сорта разработки позволяют выработать единый подход к созданию эффективного и переносимого программного обеспечения (так называемое шаблонное проектирование, см. напр

подход основан не только на теоретических предпосылках, но и на реальной практической апробации в составе коммерческого программного продукта.

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

Во второй главе диссертации в основу конструируемой модели положен изоморфизм специальным образом построенных алгебраических систем. Для построения и описания модели применяются традиционные средства объектно-ориентированного проектирования. Также используются методы программной генерации кода.

Научная новизна. В диссертации получены следующие новые результаты:

1. Изучено устройство языка Аршона (бесквадратный язык над трехбуквенным алфавитом) как с комбинаторной, так и с алгебраической точек зрения.

2. Получено описание устройства синтаксических конгруэнций класса бесцовторных равномерно рекуррентных бесконечных языков.

3. Выявлены основополагающие требования для построения эффективного переносимого программного кода, предназначенного для поиска и извлечения информации средствами языка SQL

4. Разработаны модель и методология создания класса программ, удовлетворяющих упомянутым в предыдущем пункте требованиям.

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

t irftuju,** t

• ______ . i 4

результаты могут быть использоваться в методологии разработки программных комплексов, а реализации рассматриваемой модели используются в реальных промышленных разработках.

Апробация работы. Результаты работы докладывались на Алгебраической конференции памяти Куроша (Москва, 1998), Международной конференции по теории полугрупп и ее приложениям (С-Петербург. 1999), на XXIX школе-семинаре "Математическое моделирование в проблемах рационального природопользования" (Ростов на Дону, 2001), конференциях Дискретный анализ и исследование операций (Новосибирск, 2002) и Мальцевские чтения (Новосибирск, 2004), а также на семинарах "Дискретная математика" и "Алгебраические системы" Уральского государственного университета и на семинаре "Теория автоматов" Московского государственного университета. Прикладные результаты диссертации были успешно использованы при разработке коммерческого программного продукта IBM QMF for WebSphere.

Публикации. По теме диссертации автором опубликованы работы [10, 11, 12, 13, 14, 15, 16, 17]. Из совместных работ в диссертации используются лишь результаты, принадлежащие автору.

Объем и структура диссертации. Диссертация состоит из введения, двух глав, заключительных замечаний и списка литературы. Используется сквозная нумерация параграфов. Объем диссертации — 78 страниц. Библиография содержит 37 наименований.

Содержание работы

Введение диссертации носит обзорный характер. В нем описываются актуальные вопросы в рассматриваемой предметной области, дается краткий обзор литературы, имеющей непосредственное отношение к рассматриваемой тематике, указывается положение результатов диссертации относительно проводящихся в настоящее время исследований.

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

Пусть £ конечный алфавит. Определим индуктивно систему слов наД определению положим w\ — 1, и пусть w^i получа-

ется из юг по некоторому правилу <р (это правило является параметром

построения), причем w, является префиксом в wt+i, и с ростом г последовательность длин неограниченно возрастает. В так определенной системе слов каждое wL является префиксом wt+k для всех натураль- j

ных г и к. Значит можно говорить о "пределе" данной последовательности слов, т.е. о бесконечной вправо последовательности (гверхслове) ( Wu такой, что множество ее префиксов содержит {«-ч}^. В этом случае будем говорить, что сверхслово Wu порождено правилом <р. Если ip — эндоморфизм то говорят, что Wu порождается итерацией эндоморфизма.

Одним из основных объектов исследования данной работы является язык Аршона, то есть язык всех конечных подслов сверхслова Аршо-на. Сверхслово Аршона строится названным выше способом над трехбуквенным алфавитом, однако порождающее правило не является эндоморфизмом, что усложняет исследование. Точное описание способа построения сверхслова Аршона см. в [1, 2].

Интерес к языку Аршона обусловлен тем, что этот язык изначально обладает рядом характерных свойств (например, бесквадратность). Тем самым изучение данного языка является важным шагом к пониманию устройства класса экстремально бесповторных языков над трехэлементным алфавитом.

Пусть £ и Г — алфавиты. Говорят, что слово v € допускает слово и 6 Г*, если j9(и) ^ v для подходящего гомоморфизма г? : Г* —> £*. В противном случае слово v избегает слово и. Если слово и избегается каждым словом v языка L, то говорят, что язык L избегает и. Язык называется бесповторным, если он избегает слово х" для подходящего п е N.

Понятие избегаемости можно видоизменить следующим образом. Пусть w — слово над Е. Периодом р слова w будем называть всякое натуральное число, для которого w[k) — ui\k + р] для всех к € {1,..., [ш| — р}. Легко понять, что, в частности, длина слова является его периодом. Значит, всякое слово обладает по крайней мере одним периодом. Наименьший период слова w обозначим через per (и;).

Экспонентой слова v (обозн. ехр(г;)) будем называть отношение длины слова v к его наименьшему периоду, т.е. ехр(г>) — jj^y- Наследственную экспоненту слова w (обозн.: Ьехр(ги)) определим так: hexp(iy) = max{exp(t') | v < w}. Понятие наследственной экспоненты \

для языка и сверхслова вводятся аналогично. Например, для языка L определение выглядит так: hexp(L) = sup{hexp(r) | v e L}. У

Будем говорить, что язык допускает экспоненту к, если наследственная экспонента этого языка не меньше к, и избегает экспоненту к в противном случае.

Наследственная экспонента делит множество экспонент на две части: допускаемые и избегаемые. Границу этого разбиения (т.е. наследственную экспоненту) мы будем называть границей избегаемости.

Язык называется факториалъным, если он содержит все подслова любого своего слова Если Ь — это факториальный язык над Е, то множество ¡1 = является идеалом в свободной полугруппе Е+ Этому идеалу соответствует конгруэнция р1, называемая рисовской конгруэнцией полугруппы Е+ по идеалу и определяемая следующим образом: (и, у) е рь тогда и только тогда, когда либо и — V, либо и,у € Синтаксическая конгруэнция <ть языка Ь на Е* определяется следующим образом: (и, у) е сг/, тогда и только тогда, когда для произвольных р, д е Е* слова рид и руд одновременно лежат или не лежат в Ь

Язык Ь называется равномерно рекуррентным, если для произвольного слова V £ Ь существует такое целое число п,;. что V содержится в качестве подслова во всяком слове ги € Ь длины большей п„.

Параграфы 2, 3 и 4 посвящены изучению комбинаторных и алгебраических свойств последовательности и языка Аршона. В результате получены следующие результаты.

1. На пути изучения способа задания языка Аршона итерацией двух эндомоморфизмов выяснилось, что на достаточно длинных словах порождающее правило ведет себя как один обычный эндомомор-физм. Это свойство позволило при изучении языка Аршона применить в немного доработанном виде обычную в этой области индуктивную технику исследования последовательностей, порожденных итерацией эндомоморфизма. Описанию этой техники посвящен параграф 2.

2. Однако полностью перейти к заданию языка Аршона итерацией одного эндомоморфизма невозможно: придуманная техника работы с последовательностью Аршона позволила установить принципиально иным способом ранее известный (см. [б]) результат:

Теорема 1

Последовательность Аршона невозможно породить итерацией одного эндоморфизма.

Доказательству этого факта посвящен параграф 3.

3 Применение разработанной техники позволило установить экстремальную бесповторность языка Аршона. Она непосредственно следует из следующей теоремы.

Теорема 2

Граница избегаемости языка Аршона равна

То есть язык Аршона лежит в классе экстремально бесповторных языков, изучение которого является одной из целей, послужившей основой для проведенных исследований. Доказательству этой теоремы посвящен параграф 4.

4. Также было изучено строение синтаксической конгруэнции языка Аршона. Оказалось, что синтаксическая конгруэнция языка Аршона совпадает с рисовской конгруэнцией свободной полугруппы по дополнению языка Аршона до свободной полугруппы. Однако этот результат, равно как и серия подобных результатов, полученных разными авторами ранее для других бесповторных языков (см.. напр., [4j), является следствием другого, более общего результата, которому посвящен параграф 5 данной работы.

В параграфе 5 устанавливается строение синтаксических конгруэн-ций класса бесконечных бесповторных факториальных равномерно рекуррентных языков. Точная формулировка результата выглядит следующим образом.

Теорема 3

Синтаксическая конгруэнция бесконечного равномерно рекуррентного факториалъного языка ограниченной экспоненты совпадает с рисовской конгруэнцией по дополнению этого языка до свободной полугруппы.

Вторая глава диссертации посвящена изучению подходов к проектированию программных систем, предназначенных для поиска и обработки информации посредством языка запросов SQL. В параграфе 6 дается обзор традиционных проблем, возникающих при разработке кроссплат-форменных программных систем, взаимодействующих с широким спектром систем управления базами данных. На основе анализа этих про-

блем формулируется 4 требования, которым должна удовлетворять подобная кроссплатформенная система, чтобы обеспечить максимальное удобство и гибкость разработки, повышенную эффективность работы и простоту дальнейшего сопровождения программного продукта

Т1. В рамках модели не должно быть привязки к конкретной СУБД. В то же время должна быть возможность гибкой адаптации продукта к любой целевой СУБД, к любому диалекту языка SQL без существенной модификации бизнес-логики продукта.

Т2. Код SQL должен быть отделен от кода на основном языке программирования. В идеале он вообще должен находиться в отдельном наборе файлов (в принципе, файл может быть один).

ТЗ. Организация системы управления SQL-запросами должна быть такова, чтобы обеспечить автоматизированную проверку всех (или почти всех) имеющихся в программе SQL-конструкций на этапе сборки программы.

Т4. Система управления SQL-запросами должна допускать использование специфических средств сервера баз данных для предкомпиляции SQL-конструкций с целью оптимизации выполнения запросов.

Таким образом, постановка задачи выглядит следующим образом: разработать шаблон программной системы (в рамках данной работы этот шаблон называется моделью, поскольку он отражает логическую структуру программной системы без упоминания специфических деталей конкретной реализации), удовлетворяющей выявленным требованиям. Конструктивное построение такой модели и составляет дальнейшее содержимое второй главы.

Сначала в параграфах 8 и 9 вводится понятие пакета запросов. Оказывается, что пакеты запросов можно рассматривать как алгебраические системы определенной сигнатуры. А особый способ построения пакетов позволяет установить изоморфизм получающихся пакетов, которые, в силу определения изоморфизма, оказываются неотличимыми друг от друга с точки зрения операций сигнатуры. Будучи перенесенным на язык программ, этот факт означает, что есть возможность так скомпоновать пакеты запросов, что будет обеспечена возможность гибко подстраиваться под конкретный сервер баз данных. Таким образом,

в основе рассматриваемой модели лежит ачгебраическая конструкция, вокруг которой затем и происходит все построение.

Для хранения пакетов запросов с учетом построенной алгебраической конструкции предлагается структура данных (менеджер запросов), позволяющая эффективно оперировать пакетами. Тем самым удовлетворяется требование Т1.

Затем в параграфе 10 демонстрируется, как организовать наполнение структуры данных для хранения пакетов собственно информацией о запросах, составляющих пакеты. Оказывается, что удобно выделить исходные тексты запросов в отдельный файл специальной структуры, а наполнение хранилища запросов производить при помощи специальной программы-конвертера (данный прием построения программ при помощи других программ представляет самостоятельный интерес). Тем самым удовлетворяется требование Т2. Также становится ясно, что и требование ТЗ оказывается выполненным, поскольку хранилище располагает достаточной информацией для автоматизированного тестирования.

Таким образом оказываются удовлетворенными все требования к модели, кроме требования Т4. Однако это требование по своей природе носит прикладной характер, поэтому для его выполнения требуется привлекать уже существующие прикладные разработки, как, например, технологию SQLj (см. [5. 8]).

Обсуждению всех аспектов модели, связанных с технологией SQLj посвящены параграфы И и 12 Там дается обзор технологии SQLj, ее достоинств и недостатков. Указываются способы устранения недостатков и показывается, каким образом данная технология может быть включена в состав рассматриваемой модели с целью удовлетворения требования Т4.

В результате получается достаточно удобная и гибкая, и в то же время очень емкая, конструктивно и концептуально простая, модель. Даже упрощенная ее реализация в рамках коммерческого продукта QMF for WebSphere наглядно продемонстрировала названные качества.

Построение модели разбито на логические части, каждая из которых содержит краткое описание корректности соответствующей части модели. Утверждения о корректности оформлены в виде теорем (теоремы 4-6), что дополнительно подчеркивает логическую структуру модели

Наконец, в заключительных замечаниях приводятся возможные направления дальнейшего продолжения исследований в рассматриваемой

предметной области. Предлагаются постановки ряда задач, представляющих, с точки зрения автора, реальный теоретический и практический интерес.

Список литературы

(1] Адян С.И. Проблема Бернсайда и тождества в группах. М., Наука, 1985

}2] Аршон С.Е., Доказательство существования п-значных бесконечных асимметричных последовательностей. // Мат. сб., 1937, т.2 (44), № 4, 769-779.

[3] Гамма Э., Хелм Р., Джонсон Р., Влиссидес Дж. Приемы объектно-ориентированного проектирования. Паттерны проектирования, изд. Питер, 2001.

[4] Суханов Е.В., Шур A.M. Об одном классе формальных языков // Алгебра и Логика, 1998, т.37, №4, 478-492

[5] ANSI ХЗ. 135.10:1998 Information systems — Database language — Part 10: Object Language Binding (SQL/OLB) // American National Standard Institute, New York City, 1998

[6] Dejean F. Sur un théorème de Thue // J. Combinatorial Theory (A), 1972, Vol. 13, 90-99

[7] Lothair M. Algebraic Combinatorics on Words. Encyclopedia of Mathematics and its Applications, Canibridge University Press, 2002.

[8] Melton J., Eisenberg A. Understanding SQL and Java Together: A Guide to SQL J, JDBC, and Related Technologies // Morgan Kaufmann, 2000

|9] Rozenberg G., Salomaa A. Handbook of Formal Languages, in 3 Vols, Springer, 1997.

Работы автора по теме диссертации:

[10] Клепинин А.В. Об алгебраических свойствах языка Аршона // Областной конкурс студенческих научных работ. Тезисы работ. Екатеринбург, 1997, 19-20

И

[11] Клеиинин A.B. О синтаксических конгруэнциях бесповторных языков над конечными алфавитами // Российская конференция Дискретный анализ и исследование операций, материалы конференции, Новосибирск, 2002, стр.129

[12] Клеиинин A.B. Изоморфизмы и кроссплатформенные приложения // Международная конференция Мальцевские чтения, материалы конференции, Новосибирск, 2004,

http://www.math.nsc.ru/conference/malmeet/04/Klepinm.pdf

[13] Клепинин A.B. Об универсальной модели организации доступа к базам данных // Урал. ун-т. Екатеринбург, 2005, деп. в ВИНИТИ 13.04.2005 М98-В2005

[14] Клепинин A.B. Применение SQLj для реализации объектного доступа к данным II Урал. ун-т. Екатеринбург, 2005, деп. в ВИНИТИ 13.04.2005 №497-В2005

[15] Бакиров М.Ф., Зыков E.JL, Клепинин A.B., Красноперов В.Г., Под-дубный В.А., Хмелева Т.Ю., Чечулин A.B. Клиент-серверная корпоративная информационная система управления данными об отходах на региональном уровне // XXIX школа-семинар "Математическое моделирование в проблемах рационального природопользования", тезисы докладов. Ростов-на-Дону, Издательство СКНЦ ВШ, 2001, 42-43

[16] Бакиров М.Ф., Клепинин A.B., Суханов Е.В. О комбинаторно-алгебраических свойствах бесповторных последовательностей // Kurosh Algebraic Conference '98 Abstracts of Talks, Moscow, 1998,139 140

[17] Klepinin A.V., Sukhanov E.V. On combinatorial properties of the Arshon sequence 11 Discrete Applied Mathematics 114 (2001) 155-169

Отпечатано в типографии ООО «Издательство УМЦ УПИ» 620002, г. Екатеринбург, ул. Мира, 17, С-134. Заказ Тираж -/СО экз.

Тираж J&Q экз.

Р Введение

Содержание первой главы.

Содержание второй главы.

Глава I. О комбинаторных свойствах бесповторных формальных языков

§1 Основные определения.

§2 Последовательность Аршона и ее структурные свойства

§3 Последовательность Аршона и порождение эндоморфизмом

§4 Экспонента избегаемости языка Аршона.

§5 Синтаксические конгруэнции бесповторных языков.

Глава II. Об интеграции языка SQL с языками разработки кроссплатформенных систем

§6 Обозначения и основные определения.

§7 Примеры типичного использования SQL и область применимости модели.

§8 SQL запросы и их абстрактное представление.

§9 Пакеты запросов и их изоморфизм. ф

§10 Менеджер запросов и наполнение пакетов.

§11 Технология SQLj.

§12 Интеграция с SQLj.

Заключительные замечания

В данной работе рассматриваются вопросы, связанные с задачей поиска и обработки информации.

В общем виде эту задачу можно сформулировать следующим образом. Есть некоторый (обычно конечный) набор данных. Требуется выяснить, присутствует ли в этом наборе информация, удовлетворяющая определенным критериям. И если информация присутствует, извлечь ее в удобном для потребителя виде. Легко понять, что в абстрактном алгоритмическом смысле проблемы как таковой нет, поскольку определить за конечное время наличие некоторого объекта в конечном множестве безусловно можно. Но сложность в том, что нужно уметь решать задачу поиска и извлечения информации быстро, чтобы обеспечить адекватное для человека время реакции поисковой системы на введенный запрос.

Какими же способами можно решать эту задачу? По всей видимости, можно выделить два пути.

1. Можно пытаться оптимизировать сам алгоритм поиска, когда за счет грамотного выбора структур данных, за счет использования параллелизма вычислительных систем уменьшается временная сложность алгоритма.

К этому направлению можно отнести, например, хорошо известные автоматные алгоритмы поиска слов в тексте. Эти алгоритмы настолько важны, что фактически выделяются в отдельную область исследования. Так, алгоритмам сортировки и поиска посвящен отдельный том классического трехтомника Дональда Кнута "Искусство программирования" (см. [22]). В более современном учебнике по компьютерной математике "Алгоритмы: построение и анализ" (см. [23]) алгоритмы сортировки и поиска также составляют значительную часть материала.

Но построение эффективных алгоритмов невозможно без исследований на втором пути.

2. Можно пытаться анализировать критерии поиска и свойства множества объектов, в котором поиск производится. И на основании этого анализа из известных теоретических результатов сделать вывод о наличии или отсутствии искомого объекта, сделать вывод о том, как провести поиск более эффективно.

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

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

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

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

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

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

Содержание первой главы

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

1. Фрагменты ДНК (цепочки генов) образуют формальный язык, исследования которого чрезвычайно важны для понимания механизмов хранения генетической информации.

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

3. Ход любой игры, допускающей лишь конечное множество игровых состояний, может быть представлен в виде слова. Тогда все возможные игровые стратегии, таким способом представленные в виде слов, образуют язык, знание свойств которого позволяет находить выигрышные стратегии, выявлять те или иные свойства игры.

4. Языки, обладающие специальными свойствами (коды) используются для того, чтобы уменьшить вероятность искажения важной информации.

Этот список важных примеров можно продолжать. Так что не удивительно, что исследование формальных языков, и бесповторных в частности, имеет уже почти вековую историю. Нас будет интересовать класс бесповторных языков (в них слова не могут в определенном смысле повторяться слишком часто, точное определение понятия бесповторности будет дано в §1) и свойства, присущие языкам этого класса.

Первой работой, в которой было явно сформулировано понятие бесповторности, и были найдены примеры бесповторных последовательностей, по всей видимости, следует считать ставшую классической работу норвежского математика А.Туэ ([17], см. также [27]). В этой работе были поставлены следующие вопросы.

1. Можно ли над алфавитом из двух букв построить бесконечную последовательность символов, не содержащую подслов вида г;3? Здесь запись хп обозначает п раз подряд записанное слово х. Точное определение будет дано в §1.

2. Можно ли над алфавитом из трех букв построить бесконечную последовательность символов, не содержащую подслов вида V2?

Может показаться, что ответ на второй вопрос должен быть отрицательным: три буквы — это мало, а требование отсутствия повторов выглядит достаточно сильным. Тем удивительнее факт, что на самом деле на оба вопроса ответ положительный и конструктивный: Туэ построил примеры таких последовательностей.

Еще более удивительным является тот факт, что придуманная Туэ последовательность, дающая положительный ответ на первый вопрос, позже неоднократно переоткрывалась другими авторами. Так, в частности, Морс и Хед-лунд в своей работе [9] независимо от Туэ поставили подобные вопросы и в качестве ответа придумали ту же самую последовательность. Также у этой последовательности, ныне известной как последовательность Туэ-Морса, были обнаружены важные комбинаторные и алгебраические свойства, наличие которых послужило отправной точкой для многих исследований в данной области.

Туэ интересовался существованием бесповторных последовательностей над алфавитами малой мощности. Бесповторность он формулировал как отсутствие подслов вида хп (п € М). Позже стало ясно, что это факт можно выразить в терминах более общего понятия избегаемости (точное определение см. в §1): в слове ги отсутствуют подслова вида Vй тогда и только тогда, когда ги избегает ьп. Следовательно, можно обобщить проблему Туэ так: существует ли бесконечная последовательность символов, избегающая данное слово? И если существует, то какова минимальная мощность алфавита, над которым такое слово можно построить?

Исследования в этом направлении привели к результату, известному как теорема ВЕМч^ (см. [6, 21]). Оказалось, что не для всякого слова можно построить избегающую его последовательность. А теорема ВЕМ+2 объединила несколько критериев существования такой избегающей последовательности. Переработанное и сведенное воедино доказательство этого важного результата можно найти в [13].

Таким образом, ответ на проблему Туэ в случае классического определения избегаемости дан. Однако понятие избегаемости можно еще расширить, определив дробные степени слов. Тогда проблема Туэ переформулируется так: можно ли построить бесконечную последовательность, не содержащую подслов вида где д € <ф? Если можно, то какова минимальная мощность алфавита, над которым это возможно? Каково минимальное <7, для которого над алфавитом заданной мощности это возможно?

Для бинарных алфавитов ответ на последний вопрос дает все та же последовательность Туэ-Морса: она содержит слова вида х2, но не содержит подслов вида ха для любого рационального а > 2 (см. [29, 14]). Легко понять, что в случае бинарного алфавита улучшить результат нельзя: над бинарным алфавитом невозможно построить бесконечную последовательность, не содержащую слов вида х2.

В случае алфавитов мощности 3 и выше ситуация усложняется: лишь в 1972 году Ф.Дежан удалось найти минимальное q для алфавита мощности 3 и высказать гипотезу о том, чему равно минимальное q для алфавитов большей мощности (см. [7], также см. [24]). Позже в [11] гипотеза Дежан была доказана для алфавита мощности 4, а затем в [10] гипотеза была доказана для алфавитов, мощность которых лежит в диапазоне от 5 до 11.

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

Оказалось (см. [29, 14]), что последовательность Туэ-Морса фактически исчерпывает все экстремальные языки над бинарным алфавитом в том смысле, что любое экстремальное бинарное слово на 70% состоит из поде лова последовательности Туэ-Морса. То есть получается достаточно простое описание класса всех экстремальных языков над бинарным алфавитом. И вполне естественной выглядит попытка рассмотреть класс экстремальных языков над трехэлементным алфавитом, изучить его конкретных представителей, выявить общие свойства и, быть может, даже перенести в каком-то виде вышеназванный результат об устройстве класса бинарных экстремальных языков на случай трехэлементного алфавита. Собственно, эти идеи и явились отправной точкой для исследования, результаты которого изложены в первой главе.

Основным объектом исследования стал язык Аршона, который строится из бесконечной символьной последовательности Аршона путем перечисления всех имеющихся в ней конечных подслов (в дальнейшем будут упоминаться еще несколько языков, построенных по соответствующим бесконечным последовательностям подобным образом). Отметим, что с точки зрения экстремальности бесконечная последовательность и язык всех ее подслов эквивалентны, поэтому мы не будем специально различать эти объекты, когда речь будет идти лишь об экстремальности.

Еще из работы Туэ было известно, что над трехэлементным алфавитом существуют бесконечные бесквадратные языки. Следовательно, представителей класса экстремальных языков следует искать именно среди бесквадратных языков. И два таких языка уже появлялись в исследованиях. Речь идет о языке Дежан (он заведомо лежит в классе экстремальных, поскольку порождающая его символьная последовательность специально строилась так, чтобы оказаться экстремальной) и о языке Аршона (последовательность изначально конструировалась как просто бесквадратная (см. [19]), позже она использовалась в качестве важного вспомогательного элемента в решении групповой проблемы Бернсайда [18]). Отметим, что язык, получающийся из ранее упоминавшейся бесквадратной последовательности Туэ, экстремальным не является. Поэтому для данного исследования он особого интереса не представляет.

Первое, что следовало сделать, — разобраться со свойствами языка Аршона. А именно, хотелось получить ответы на следующие вопросы.

1. Язык Аршона задается итерацией двух эндомоморфизмов свободной полугруппы. Как работать с таким объектом? Можно ли каким-то образом от итерации двух эндомоморфизмов перейти к достаточно хорошо изученной итерации одного эндомоморфизма?

2. Язык Аршона бесквадратен. Этот факт говорит о почти экстремальной бесповторности языка. А чему равно точное значение границы избегаемое™ языка Аршона? Является ли он на самом деле экстремально бесповторным?

3. Насколько похож язык Аршона на другие экстремально бесповторные языки с точки зрения устройства синтаксической конгруэнции языка? Как устроена синтаксическая конгруэнция языка Аршона?

Проведенное исследование дает ответы на все поставленные вопросы. Вот какими оказались результаты.

1. На пути изучения способа задания языка Аршона итерацией двух эндомоморфизмов выяснилось, что на достаточно длинных словах итерация двух порождающих эндомоморфизмов ведет себя как один обычный эндомоморфизм. Это свойство позволило при изучении языка Ар шона применить в немного доработанном виде обычную в этой области индуктивную технику исследования последовательностей, порожденных итерацией эндомоморфизма. Описанию этой техники посвящен §2.

2. Однако полностью перейти к заданию языка Аршона итерацией одного эндомоморфизма невозможно: придуманная техника работы с последовательностью Аршона позволила установить принципиально иным способом ранее известный (см. [7]) результат:

Теорема 1

Последовательность Аршона невозможно породить итерацией одного эндоморфизма.

Доказательству этого факта посвящен §3.

3. Применение разработанной техники позволило установить экстремальность языка Аршона. Она непосредственно следует из следующей теоремы:

Теорема 2

Граница избегаемости языка Аршона равна

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

Доказательству теоремы 2 посвящен §4.

4. Также было изучено строение синтаксической конгруэнции языка Аршона (точное определение см. в §1). Оказалось, что синтаксическая конгруэнция языка Аршона совпадает с рисовской конгруэнцией свободной полугруппы по дополнению к языку Аршона.

Заметим, что данный результат, полученный в совместной работе [37], прекрасно вписался в систему подобных результатов: этим же свойством обладает двухбуквенный язык Туэ-Морса (см. [28]); легко доказывается что язык Дежан им также обладает.

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

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

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

Как известно, теорема Клини отвечает на подобный вопрос: она утверждает, что классы регулярных и представимых языков совпадают (см. [27, Глава 2]). Но теорему Клини можно переформулировать и на языке полугрупп: язык является регулярным (и, соответственно, представимым) тогда и только тогда, когда его синтаксический моноид конечен (см. [24, Глава 6]). Более того, синтаксический моноид фактически определяет автомат, распознающий язык. Поэтому устройство синтаксического моноида непосредственно связано со сложностью и эффективностью распознающего алгоритма.

Во-вторых, Эйленберг (см., например, [12]) установил, что между многообразиями конечных полугрупп и специальными классами языков (их называют многообразиями языков) существует взаимно-однозначное соответствие. И в основе этого соответствия лежит сопоставление языку его синтаксической полугруппы.

Соответствие Эйленберга позволяет решать задачу классификации языков, группировать в один класс языки со схожими свойствами синтаксических полугрупп. Или наоборот выяснять, как конкретное свойство полугруппы влияет на свойства языка, для которого эта полугруппа является синтаксической.

Обычно результаты в этой области получаются именно так: от полугрупп к языкам. В качестве наиболее яркого примера можно привести теорему Шютценберже (см., например, [12]), которая утверждает, что многообразие апериодических (комбинаторных) конечных моноидов соответствует многообразию звездно-свободных языков. Фактически с этого результата и начались исследования многообразий языков.

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

В процессе изучения различных бесповторных языков (в частности, Туэ-Морса, Дежан, Аршона) была отмечена закономерность: у всех названных языков синтаксическая конгруэнция совпадает с рисовской конгруэнцией по дополнению к языку. И это совпадение оказалось не случайным: было обнаружено достаточное условие для такого совпадения конгруэнций.

Язык L называется равномерно рекуррентным, если для произвольного слова v б L существует такое целое число nv, что v содержится в качестве подслова во всяком слове w € L длины большей nv. Язык L называется языком ограниченной экспоненты, если существует такое целое число к, что никакое слово из L не содержит подслов вида хк. Язык называется фактори-алъным, если вместе с каждым своим словом он содержит все подслова этого слова (иными словами, язык является факториальным, если он замкнут относительно взятия подслов).

Теорема 3

Синтаксическая конгруэнция бесконечного равномерно рекуррентного фак-ториалъного языка ограниченной экспоненты совпадает с рисовской конгруэнцией по дополнению этого языка до свободной полугруппы.

Эта теорема охватывает достаточно широкий класс языков. Достаточно сказать, например, что под условие теоремы попадают все языки ограниченной экспоненты, порожденные DOL-системами (про DOL-системы см., например, [27]).

Содержание второй главы

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

Особенно ярко этот недостаток существующих технологий проявился в процессе создания программного продукта QMF for WebSphere (подробную информацию о продукте см., например, в [4, 5]), в коллектив разработчиков которого входит автор данной работы.

Одна из основных задач, которая ставилась при разработке QMF for WebSphere, состояла в обеспечении работоспособности программы на всем спектре систем управления базами данных IBM DB2: от систем, работающих на персональных компьютерах, до систем, предназначенных для использования на крупных предприятиях. Также требовалось обеспечить поддержку СУБД других производителей (Oracle, в частности). Поэтому особенно важным оказалось придумать такую модель взаимодействия с СУБД, чтобы использование широкого набора целевых СУБД в программном продукте было максимально простым.

В процессе осмысления задачи, на основе имеющегося большого опыта разработки программ, взаимодействующих с СУБД, автору данного текста удалось выявить некоторые общие закономерности, которые позволили построить необходимую модель и обеспечить реализацию требующейся функциональности в рамках программного продукта. Однако сфера применимости созданной модели не ограничивается отдельно взятым программным продуктом: исходная задача допускает естественное обобщение (точная постановка будет дана ниже), а модель, являющаяся решением этой обобщенной задачи, позволяет не только существенно упростить процесс адаптации продукта под различные СУБД, но и ощутимо снизить сложность процессов разработки, отладки и поддержки программы. В таком обобщенном виде модель оказывается достаточно универсальной для использования в самых разнообразных ситуациях, в широком спектре разрабатываемых программных систем.

Описанию решения этой обобщенной задачи и посвящена данная глава.

Отметим, что в процессе исследования задачи, в процессе поиска решений для реализации QMF for WebSphere было разработано несколько технологических и технических решений, представляющих самостоятельный интерес. В частности был разработан уровень абстракции баз данных (database abstraction layer), подсистема управления запросами, технология интеграции с SQLj API, технологии оптимизации операций с серверами баз данных. Все эти решения сейчас являются неотъемлемой частью продукта.

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

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

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

часть модели.

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

Как уже упоминалось выше, в настоящее время достаточно большое количество программных комплексов пользуются сервисами СУБД. Причина ясна: очень удобно иметь единый, в какой-то мере стандартный и универсальный способ описания и решения типичных задач управления данными. Так, практически всегда требуется сначала каким-то способом определить структуры для хранения данных, затем описать правила согласованности, целостности данных, затем, собственно, описать операции по извлечению данных, по их изменению. Неудивительно, что язык SEQUEL (Structured English Query Language), разработанный в 1974 году в исследовательских лабораториях корпорации IBM для решения подобных задач управления данными, оказался положительно воспринят разработчиками программного обеспечения и был взят за основу при подготовке спецификации стандартного языка запросов.

В результате была выделена та общая сущность, которая объединяла все имевшиеся на тот момент реализации систем управления базами данных (каждый разработчик СУБД предлагал свои уникальные возможности в рамках своей СУБД), и в 1986 году ANSI опубликовал первую спефика-цию языка запросов, ныне широко известного как SQL (Structured Query Language). В свою очередь разработчики СУБД постарались обеспечить максимальную совместимость своих систем с этим ставшим стандартным языком. Позже язык SQL несколько раз расширялся, чтобы учесть новые требования, новые возможности применения СУБД, новые технологии. Но по сей день в любой задаче, связанной с хранением и обработкой данных, в той или иной степени используется SQL.

Таким образом, на сегодняшний день SQL является стандартным языком взаимодействия с СУБД. Он поддерживается всеми современными СУБД. Все современные средства разработки программ предлагают доступ к API, позволяющему использовать SQL для доступа к данным. Создается впечатление, что использование SQL в чистом виде решает все задачи, возникающие при создании программных систем. Однако на самом деле это не так. Все хорошо, когда речь идет о разработке небольших программ. Как только же речь заходит о реализации крупной программной системы, использующей СУБД, о тесной интеграции языка SQL и основного языка разработки программного продукта, неминуемо проявляются следующие неприятные для разработчика моменты, которые невозможно обойти в рамках обычных классических методов использования SQL в программах.

1. Разные СУБД используют разные диалекты SQL. То есть в СУБД реализуется основная часть спецификации SQL, а затем добавляется расширение языка, специфичное для конкретного сервера баз данных. В результате разработчик вынужден выбирать: либо сохранить независимость программы от СУБД, оставаясь в рамках стандартной части SQL (при этом в жертву приносятся быстродействие программы и возможность использования специфики сервера, часто выигрышной для пользователя), либо использовать максимум возможностей конкретного сервера (при этом неминуемо теряются переносимость кода и независимость от СУБД).

2. Язык SQL является инородным по отношению к основному языку программирования, на котором ведется разработка системы. С одной стороны это хорошо: для понимания конструкций SQL не требуется знать язык, на котором написана сама программа. Но с другой стороны из этой инородности SQL следуют два неприятных факта. a) В процессе трансляции программы невозможно проверить корректность (синтаксическую и логическую) конструкций SQL. Следовательно, усложняется отладка кода: требуется обеспечить во время тестирования выполнение всех веток программного кода, на которых происходит запуск SQL-конструкций. Причем такой подход позволяет установить лишь синтаксическую корректность используемых конструкций SQL. Если же SQL-запросы содержат параметры, отладка становится еще сложнее. b) Конструкции SQL оказываются разбросанными по коду программы. Следовательно, усложняется сопровождение программы, поскольку любое изменение в используемой структуре таблиц СУБД неминуемо влечет тщательный анализ всего программного кода с целью выявления SQL-конструкций, подлежащих исправлению.

3. Во многих случаях SQL-конструкции являются постоянными в том смысле, что SQL-запрос в процессе использования программы не меняется, а меняются лишь отдельные параметры запроса. Было бы крайне заманчиво в такой ситуации заранее подготовить, "откомпилировать" SQL-конструкции в некий полуфабрикат, который потом сэкономит время на запуске запроса (в момент запуска не придется выполнять синтаксический анализ запроса, не потребуется готовить план выполнения SQL-конструкции). Стандартные API взаимодействия с СУБД (ODBC, JDBC) не предоставляют таких возможностей. Точнее, подобные возможности есть, но они носят локальный характер: можно не выполнять повторную трансляцию запроса, когда он выполняется, скажем, несколько раз в цикле; но при повторных запусках программы все равно требуется заново транслировать каждый запрос SQL.

Еще раз подчеркнем, что на вышеназванные проблемные места можно : обращать внимания при разработке небольшой программы, использующей одну конкретную СУБД. В этом случае они не очень существенны. Но в случае большого проекта их влияние нельзя недооценивать. Так, автору требовалось обеспечить работоспособность продукта в кроссплатформенной среде (точное определение см. в §6) на всей линейке серверов IBM DB2, на базах Informix, Red Brick, Oracle, на других СУБД, на платформах от персональных компьютеров до промышленных мэйнфреймов. Легко понять, что в подобных условиях крайне важно обеспечить максимальную гибкость в привязке к базе данных, как можно сильнее упростить процессы разработки, отладки и сопровождения продукта. В результате вполне естественной выглядит следующая задача: разработать единый подход к решению проблем интеграции разных языков и построить модель системы управления SQL-запросами, устраняющую вышеназванные недостатки. Сформулируем требования, которым должна удовлетворять искомая модель.

Т1. В рамках модели не должно быть привязки к конкретной СУБД. В то же время должна быть возможность гибкой адаптации продукта к любой целевой СУБД, к любому диалекту языка SQL без существенной модификации бизнес-логики продукта.

Т2. Код SQL должен быть отделен от кода на основном языке программирования. В идеале он вообще должен находиться в отдельном наборе файлов (в принципе, файл может быть один).

ТЗ. Организация системы управления SQL-запросами должна быть такова, чтобы обеспечить автоматизированную проверку всех (или почти всех) имеющихся в программе SQL-конструкций на этапе сборки программы.

Т4. Система управления SQL-запросами должна допускать использование специфических средств сервера баз данных для предкомпиляции SQL-конструкций с целью оптимизации выполнения запросов.

В построении такой модели и состоит суть данной работы. Отметим, что apriori совсем не ясно, существует ли нужная модель.

Удивительным, на наш взгляд, является тот факт, что выполнить все названные требования оказалось вполне возможно. Причем реализация возникающей в результате модели действительно дает весьма ощутимый выигрыш в процессе разработки и дальнейшего сопровождения программного комплекса. Опыт использования отдельных элементов модели в продукте QMF for WebSphere наглядно это продемонстрировал.

Сразу же отметим, что в рамках данного текста в качестве целевого языка программирования используются язык Java и связанная с этим языком терминология. Но это ни в коей мере не означает, что модель может быть реализована только на Java. С минимальной адаптацией она реализуется на произвольном объектно-ориентированном языке программирования.

Процесс построения модели будет состоять из нескольких шагов.

Сначала (§8) будет введено понятие пакета запросов. Окажется, что для пакетов запросов можно естественным образом построить изоморфизм. И наличие этого изоморфизма позволит так скомпоновать пакеты запросов, что будет обеспечена возможность гибко подстраиваться под конкретный сервер баз данных. Для хранения пакетов запросов будет предложена структура данных (менеджер запросов), позволяющая эффективно оперировать пакетами. Тем самым будет удовлетворено требование Т1.

Затем (§10) будет показано, как организовать наполнение структуры данных для хранения пакетов собственно информацией о запросах, составляющих пакеты. Окажется, что удобно выделить исходные тексты запросов в отдельный файл специальной структуры, а наполнение хранилища запросов производить при помощи специальной программы-конвертера. Тем самым будет удовлетворено требование Т2. Также станет ясно, что и требование ТЗ оказывается удовлетворенным, поскольку хранилище будет располагать достаточной информацией для автоматизированного тестирования.

На этот момент окажутся удовлетворенными все требования к модели, кроме требования Т4. Поэтому останется рассмотреть технологию SQLj и способ ее использования для удовлетворения требования Т4.

Сначала будет рассмотрен SQLj API. Это стандартный программный интерфейс, предложенный ведущими производителями СУБД для интеграции SQL-конструкций в язык программирования Java. Отметим, что упоминание языка Java не уменьшает общности, поскольку аналоги SQLj API есть и для других языков програмирования. Функциональность, предоставляемая такими API практически не различается. Окажется, что простое применение SQLj позволяет выполнить требование Т4 и частично требования Т2 и ТЗ. Но требование Т1 при этом гарантированно не выполняется.

Тем не менее, в рамках рассматриваемой модели вполне можно воспользоваться технологией SQLj. За счет этого можно получить доступ к крайне полезным возможностям, предоставляемым SQLj API, в рамках нашей модели. В частности, использование SQLj API позволяет выполнить требование Т4, которое невозможно удовлетворить другими способами.

Обсуждению всех аспектов модели, связанных с технологией SQLj посвящены §11 и §12.

В результате получается достаточно удобная и гибкая, и в то же время очень емкая, конструктивно и концептуально простая, модель. Даже упрощенная ее реализация в рамках коммерческого продукта QMF for WebSphere наглядно продемонстрировала названные качества.

Для удобства читателя каждый существенный фрагмент модели содержит краткое описание корректности конструкции. Утверждения о корректности оформлены в виде теорем, что дополнительно подчеркивает логическую структуру модели.

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

• Объектная структура ядра модели. Она является скелетом для построения остального кода. Именно удачность выбранной структуры позволяет удовлетворить все поставленные требования, позволяет гибко адаптировать систему к различным СУБД.

• Нетривиальный подход к применению технологии статического SQL (SQLj). Он позволяет использовать преимущества конкретных серверов в сфере оптимизации запросов. Отметим, что в рамках разработки QMF for WebSphere это вторая попытка получить интеграцию с SQLj. Первая оказалась неудачной, поскольку не удалось найти такого способа использования SQLj, который бы гарантировал работоспособность технологии на всех используемых СУБД. А в рамках описываемой модели такой способ был найден.

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

Как будет описано в §10, суть приема состоит в том, что фактически на базе основного языка программирования строится модуль, способный выполнять определенные наборы операций, специфика которых описывается на собственном специальном языке. То есть фактически возникает еще более высокоуровневый язык описания логики системы (в случае рассматриваемой модели в качестве языка более высокого уровня выступает текстовый формат представления пакетов и составляющих их запросов). Использование же более высокоуровневых языков повышает скорость разработки, этот факт общеизвестен.

Важность такой технологии "многоуровневого" программирования состоит в том, что часто она может быть использована для очень гибкой параметризации кода, для отделения описания бизнес-логики от реализации ее отдельных элементов. Эти преимущества технологии "многоуровневого" программирования были успешно использованы автором ранее при разработке клиент-серверной корпоративной информационной системы для Министерства охраны окружающей среды (см. [35]), где на специальном языке описывалось поведение большого количества функционально сложных диалогов просмотра/редактирования данных и нетривиальная логика их взаимодействия с СУБД, в которой данные размещались.

Таковы результаты, изложенные в этой работе. Они докладывались на Алгебраической конференции памяти Куроша (Москва, 1998), Международной конференции по теории полугрупп и ее приложениям (С-Петербург, 1999),| на XXIX школе-семинаре "Математическое моделирование в проблемах рационального природопользования" (Ростов на Дону, 2001), конференциях Дискретный анализ и исследование операций (Новосибирск, 2002) и Маль-цевские чтения (Новосибирск, 2004), а также на семинарах "Дискретная математика" и "Алгебраические системы" Уральского государственного университета и на семинаре "Теория автоматов" Московского государственного университета. Прикладные результаты были успешно использованы при разработке коммерческого программного продукта IBM QMF for WebSphere.

Основные результаты опубликованы в [30, 31, 32, 33, 34, 35, 36, 37]. Из совместных работ в данном тексте используются лишь результаты, принадлежащие автору.

Работа выполнена под руководством профессора Евгения Витальевича Суханова, которому автор глубоко признателен за постоянное внимание и всестороннюю поддержку.

1. ANS1.ХЗ.135.10:1998 Information systems — Database language — Part 10: Object Language Binding (SQL/OLB) // American National Standard Institute, New York City, 1998

2. ANSI NCITS 311.1:1999 SQLJ Parti: SQL Routines Using the Java™ Programming Language // American National Standard Institute, New York City, 1999

3. ANSI NCITS 331.2:2000 SQLJ Part2: SQL Types Using the Java™ Programming Language // American National Standard Institute, New York City, 2000

4. Getting Started with DB2 QMF for Windows and DB2 QMF for WebSphere // IBM, 2004,ftp: / / ftp.software.ibm.com/software/data/qmf/pdfs/scl87449.pdf

5. QMF for WebSphere 8.1 // информация о продукте, Rocket Software, 2004, http://www.rocketsoftware.com/qmf/websphere/default, asp

6. Bean D.R., Ehrenfeucht A., McNulty G.F. Avoidable patterns in strings of symbols U Pacific J. Math., 1979. Vol. 85. No. 2, 261-294.

7. Dejean F. Sur un théorème de Thue // J. Combinatorial Theory (A), 1972, Vol. 13, 90-99

8. Melton J., Eisenberg A. Understanding SQL and Java Together: A Guide to SQLJ, JDBC, and Related Technologies // Morgan Kaufmann, 2000

9. Morse M., Hedlund G. Unending chess, symbolic dynamics, and a problem in semigroups, j/ Duke Math J., 1944, Vol. 11, 1-7.

10. Ollagnier J.M. Proof od Dejean's conjecture for alphabets with 5,6,7,8„9,10 and 11 letters j j Theoretical Computer Science, 1992, Vol. 95, 187-205

11. Pansiot J.J. A propos d'une conjecture de F.Dejean sur les répétitions dans le mots // Discrete Appl. Math., 1984, Vol. 7, 297-311

12. Pin J.E. Varieties of Formal Languages // North Oxford, London et Plenum, New-York, 1986

13. Sapir M., Combinatorics on words with applications. // Institute Blaise Pascal, Rapports LITP, 1995, Vol. 32.

14. Shur A.M. Overlap-free words and Thue-Morse sequences // Int. J. of Alg. and Сотр., 1996, 53(2), 212-219.

15. Sanyal S., Martineau D., Gashyna K., Kyprianou M. DB2 Universal Database v7.1 // Prentice Hall PTR, Upper Saddle River, New Jersey 07458, 2001

16. Адян С.И. Проблема Бернсайда и тождества в группах. М., Наука, 1985

17. Аршон С.Е., Доказательство существования п-значных бесконечных асимметричных последовательностей. // Мат. сб., 1937, т.2 (44), № 4, 769-779.

18. Грофф Д., Вайнберг П. SQL: полное руководство. Пер. с англ., К., Издательская группа BHV, 1999

19. Зимин А.И. Блокирующие множества термов // Мат. сб., 1982, т. 119. № 3, 363-375.

20. Кнут Д. Искусство программирования. 3-е изд., М., Издательский дом "Вильяме", 2000

21. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М., МЦНМО, 2001

22. Лаллеман Ж. Полугруппы и комбинаторные приложения. М., Мир, 1985

23. Ларман К. Применение UML и шаблонов проектирования. Пер. с англ., М., Издательский дом "Вильяме", 2002

24. Морган М. Java™ 2 Руководство разработчика. Пер. с англ., М., Издательский дом "Вильяме", 2000

25. Саломаа А. Жемчужины теории формальных языков. М., Мир, 1986

26. Суханов Е.В., Шур А.М. Об одном классе формальных языков // Алгебра и Логика, 1998, т.37, №4, 478-492

27. Шур А.М. Бинарная избегаемость и слова Туэ-Морса // Доклады РАН, 1996, 348(5), 598-599.Работы автора по теме диссертации:

28. Клепинин A.B. Об алгебраических свойствах языка Аршона // Областной конкурс студенческих научных работ. Тезисы работ. Екатеринбург, 1997, 19-20

29. Клепинин A.B. О синтаксических конгруэнциях бесповторных языков над конечными алфавитами // Российская конференция Дискретный анализ и исследование операций, материалы конференции, Новосибирск, 2002, стр.129

30. Клепинин A.B. Изоморфизмы и кроссплатформенные приложения // Международная конференция Мальцевские чтения, материалы конференции, Новосибирск, 2004,http: / / www.math.nsc.ru/conference/malmeet / 04/Klepinin.pdf

31. Клепинин A.B. Об универсальной модели организации доступа к базам данных И Урал. ун-т. Екатеринбург, 2005, деп. в ВИНИТИ 13.04.2005 №498-В2005

32. Клепинин A.B. Применение SQLj для реализации объектного доступа к данным // Урал. ун-т. Екатеринбург, 2005, деп. в ВИНИТИ 13.04.2005 №497-В2005

33. Бакиров М.Ф., Клепинин A.B., Суханов Е.В. О комбинаторно-алгебраических свойствах бесповторных последовательностей / / Kurosh Algebraic Conference '98 Abstracts of Talks, Moscow, 1998, 139-140

34. Klepinin A.V., Sukhanov E.V. On combinatorial properties of the Arshon sequence // Discrete Applied Mathematics 114 (2001) 155-169