Структурно-лингвистические, алгоритмические и аппаратные средства акселерации символьной машины баз данных тема диссертации и автореферата по ВАК РФ 05.13.05, кандидат технических наук Сорокин, Валерий Евгеньевич

• Сорокин, Валерий Евгеньевич
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Сорокин, Валерий Евгеньевич

ф ВВЕДЕНИЕ

Глава 1. Аналитический обзор современного состояния средств

СУБД и машин баз данных .Г

1.1. Общие положения: исторический очерк

1.2. Неоднородные многопроцессорные ма шины баз данных (МБД) 21 .|г 1.3. Параллельные машины баз данных

1.4. Побудительные причины исследования и сущность предлагаемого подхода к созданию МБД

1.5. Выводы

Глава 2. Структурно - лингвистические средства акселерации —

2.1. Понятийный базис продукционной алгоритмической системы

2.2. Классификация формул подстановок

2.3. Способы синтеза акселерационных форм представления продукций

2.4. Иллюстрация продукционной реализации операций реляционной алгебры

2.5. Способы сопоставления (поиска по образцу)

2.6. Способы сортировки

2.6.1. Классификация алгоритмов сортировки последовательное

2.7. Способ парной параллельной сортировочной транспозиции эле ментов и слияния отсортированных последовательностей

2.8. Выводы

Глава 3. Разработка аппаратных средств акселерации 3.1. Способ организации машины баз данных 3.2. Специализированное устройство сортировки

3.3. Специализированное устройство слияния

3.4. Специализированное устройство быстрого поиска позиций вхождений образцов.

ЗАЛ. Работа устройства поиска вхождений образца

3.5. Специализированное устройство модификации слов

3.6. Выводы

Глава 4. Алгоритмические средства устройств управления специализированными устройствами МБД и результаты исследования скоростных характеристик 4.1. Алгоритмы управления устройств сортировки и слияния

4.1.1. Алгоритм управления устройства сортировки

4.1.2. Алгоритм управления устройства слияния

4.2. Алгоритм управления устройства поиска вхождения

4.3. Алгоритм управления устройства модификации

4.4. Результаты исследования скоростных характеристик

4.4.1. Сопоставительный анализ ускорений разработанного устройства и аналога

4.4.2. Анализ скоростных характеристик устройства поиска

4.4.3. Анализ скоростных характеристик продукционного символьного процессора .J

4.5. Выводы

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

i Актуальность работы. Сбор релевантной информации, надежность её хранения, высокоскоростной доступ и обработка при минимально допустимой стоимости составляют основные направления в условиях глобальной информатизации и компьютеризации. Бурный рост объёмов, разнообразия типологий и сложности логических структур информации в современных компьютерных системах определяет необходимость в разработке новых методов и систем хра-У нения с быстрым откликом на запросы пользователей.

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

Решению проблем создания машин и систем баз данных и знаний посвящены работы М. Сенко, Я. Палмера, Г. Найсена, Э. Озкарахана, JI. Калини-ченко, Д. Поспелова и других исследователей как у нас в стране, так и за рубежом. ф Между тем, в существующих работах отсутствуют реализации машин баз данных, основанных на технологии обработки символьной информации.

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

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

Работа выполнялась в рамках НИР по Единому заказ-наряду и грантам Г00-4.2.15 и Г02-4.2.5, выполненных в Курском государственном техническом университете в период с 1999 по 2005 годы при непосредственном участии автора.

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

Для достижения указанной цели поставлены и решены следующие основные задачи:

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

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

- разработка технических решений устройств: поиска, модификации, сортировки и слияния упорядоченных данных, и осуществление их структурно-функционального объединения в архитектуру символьной машины баз данных;

- проведение экспериментальных исследований скоростных характеристик символьной машины баз данных.

Объектом исследования являются алгоритмические и аппаратные средства, поддерживающие процессы управления данными.

Предмет исследования составляют процессы преобразования информации в системах управления базами данных (СУБД).

Методы исследования базируются на теории алгоритмов, конструктивной математической логике, современной прикладной семиотике, а также теории автоматов и проектирования ЭЦВМ.

Научная новизна работы заключается в получении следующих результатов:

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

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

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

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

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

Апробация работы. Результаты диссертационного исследования докладывались и обсуждались на:

- 2-й Международной конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации. Распознавание-1995» (Курск, 1995);

- Международной конференции «Актуальные проблемы компьютеризации в странах СНГ» (Донецк, 2002);

- 6-й Международной конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации. Распознавание-2003» (Курск, 2003);

- 6-й Международной научно-технической конференции «Медико-экологические информационные технологии-2003» (Курск, 2003).

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

Реализация и внедрение. Результаты диссертационной работы внедрены в НПО «Экран» (Москва), а также используются в учебном процессе Курского государственного технического университета в рамках курса «Высокопроизводительные вычислительные системы», что подтверждается актами о внедрении.

На защиту выносятся:

1. Акселерационные формы представления продукций, а также образцов для быстрых символьных вычислений и процессов сопоставления в контурах СУБД.

2. Способы, алгоритмы и устройства быстрого поиска и модификации, а также алгоритмы и устройства быстрой параллельной сортировки и слияния.

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

4. Результаты исследования скоростных характеристик символьной машины баз данных.

Структура и объём диссертации. Диссертация состоит из введения, четырех глав и заключения, изложенных на 167 страницах, содержит 57 рисунков, 2 таблицы, списка литературы из 75 наименований.

Заключение диссертации по теме «Элементы и устройства вычислительной техники и систем управления», Сорокин, Валерий Евгеньевич

4.5. Выводы

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

В результате проведения эксперимента в конфигурации с раздельным использованием устройств СМБД для получения зависимости затрат времени от длины данных, соответственно, для основных функций: SELECTION 1% (выборка 1 процента данных); SELECTION 10% (выборка 10 процента данных); JOIN AselB (объединение двух отношений); JOIN CselAselB (объединение трёх отношений); MIN Scalar (скалярная операция нахождения минимума); MIN Group (групповая операция нахождения минимума); COUNT Scalar (скалярная операция СЧЁТ); COUNT Group (групповая операция СЧЁТ) - достигается скоростное преимущество в три-четыре раза по отношению к СУБД-машине Rinda ее аналогов: Terada и Gamma для всех перечисленных функций.

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

Установлено, что затраты времени на реализацию функции DECODE, реализованной в языке PL-SQL, поддерживаемом СУБД Oracle, в конфигурации с совместным функционированием устройства поиска и модификации с использованием акселерационных форм представления продукций уменьшаются до восемнадцати раз по сравнению с выполнением этой функции на марковском символьном процессоре.

157

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Довгаль, В. М. Проблема визуализации объектов [Текст] / В. М. Довгаль, В. Е. Сорокин // Материалы 2-й Межд. конф. «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации» («Распознавание-1995»). Курск, 1995. С. 245-246.

2. Пат. РФ 2150740, МКИ7 G 06 F 17/30. Устройство для реализации подстановок [Текст] / Сорокин В. Е. [и др.]. Опубл. 10.06.2000, Бюл. № 16.

3. Сорокин, В. Е. Архитектура символьной СУБД-машины [Текст] / В. Е. Сорокин // Материалы Межд. конф. «Актуальные проблемы компьютеризации в странах СНГ». Донецк: АРК-Ц, 2002. С. 70-78.

4. Сорокин, В.Е. Метод быстрой обработки двумерных массивов [Текст] / В.Е. Сорокин [и др.] // Материалы 6-й Межд. конф. «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации» («Распознавание-2003»). Курск, 2003. С. 90-92.

5. Сорокин, В.Е. Процессор быстрых символьных вычислений [Текст] / В.Е. Сорокин [и др.] // Материалы 6-й Межд. науч.-техн. конф. «Медико-экологические информационные технологии-2003». Курск, 2003. С. 157-158.

6. Довгаль, В. М. Проблема построения символьных бриджеров для сопряжения разнородных компьютерных сетей. Ч. 1. Акселерация работы автономных продукций [Текст] / В. М. Довгаль, В. Е. Сорокин,

A. В. Шанцев //Телекоммуникации. 2004. № 3. С. 16-22.

7. Довгаль, В. М. Проблема построения символьных бриджеров для сопряжения разнородных компьютерных сетей. Ч. 2. Акселерация работы алгоритмических схем и архитектура аппаратных средств [Текст] /

