Конференции ИВТ СО РАН

Тезисы докладов

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

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

Сигнатура реляционной структуры L есть непустое множество с отображением, присваивающим каждому реляционному символу в L отношение той же арности над этим множеством. Пусть М – бесконечная структура сигнатуры L. Здесь мы рассматриваем упорядоченные структуры. Это означает, что L включает бинарный реляционный символ <, интерпретация которого в М удовлетворяет аксиомам линейного порядка.

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

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

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

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск