Косьмина Я.О.
http://kid.stu.cn.ua/~dart_vader
e-mail: [email protected]
Распределённая параллельная Пролог-система
Традиционно базы данных не имеют универсальных языков обработки данных [1], ограничиваясь языками запросов. С другой стороны универсальные языки обработки данных не имеют возможности работать с большими массивами информации. Также жестко стоит вопрос производительности систем обработки информации.
Различные реализации Пролога уже давно взаимодействуют с базами данных через интерфейсы [2] или драйверы доступа к системам управления базами данных (Amzi, GNU, SWI и др.). Значительный интерес представляет параллелизм и распределение в Акторном Прологе [3], при создании которого его автор, А.А. Морозов, частично решил проблему “необратимых” процессов, существующих вне Пролог-машины, но с которыми Пролог должен взаимодействовать. Ещё одной важной особенностью Акторного Пролога является то, что он позволяет сохранить текущее состояние программы на диск и затем восстановить выполнение этой программы.
Среди диалектов Пролога представляет интерес язык параллельного логического программирования KL1 [4]. При тестировании на стандартных примерах, удовлетворяющих ограничениям KL1, программа, написанная на этом языке, выполнялась в два раза быстрее в сравнении с аналогичной программой, написанной на Прологе (на компьютере с одним процессором). Все прикладные системы, написанные на KL1, работают со скоростью, почти линейно пропорциональной числу процессоров.
В данной статье рассматривается возможность создания параллельной Пролог-системы, которая базируется на универсальном языке обработки данных.
Универсальный язык обработки данных
Среди универсальных языков обработки данных высокий интерес представляют логические языки. Они имеют следующие преимущества: вывод целевого утверждения и обратимость процессов. Программа на логическом языке состоит из набора утверждений, составляющих базу знаний. Выполнение программы - это конструктивный вывод целевого утверждения из программы.
Среди логических языков наибольшую известность получил Пролог. Для Пролога существует стандарт ISO, его интерпретаторы и компиляторы поддерживаются рядом фирм на различных платформах. Эти особенности послужили главными аргументами в пользу выбора языка SWI-Пролог, среди диалектов Пролога – KL1[4] и других логических языков, например языка Рефал [5].
Типичный способ представления данных – таблица, она состоит из строк, а строки – из полей. Проводя аналогию с языком Пролог: поля – это аргументы терма, строки – это факты, а таблицы – предикаты, рис.1.
Т
поле(‘ФИО’, фамилия).
поле(‘ФИО’, имя).
поле(‘ФИО’, отчество).
|
Фамилия |
имя |
о  тчество
|
|
Торндотар |
Дария |
Т  ор
|
|
Нотар |
Ив |
Фёрн |
‘ФИО’(‘Торндотар’, ‘Дария’, ‘Тор’).
‘ФИО’(‘Нотар’, ‘Ив’, ‘Фёрн’).
Рис.1. Представление реляционной таблицы в Прологе.
Конечно, поля таблиц придётся хранить отдельно – в специальном предикате “поле”.
Отношения между таблицам
и задаются с помощью правил, также как представления (view) и процедуры.
На Прологе легко задаются отношения реляционной алгебры, пример на рис. 2.
select *
from ФИО
where Фамилия = “Торндотар”;
а)
forall( ‘ФИО’('Торндотар', A, B) ).
б)
Рис. 2. Отношение select на SQL (а) и на Прологе (б).
Как уже упоминалось, Пролог является языком обработки данных. Поэтому, например, после выполнения запроса на рис. 2б можно сразу обработать данные. Языки запросов не дают такой возможности.
Используя в качестве хранилища предикатов файлы на внешнем носителе можно получить большие объёмы данных для Пролог-машины. Для обмена данными между диском и памятью будет использоваться кэш данных.
Производительность
Проблемы производительности решаются распределением базы предикатов и распараллеливанием целей, возникающих в ходе вывода Пролог-машины.
Распределение предикатов возможно двумя путями:
а) дублирование базы предикатов для всех узлах системы обработки данных;
б) распределение информации по узлам.
Пункт (б) более предпочтителен, поскольку он позволяет сэкономить на дисковом пространстве. Алгоритм распределения ресурсов распределяет данные и процессорное время по ходу вычислений.
Существует ряд алгоритмов распределения ресурсов: “распределитель-работники”, хэш-фрагментация и др. [6]. Из рассмотренных алгоритмов для реализации Пролог-системы был выбран алгоритм балансировки, зарекомендовавший себя в проекте FGCS (Fifth Generation Computer Systems) [4]. Этот алгоритм применяется для распределения базы предикатов логического языка, распараллеливания логического вывода и обладает почти линейной зависимостью производительности от числа процессоров.
Производительность сильно зависит от индексации базы предикатов, эта проблема подробно рассматривается в моей статье “Индексация предикатов в Прологе” [7].
Выводы
Благодаря использованию Пролога как языка обработки данных может быть достигнута высокая логическая выразительность программ. Предложенные методы позволяют повысить производительность систем обработки данных, основанных на использовании машины Пролога.
Новизна изложенного подхода состоит в объединении двух компонентов – языка программирования Пролог и базы данных с последующим получением нового качества параллельной Пролог-системы: хранимой распределенной базы предикатов на внешнем носителе.
Список литературы
-
Хомоненко А.Д. и др., Базы данных. – Спб.: "КОРОНА принт", 2002, 672c. -
IF/Prolog / https://www.ifcomputer.co.jp/en/manuals5.2/home.html. -
А.А. Морозов, Логический анализ функциональных диаграмм в процессе интерактивного проектирования информационных систем: Диссертация на соискание учёной степени кандидата физико-математических наук, - Москва, 1998. -
Transforming CHIP Programs to KL1. Design and Implementation of the CHUKL Preprocessor, Konstantinos D. Varsamos; MSc Thesis, Department of Computer Science University of Bristol: September 1994. -
Метавычисления и их приложения (диссертация). С.Абрамов / ftp://ftp.botik.ru/pub/local/Sergei.Abramov/book.appndx/dissertation -
В.В. Воеводин, Вл.В. Воеводин, Параллельные вычисления. – Спб.: "БХВ-Петербург" , ISBN: 5-94157-160-7, 2004, 608 c. -
Я.О. Косьмина, Индексация предикатов в Прологе, 2004 / https://online.com.ua/~dart/notikoj/index_predicates.html.