B. М. Довгаль, В. Е. Сорокин, А. В. Шанцев // Телекоммуникации. 2004. №7. С. 5-13.

160

Список литературы диссертационного исследования кандидат технических наук Сорокин, Валерий Евгеньевич, 2005 год

1. Озкарахан, Э. Машины баз данных и управление базами данных: Пер. с англ. Текст. / Э. Озкарахан // М.: Мир, 1989. 487 с.

2. Su, S. Database machine and some issues on database management systems standart Text. / S. Su, H. Chang, P. Eischer, E. Lowenthal // AFIPS, NCC, USA, 1980.

3. Boral, H. Database machine Morphology Text. / H. Boral, S.Redfield // Proc. of the 11-th Int. Conf. on VLDB. Database machine Morphology , Stockholm, Aug. 1985.

4. Ozkarachan, E. Database machines and database management Text. / E. Ozkarachan // USA, Prentice Hall, 1986.

5. Hawthorn, P. B. Performance analysis of alternative database machine architectures Text. / P. B. Hawthorn, D. J. De Witt // IEEE Trans, of Software Eng.-Jan. 1982.-Vol. SE-8,No.l.

6. Калиниченко, Л. А. Машины баз данных и знаний. Текст. / Л. А. Калиниченко, В. М. Рыбкин // М.: Наука. Гл. ред. физ.-мат. лит., 1990. 248 с.

7. Калиниченко, Л. А. Методы и средства интеграции неоднородных баз данных. Текст. / Л. А. Калиниченко // М.: Наука, 1983.- 423 с.

8. Feng, Т. A. Very large data base computer Text. / T. A. Feng // IEEE Computer Soc. Workshop on Computer Architecture for Analysis and Image Database Management. Virginia, USA, 1981.

9. Day, K. Micro-based DBMS manages and relational database Text. / K. Day // Electronic Design. June 1982. - No. 3.

10. E. A. Ozlcarahan, L. A. Kerschberg I I Heterogeneous Technical Report TR-82-006, Dept. of Computer Science, Arizona State University, Tempe, 1998.

11. Ozlcarahan, E. A. Performance Evaluation of a Relational Associative Processor. Text. / E. A. Ozlcarahan, S. A. Schuster, К. C. Sevcik // ACM Transactions on Database Systems, 1999, Vol. 2, No. 2.

12. Kamibayashi, N. A. Database machine based on the data distribution approach Text. / N. A. Kamibayashi //AFIPS, NCC. USA, Virginia, 1997.

13. Kamibayashi, N. A. SPIRIT-3: an advanced relational data base machine introducing a novel data-staging architecture with tuple stream filters to process relational algebra Text. /N. A. Kamibayashi, K. Seo //AFIPS, NCC.—1998.

14. Hsiao, D. K. Database machine architecture on the Context of information technology Evolution Text. / D. K. Hsiao, S. Madnick // Proc. of the 3-rd Intern. Conf. on VLDB.- Japan, Tokyo, 1998.

15. Madnick, S. E. INFOPLEX hierarchical ecomposition of a large information management system using microprocessor complex Text. / S. E. Madnick // AFIPS, NCC.- 2001.

16. Seo, K. Look-ahead data staging architecture for relational data base machine Text. / K. Seo, A. Mikamatsu, H. Aiso, N. A. Kamibayashi // Proc. of 8-th Ann. Symp. Comput-Architecture.-May 1998.

17. Takeda, H. "An Accelerating Processor for Relational Operations," Text. / H. Takeda, T. Satoh // Proc. Int'l Conf. Databases, Parallel Architectures, and Their Applications. Mar. 1999, p. 559.

18. Shiokawa, S. "UfPS-ll/5E Series Mainframe" Text. / S. Shiokawa, Y. Obasht, A. Nagoya// Review of the ECL. Vol. 35, No. 6, June 2001, pp. 633-641.

19. Itoh, K. "DIPS-V30 Development." Text. / K. Itoh, R. Yazawa, Y. Fukumura // Review of the ECL, Vol. 34, No. 5, May 2000, pp. 587-593.

20. Aid, S. G. Parallel Sorting Algorithms Text. / S. G. Akl // Academic Press, New York. 1985.

