Применение логики предикатов в базах данных

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

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

Логика эффективно применима при описании данных и разработке методов доступа, формулируемых в виде задачи логического вывода, например в информационно-поисковых системах[1].

Рассмотрим следующий пример структуры данных[2]. Данные определяются многоместными предикатами и задаются следующими таблицами.

Номер поезда х

Откуда у

Куда 2

28

Москва

Казань

10

Смоленск

Казань

Категория поезда (дг, у)

Номер поезда х

Категория у

28

Скорый

10

Пассажирский

Обслуживание (дг, у)

Номер поезда х

Обслуживание у

28

Буфет

10

Ресторан

Расписание (я:, у, z, k)

Номер поезда х

Время отправления <ч.мин> у

Время прибытия 0 2

Время в пути о к

28

<20.20>

10

<10.15>

Остановки (д:, у, z, k)

Номер поезда х

Остановки у

Время прибытия г

Время отправления к

28

Муром

<23.20>

<23.25>

10

В данном приложении используются различные области интерпретации переменных xt е Q,;x„e Qn.

Рассмотрим расширенную область интерпретации Q = Qx v Q2 v ... v Qn.

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

Следующая логическая формула связывает заданные отношения в составе утверждения:

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

1. Существует ли данная остановка на пути из Москвы или Твери? Ответом на этот вопрос (запрос) является хотя бы одна подстановка,

при которой формула выполнима.

  • 2. Показать все остановки заданного маршрута.
  • 3. Номер поезда, который останавливается в Муроме в t = <23.20>.

  • [1] Грэй П. Логика, алгебра и базы данных.
  • [2] Борщев В. Б. Пролог: основные идеи и конструкции // Прикладная информатика. Сб.статей / под ред. В. М. Савинкова. М.: Финансы и статистика, 1986. С. 49—76.
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >