Лекции по Основам ВТ
Информация - Компьютеры, программирование
Другие материалы по предмету Компьютеры, программирование
и и, или, не и кванторы всеобщности и существования.
Общая запись выражения с переменными на домене:{x1...xk| (x1...xn)} формула , которая обладает свойством , что только ее свободные переменные на доменах являются различными переменными.
Пример: {x1x2|R1(x1x2)(y)( R2(x1y) R2(x2y)} Означает множество таких кортежей в R1, что ни один из их компонентов , не является первым компонентом какого-либо отношения R2.
Реляционные исчисления с перменными кортежами.
Вид выражения: { t/.. (t)} t относится к .. (t) ; tединственная свободная переменная кортеж . Обозначить кортеж фиксированной длины , если необходимо указать арность кортежа , то tii арность. Пси- это некоторая формула, построенная по специальным правилам.
Для обозначения переменных кортежей чаще пользуются прописными буквами.
Пример:{t(R1(t) U R2(t))} интересуют все кортежи t принадлежащие R1(t) или R2(t). запись справедлива когда R1(t) и R2(t) имеют одинаковую арность . Эта операция эквивалентна операции U в реляционной алгебре.
Формулы в реляционном исчислении строятся из атомов и совокупности операторов (арифметических и логических)
Атомы формул бывают 3-х типов: 1) R(t) , R имя отношения. Атом означает, что t есть кортеж в отношении R. 2) S[i] u[j] , где s и u являются переменными кортежами , -арифметический оператор (>= 5-го компонента переменной u. 3) s[i] a равносильно a s[i] ,где a-конст. пример: s[3]=70 3-й компонент кортежа s равен 70.
При записи формул используются понятия свободных и связанных переменных кортежей , это связано с применением в этих формулах кванторов.( и ) Кванторы играют ту же роль , что и декларации в языках программирования.
Понятие свободных переменных аналогично понятию глобальных переменных , описывающихся в текущей процедуре . Понятие связанных переменных аналогично локальным переменным , описывающимся в текущей процедуре.
Определение формул , а так же свободныхи связанных вхождений переменных кортежей.
1) каждый атоместь формула , все вхождения переменных кортежей упомянутых в атоме являются свободными. 2) если 1 и 2формулы , то справедливо: 1. 1 1 2 являются истинными, 2. 1U 2 обе истинны и также являются формулами. В виде дополнения в литературе добавляют 1тоже является формулой. Экземпляры переменных кортежей являются свободными или связанными. 3) если - формула, то существует такая S(), которая тоже является формулой ,т.е. S() 4) если -формула, то существует S() тоже формула. 5)Формула в случае необходимости может заключаться в ( ), порядок старшинства: 1-арифметические операторы сравнения; 2-кванторы всеобщности и существования; 3-логические операторы: не, и ,или (,,)
Теорема1: устанавливающая эквивалентность безопасных выражений в исчислении выражением в реляционной алгебре.
Формулировка: если Е выражение реляционной алгебры , то существует эквивалентное ему базисное выражение в реляционном исчислении с переменными кортежами Для основных операций реляционной алгебры можно указать следующие соответствующие выражения реляционного исчисления на переменных кортежах. 1) R1UR2{t/R1(t)UR2(t)} 2) (R1-R2){t/R1(t) , R2(t)} читается: множество кортежей t, что t принадлежит R1 и не принадлежит R2 .
Выражение исчисления с переменными на доменах эквивалентны заданному выражению исчисления с переменными на кортежах.
{t/ (t)}
1)если t является кортежем арности к , то вводится к новых переменных на доменах t1,t1...tk ; 2) атомы R(t) заменяются атомами R(t1,t2,...,tk) : R(t)R(t1...tk); 3) каждое свободное вхождение t[i] заменяется на ti; 4) для каждого квантора существования или всеобщности вводится m переменных на доменах , где m арность u . [u],(u)mu1...um. в области действия этой квантификации действуют замены R(u)R(U1...Um) ; U(i) Ui ; ( U) (U1)...(Um) ; ( u) (U1)...(Um) ;5)выполняется построение выражения {t1...tk/ (t1...tk} , -это в котором осуществлена замена переменных.
Теорема2: для каждого безопасного вырожения реляционного ичисления с переменными кортежами существует эквивалентное безопасное выражение реляционного исчисления на доменах
Теорема3: для каждого безопасного выражения реляционного исчисления с перменными на доменах существует эквивалентное ему выражение реляционной алгебры.
Дополнительные возможности языка манипулирования данными в реляционных системах.
ЯМД выходит за рамки абстрактных языков , т.к. для обработки данных требуются операции выходящие за рамки возможностей реляционной алгебры . Это прежде всего следующие команды: включить данные, модифицировать данные , удалить данные.
Арифметические выражения: 1) арифметические вычисления и сравнения могут непосредственно включаться в формулы селекции реляционной алгебры выражений или в атомы в выражениях реляционного исчисления 2) команды присваивантя и печати 3) агрегатные функции это функции применяемые к столбцам отношений , в результате выполнения которых вычисляется одна единственная величина .
Т.к. реляционные языки могут реализовывать функции не имеющие аналогов ни в реляционноцй алгебре , ни в реляционных исчислениях , то в действитеьности эти языки являются более чем полные, некоторые функции этих языков дублируются.
Полным считается язык в котором реализуются все возможности реляционного исчисления с переменными кортежами , либо спеременным