21. Blasgenand, M. W. "Storage and Access in Relational Data Bases," Text. / M. W. Blasgenand, 1С. P. Eswaran // IBM System J. Vol. 16, No. 4, 2002, pp. 363377.

22. Kitsuregawa, M. "Application of Hash to Data Base Machine and Its Architecture" Text. / M. Kitsuregawa, M. Tanaka, T. Moto-oka // New Generation Computing, Vol. 1, No. 1, 2002, pp. 63-74.

23. McGregor, D. R. "High Performance Hardware for Database Systems in Systems for Large Data Bases" Text. / D. R. McGregor, R. G. Thomson, W. N. Dawson, P. C. Lockemann, E. J. Neuhold [eds.] // North-Holland, Amsterdam, 2001, pp. 103-116.

24. Satoh, T. "A Compact Multiway Merge Sorter Using VLSI Linear-Array Comparators" Text. / T. Satoh, H. Takeda, N. Tsuda // Proc. Int'lConf, Foundation Data Organization and Algorithms, June 1999, pp. 223-227.

25. Tsuda, N. "A Pipeline Sorting Chip," Text. / N. Tsuda, T. Satoh, T. Kawada // Proc. IEEE Int'l Solid-State Circuits Conf. IEEE CS Press. Los Alami-tos. Calif, 2001. pp. 270-271.

26. Maryanski, F. Backend database systems Text. / F. Maryanski // Computing Surveys.- March 1980.- Vol. 12, No. 1.

27. ЗЗ.Четверушкин, Б. H. Высокопроизводительные многопроцессорные вычислительные систем Текст. / Б. Н. Четверушкин // Вестник РАН, 2002, том.72. № 9. С. 786-794.

28. Пат. РФ 2150740, МКИ7 G 06 F 17/30. Устройство поиска вхождений Текст. / Сорокин В. Е. [и др.]. Опубл. 10.06.2000, Бюл. № 16.3 5.Коллинз, Г. М. Микроэлектронные технологии. Текст. / Г.М.Коллинз // Интрон-М, 2003. 271 с.

29. Зб.Ва, Б. У. ЭВМ для обработки символьной информации Текст. / Б. У. Ва, М. Б. Лоурай, Ли Гоцзе // ТИИЭР. 1989. т.77, № 4. С.5-40.

30. Эйсымонт, Л. К. Компьютеры для обработки символьной информации Текст. / Л. К. Эйсымонт // Зарубежная радиоэлектроника. 1990. №. 4. С.3-28.

31. Вагин, В. Н. Проект «ПАМИР» Текст. / В. Н. Вагин, В.Н.Захаров, Д.А.Поспелов и др. // Известия АН СССР. Техническая кибернетика. 1988. №2. с.161-171.

32. Довгаль, В. М. Методы модификации формальных систем обработки символьной информации. Текст. / В. М. Довгаль // Курск: Курск, гос. техн. унт, 1996.115 с.

33. Довгаль, В. М. Марковские системы обработки символьной информации Текст. / В. М. Довгаль // Известия вузов "Приборостроение". Т. 40, вып.2, 1997. С.55-58.

34. Марков, А. А. Теория алгорифмов. Текст. / А.А.Марков, М. Н. Нагорный // М.: Наука, 1984. 432 с.

35. Пат. РФ 2039375, МКИ6 G 06 F 17/00, 17/20. Устройство для реализации продукций Текст. / В. М. Довгаль [и др.] (Россия). Опубл. 09.07.95, Бюл. № 19.

36. Пат. РФ 2067315, МКИ5 G 06 F 15/20. Устройство для реализации подстановок Текст. / В. М. Довгаль [и др.] (Россия). Опубл. 27.09.96, Бюл. № 27.

37. Довгаль, В. М. Проблема построения символьных бриджеров для сопряжения разнородных компьютерных сетей. Часть 1. Акселерация работы автономных продукций Текст. / В. М. Довгаль, В. Е. Сорокин, А. В. Шанцев // Телекоммуникации. № 3. 2004. С. 16-22.

38. Довгаль, В. М. Акселерация обработки символьной информации Текст. / В. М. Довгаль, В. В. Малютин // Сборник материалов 6-ой Международной научно-технической конференции "Медико-экологические информационные технологии-2003", Курск, 2003. С. 174-177.

