Университеттің 85 жылдығына арналған Қазіргі заманғы математика
Университеттің 85 жылдығына арналған «Қазіргі заманғы математика
жүктеу/скачать 12,2 Mb. Pdf көрінісі
|
TaimanovMatem
| Университеттің 85 жылдығына арналған «Қазіргі заманғы математика:
проблемалары және қолданыстары» III халықаралық Тайманов оқуларының материалдар жинағы, 25 қараша, 2022 жыл 420 Запрос базы данных может быть формально определен как отображение, которое принимает состояние базы данных и производит новое отношение фиксированной арности над М. Мы рассматриваем два языка для запрашивания. Запросы первого языка есть формулы сигнатуры L` – мы называем их ограниченными . Запросы второго языка есть формулы сигнатуры L`` – мы называем их расширенными . Итак, базы данных предназначены для хранения текущей информацииокак-то структурированной предметной области. В каждый момент времени эта информация является конечной и представляет собой конечный набор конечных таблиц. Обычно число таблиц и устройство каждой таблицы не меняются с течением времени, но меняются строки таблиц. Могут добавляться новые строки и удаляться некоторые старые. Строки хранящихся таблиц представляют собой конечные последовательности элементов. Число элементов каждой последовательности фиксировано для фиксированной таблицы. Устройство таблицы практически и есть число элементов в каждой строке этой таблицы. Более формально, каждая таблица – это конечно местное конечное отношение, а сама база данных – это конечный набор конечно местных конечных отношений. Для удобства разговора о базе данных каждому ее отношению приписывают некоторое имя с указанием числа аргументов (или местности) этого имени отношения. Схема (или сигнатура) базы данных и есть конечная последовательность этих имен отношений с указанием местности каждого имени. В каждый момент времени именам отношений из этой схемы присвоены некоторые отношения соответствующих местностей. Это – состояние базы данных в данный момент. Состояние называется конечным, если все его отношения конечны. Иногда удобно рассматривать не произвольные состояния базы данных, а ограниченные какими-то условиями. Типичным ограничением является условие, что элементы всех строк всех таблиц выбраны из фиксированного подмножества I универсума. Другими словами, каждому имени отношения из рассматриваемой схемы базы данных поставлено в соответствие отношение той же местности на множестве I. В этом случае говорят, что рассматриваемое состояние базы данных является состоянием над I. Мы будем рассматривать локально генерические запросы , которые являются инвариантами при любых сохраняющих линейное упорядочение отображениях конечных подмножеств универсума в универсум. Грубо говоря, ответ на такой запрос основывается на хранящейся информации, но не зависит от способа кодировки этой информации при хранении. Определение 1.Будем говорить что k–арный запрос является локально генерическим над конечными состояниями , если a тогда и только тогда когда ( a ) ( s )) для любого частичного <-изоморфизма : где для любого конечного состояния s над X и для любого k-кортежа a в X. Состояние s обогащает универсум M сигнатуры L до L -структуры, которую мы будем обозначать как ( M , s ) . Определение 2. -состояние s для L -структуры W называется псевдо-конечным в W , если ( W , s ) есть модель L -теории первого порядка всех структур ( W , r ) , где r – конечное состояние над W . Псевдо-конечное множество – это частный случай псевдо-конечного состояния. Имеется в виду сигнатура, состоящая из одного одноместного отношения и некоторых других отношений. Рассматриваются такие системы этой сигнатуры, на которых выполняются все замкнутые формулы логики предикатов, истинные на всех конечных системах этой сигнатуры. Тогда интерпретация этого одноместного отношения в такой системе называется псевдо-конечным множеством. |