| Главная » Статьи » Программирование | [ Добавить статью ] |
Пролог и базы данных, будущее языка prolog
Есть серьезные основания утверждать, что Пролог на самом деле представляет из себя не много не мало, а идейный костяк СУБД будущего.
Действительно, ныне наиболее широкое распространение получили реляционные СУБД, управляющие данными, представимыми в виде таблиц. Существующие средства позволяют эффективно работать с данными, организованными таким образом, объемом десятков миллиардов записей. Стандартным языком для работы с табличными данными является с начала 80-х годов язык SQL. Для проверки дальнейших примеров использовалась система PostgreSQL* версии 6.4.2 1999 года, распространяемая на условиях BSD.
* Система PostgreSQL разрабатывается в Калифорнийском университете Беркли по заказу ряда оборонных и научных учреждений США с 1986 года с целью создания эффективной СУБД структуры более сложной, чем реляционные.
Однако, любую таблицу или множество таблиц можно описать на Прологе. Поэтому пролог-программы обычно и называют базами данных или, чтобы подчеркнуть их большую выразительную силу, базами знаний. Например, таблицу, содержащую города и расстояния по железной дороге между ними, можно описать так:
В этой пролог-программе описана таблица по имени paths, состоящая из 4-х записей и 3-х полей. На SQL запрос о расстоянии между Москвой и Брестом к подобной таблице выглядит так:
На Прологе этот же запрос будет таким:
Оба запроса гарантируют, что если существует несколько путей между двумя пунктами, то обо всех из них будет сообщено в ответе. В этих запросах важно, чтобы на первом месте стояла Москва, а затем Брест, что очень неудобно. Если не знать, что ставить на первое место, то на SQL придется либо требовать удвоения объема базы данных, либо писать следующий запрос:
Для того, чтобы избежать подобных неудобств при работе с Прологом, достаточно добавить к программе
одно правило:
В случаях, подобных поиску длин путей между Москвой и Киевом, SQL вообще ничем вразумительным помочь не сможет. Пролог же легко справляется с подобными задачами, т.е. поиском маршрутов в произвольном графе, заданном только путями, соединяющими соседние пункты, добавлением нескольких новых, хотя и не слишком тривиальных правил к своей базе данных.
То, что базовая часть SQL может быть реализована на Прологе, подтверждается тем, что некоторые дистрибутивы Пролога в качестве примера включают подобную реализацию. Такие средства SQL, как индексы, сортировка, группировки и т. п. связаны либо с машинным представлением данных, либо с готовыми высокоуровневыми функциями. Машинное представление базы данных на Прологе можно также оптимизировать, используя индексы, а с добавлением высокоуровневых средств вообще никаких проблем кроме чисто техниче- ских быть не может.
Что же касается баз данных не реляционной структуры, например, сетевых, продукционных или иерархических, которые для многих задач являются оптимальными с точки зрения соответствия структуре данных этих задач, то с ними связана та же проблема, что и с базой данных, описанной на языке логики предикатов, а именно отсутствие формальных, эффективных (не переборных) методов извлечения из них той части информации, которая соответствует заданному запросу.
Итак, для баз данных, структуры более сложной, чем предлагаемая Прологом, не существует СУБД, способной эффективно выдавать ответы на запросы. С другой стороны, структура реляционных БД является подмножеством структуры программ на Прологе. Следовательно, альтернативы Прологу как СУБД будущего нет. Конечно же имеется в виду не сам Пролог, как транслятор, а лишь язык на основе предложений Хорна, используемый для внешнего представления баз данных и, возможно, как язык запросов.
Если вспомнить судьбу другого языка программирования, разработанного математиками, Алгола, то предположение о малой самостоятельной жизнеспособности у Пролога получит еще одно подтверждение. Алгол, как и Пролог двадцать лет спустя, в течение десятилетия 60-х играл роль передового языка программирования, который не воспринимается профессионалами. Затем он постепенно исчез. С другой стороны, сегодня трудно назвать язык программирования, который бы в той или иной степени не основывался на идеях, впервые реализованных Алголом...
Использованная литература:
Опубликована в журналах "Компьюлог” №4, 2000, с.63–65, "Информационные технологии” №3, 2001, с.11–13.
Действительно, ныне наиболее широкое распространение получили реляционные СУБД, управляющие данными, представимыми в виде таблиц. Существующие средства позволяют эффективно работать с данными, организованными таким образом, объемом десятков миллиардов записей. Стандартным языком для работы с табличными данными является с начала 80-х годов язык SQL. Для проверки дальнейших примеров использовалась система PostgreSQL* версии 6.4.2 1999 года, распространяемая на условиях BSD.
* Система PostgreSQL разрабатывается в Калифорнийском университете Беркли по заказу ряда оборонных и научных учреждений США с 1986 года с целью создания эффективной СУБД структуры более сложной, чем реляционные.
Однако, любую таблицу или множество таблиц можно описать на Прологе. Поэтому пролог-программы обычно и называют базами данных или, чтобы подчеркнуть их большую выразительную силу, базами знаний. Например, таблицу, содержащую города и расстояния по железной дороге между ними, можно описать так:
% City1, City2, distance
paths(’Москва’, ’Брест’, 1094).
paths(’Москва’, ’Абакан’, 4229).
paths(’Москва’, ’Севастополь’, 1542).
paths(’Киев’, ’Брест’, 577).
paths(’Москва’, ’Брест’, 1094).
paths(’Москва’, ’Абакан’, 4229).
paths(’Москва’, ’Севастополь’, 1542).
paths(’Киев’, ’Брест’, 577).
В этой пролог-программе описана таблица по имени paths, состоящая из 4-х записей и 3-х полей. На SQL запрос о расстоянии между Москвой и Брестом к подобной таблице выглядит так:
SELECT distance
FROM paths
WHERE City1 = ’Москва’
AND City2 = ’Брест’;.
FROM paths
WHERE City1 = ’Москва’
AND City2 = ’Брест’;.
На Прологе этот же запрос будет таким:
paths(’Москва’, ’Брест’, X).
Оба запроса гарантируют, что если существует несколько путей между двумя пунктами, то обо всех из них будет сообщено в ответе. В этих запросах важно, чтобы на первом месте стояла Москва, а затем Брест, что очень неудобно. Если не знать, что ставить на первое место, то на SQL придется либо требовать удвоения объема базы данных, либо писать следующий запрос:
SELECT distance
FROM paths
WHERE City1 = ’Москва’
AND City2 = ’Брест’
OR City2 = ’Москва’
AND City1 = ’Брест’;.
FROM paths
WHERE City1 = ’Москва’
AND City2 = ’Брест’
OR City2 = ’Москва’
AND City1 = ’Брест’;.
Для того, чтобы избежать подобных неудобств при работе с Прологом, достаточно добавить к программе
одно правило:
paths(X, Y) :- paths(Y, X).
В случаях, подобных поиску длин путей между Москвой и Киевом, SQL вообще ничем вразумительным помочь не сможет. Пролог же легко справляется с подобными задачами, т.е. поиском маршрутов в произвольном графе, заданном только путями, соединяющими соседние пункты, добавлением нескольких новых, хотя и не слишком тривиальных правил к своей базе данных.
То, что базовая часть SQL может быть реализована на Прологе, подтверждается тем, что некоторые дистрибутивы Пролога в качестве примера включают подобную реализацию. Такие средства SQL, как индексы, сортировка, группировки и т. п. связаны либо с машинным представлением данных, либо с готовыми высокоуровневыми функциями. Машинное представление базы данных на Прологе можно также оптимизировать, используя индексы, а с добавлением высокоуровневых средств вообще никаких проблем кроме чисто техниче- ских быть не может.
Что же касается баз данных не реляционной структуры, например, сетевых, продукционных или иерархических, которые для многих задач являются оптимальными с точки зрения соответствия структуре данных этих задач, то с ними связана та же проблема, что и с базой данных, описанной на языке логики предикатов, а именно отсутствие формальных, эффективных (не переборных) методов извлечения из них той части информации, которая соответствует заданному запросу.
Итак, для баз данных, структуры более сложной, чем предлагаемая Прологом, не существует СУБД, способной эффективно выдавать ответы на запросы. С другой стороны, структура реляционных БД является подмножеством структуры программ на Прологе. Следовательно, альтернативы Прологу как СУБД будущего нет. Конечно же имеется в виду не сам Пролог, как транслятор, а лишь язык на основе предложений Хорна, используемый для внешнего представления баз данных и, возможно, как язык запросов.
Пролог и будущее
Перспективы собственно Пролога весьма туманны. Автор, например, в течении всей весны 2000 года не мог попасть на web-страницу (http://www.logic-programming.org/prolog std.html), посвященную стандартизации этого языка. Хотя некоторые энтузиасты возможно будут использовать его еще долго. На пути трансформации в полноценную СУБД Прологу нужно, как минимум, пройти через следующие изменения:- все предикаты должны стать динамическими;
- должно быть добавлено удобное средство для сохранения базы данных в файл.
Если вспомнить судьбу другого языка программирования, разработанного математиками, Алгола, то предположение о малой самостоятельной жизнеспособности у Пролога получит еще одно подтверждение. Алгол, как и Пролог двадцать лет спустя, в течение десятилетия 60-х играл роль передового языка программирования, который не воспринимается профессионалами. Затем он постепенно исчез. С другой стороны, сегодня трудно назвать язык программирования, который бы в той или иной степени не основывался на идеях, впервые реализованных Алголом...
Использованная литература:
- The PostgreSQL Development Team PostgreSQL User’s Guide /Edited by Thomas Lockhart, 1998 (http://postgreSQL.org).
- Жан-Луис Лорьер Системы искусственного интеллекта — М.: Мир, 1991.
- Тейз А., Грибомон П., Луи Ж. и др. Логический подход к искусственному интеллекту — М.: Мир, 1990.
- Игорь Швыркин Пролог. Генезис //Мир ПК, 5/2000, 48–53.
Опубликована в журналах "Компьюлог” №4, 2000, с.63–65, "Информационные технологии” №3, 2001, с.11–13.
Добавлено: 06.02.2011 | Просмотров: 11093 | Рейтинг: 4.7/3 |
Теги:
| Комментарии (0) | |