39. Довгаль, В. М. Метод синтеза продукций-акселераторов конструктивных процессов: Препринт 56-96 Текст. / В. М. Довгаль // Курск, гос. техн. ун-т. Курск, 1996. 11 с. 161.

40. Довгаль, В. М. Алгоритмический индикатор пересечения слов: Препринт 58-96 Текст. / В. М. Довгаль // Курск, гос. техн. ун-т. Курск, 1996. 6 с.

41. Довгаль, В. М. Конструктивные процессы, порождаемые продукциями с пересекающимися образцами и модификаторами: Препринт 63-96 Текст. / В. М. Довгаль // Курск, гос. техн. ун-т. Курск, 1996. 7 с.

42. Довгаль, В. М. Самоиндукционные процессы в схемах продукций: Препринт 63-96 Текст. / В. М. Довгаль // Курск, гос. техн. ун-т. Курск, 1996. 7 с.

43. Довгаль, В. М. Взаимодействие конструктивных процессов: Препринт 52-96 Текст. / В. М. Довгаль // Курск, гос. техн. ун-т. Курск, 1996. 7 с.

44. Писаненко, Р. И. Способы быстрого сопоставления с образцом Текст. / Р. И. Писаненко, В. М. Довгаль // Известия КГТУ. №2(9). 2002. С. 111-117.

45. Baeza-Yates, R. A. "Searching subsequences, Baeza-Yates R.A." Text. / R. A. Baeza-Yates // Theoretical Computer Science, 1991, Vol. 78, No. 2, p. 363-76.

46. Воуег, R. S. "A fast string searching algorithm" Text. / R. S. Boyer, J. S. Moore // Communications of the ACM, 1977, Vol. 20, No. 10, p. 762-72, October 1977.

47. Knuth, D. E. Fast pattern matching in strings Text. / D. E. Knuth, J. H. Morris (Jr), V. R. Pratt // SIAM Journal on Computing 6(1), 1977:323-350.

48. Horspool, R. N. Practical fast searching in strings Text. / R. N. Horspool Software//Practice & Experience, 10(6), 1980:501-506.

49. Smith, P. D. Experiments with a very fast substring search algorithm Text. / P. D. Smith // Software Practice & Experience 21(10), 1991:1065-1074.67.http://www.codenet.ru.

50. Марчук, Г. И. Модульная асинхронная развиваемая система: концепция Препринт N 86 Текст. / Г. И. Марчук, В. Е. Котов // ВЦ СО АН СССР. -1978.154 с.

51. Котов, В. Е. Введение в теорию схем программ Текст. / В. Е. Котов // Новосибирск, Наука, 1978, 258 с.

52. Котов, В. Е. Асинхронные вычислительные процессоры над памятью. Текст. / В. Е. Котов, А. С. Нариньяни // Кибернетика, 1966. № 3. С. 64-71.

53. Скотт, Урман Oracle9i. Программирование на языке PL/SQL: Пер. с англ. Текст. / У. Скотт// М.: Издательство "Лори", 2004, 544 с.

54. Грейвс, Марк Проектирование баз данных на основе XML: Пер. с англ. Текст. / М. Грейвс // М.: Издательский дом "Вильяме", 2002, 640 с.

55. Валиков, А. Н. Технология XSLT Текст. / А. Н. Валиков // СПб.: БХВ-Петербург, 2002, 544 с.74.http://www.intelligententerprise.com.

56. Пат. РФ 2246750, МПК7 G 06 F 7/08. Устройство для сортировки чисел /Довгаль В.М. и др. (Россия). Опубл. 20.02.05, Бюл. № 5.

57. ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «КУРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

58. УДК 681.3 На правах рукописи

59. СОРОКИН ВАЛЕРИЙ ЕВГЕНЬЕВИЧ

60. СТРУКТУРНО-ЛИНГВИСТИЧЕСКИЕ, АЛГОРИТМИЧЕСКИЕ И АППАРАТНЫЕ СРЕДСТВА АКСЕЛЕРАЦИИ СИМВОЛЬНОЙ МАШИНЫ БАЗ ДАННЫХ

61. Специальность 05.13.05 «Элементы и устройства вычислительной техники и систем управления»