Реляционная логика. Основные понятия.

Известно, что соответствие, заданное на элементах одного множества X, называют отношением (relation). Правила, заданные отношением, формируют множество упорядоченных последовательностей элементов множества X. В свою очередь это множество является подмножеством декартового произведения множества X, т. е. rel = {|xi  X}  n XУпорядоченная последовательность называется кортежем, а его отдельные элементы – компонентами кортежа. Кортежи принято обозначать символами t  T, где T – множество кортежей. Число компонент кортежа определяет его длину или арность. Таблица – наиболее удобная форма отображения отношения. Если столбцами таблицы являются некоторые подмножества множества X, а элементами таблицы – значения элементов множества X, то строками являются кортежи заданного отношения. Область определения значений компонентов кортежа принято называть доменом и обозначать Di. Признак, по которому выделена область определения компоненты кортежа – домен – называют атрибутом и обозначают символом Ii. Значение атрибута, взятое из домена, выделяет объект реального мира из множества ему подобных по данному признаку. Последовательная запись атрибутов, заданная декартовым произведением доменов формирует схему отношения, т. е. Sch(r) = r(I1, I2,… Ik) = RКаждая область определения значений атрибутов может быть поименована, что существенно облегчает организацию обработки данных. Несколько атрибутов могут иметь единую область определения их значений (один домен), но не наоборот. Набор кортежей одного отношения формирует тело таблицы, место атрибута в которой задано схемой отношения, а его значение – областью определения Di. Количество используемых в отношении атрибутов (столбцов таблицы) определяет его арность, а число кортежей – мощность. Итак, одним из способов задания и описания отношения является таблица, “шапка” которой формируется схемой отношения, а “тело” есть множество кортежей, описывающих множество объектов реального мира. Схема отношения задаёт строгий порядок компонент кортежа, не допуская их перестановки и/или удаления из кортежа. Атрибуты кортежа должны зависеть только от ключа отношения, в противном случае отношение следует декомпозировать на 2 и более отношений. 2 6) Реляционная алгебра. Основные и дополнительные унарные операторы. Произвольное множество X с заданной на нём совокупностью операций, обеспечивающих функциональное отображение Г: Xn  X, называют алгеброй. При этом множество X называют основным множеством алгебры, знаки алгебраических операций – операторами, а объекты множества X, над которыми выполняются алгебраические преобразования – операндами. Если в качестве множества X использовать множество отношений, а в качестве алгебраических операций такие преобразования, которые обеспечивают формирование новых отношений, то получим особый тип алгебр – реляционную алгебру. Всё множество операторов реляционной алгебры можно представить 2-мя классами: унарные (1 операнд) и бинарными (2 операнда). Основные унарные операторы. Оператор выбора δB(r) (Selection (отношение, условия)) позволяет извлекать из данного отношения r кортежи, удовлетворяющие условию B, и формировать новое отношение r’. Условия представляют собой выражения, которые могут включать только операторы сравнения множества θ = {=, ≠, >, ≥, <, ≤}, между текущими и заданными значениями атрибутов, а также логические операторы для формирования сложных условий из множества Σ = {&, , }. В то же время использование функциональных символов в формировании условий запрещено. Оператор проекции πR’(r) (Projection(отношение, список_атрибутов)) позволяет формировать из данного отношения r новое отношение r’ путём удаления и (или) переупорядочения атрибутов в соответствии с заданной схемой нового отношения R’. Для выполнения этой операции должна быть прежде всего задана схема генерируемого отношения R’ = Sch(r’). Дополнительные унарные операторы. Оператор добавления (ADD (r; I1 = d1; I2 = d2;… Im = dm)) предусматривает добавление кортежа в заданное отношение. Для этого должно быть указано имя отношения и значения всех компонент кортежа, который необходимо включить в отношение. В случае, когда порядок атрибутов строго фиксирован, разрешается не указывать имена атрибутов, а только лишь их значения, т. е. ADD (r; d1; d2;… dm). Оператор добавления (DEL (r; I1 = d1; I2 = d2;… Im = dm)) определяет исполнение операции удаления кортежа из данного отношения. Для этого должно быть указано имя отношения и значения всех компонент кортежа. В случае, когда порядок атрибутов строго фиксирован, разрешается не указывать имена атрибутов, а только лишь их значения, т. е. DEL (r; d1; d2;… dm). В большинстве баз для этого используют ключ, когда достаточно указать имя отношения и значение ключа. Оператор изменения (CH (r, I1 = d1; I2 = d2; … Ii = di; … Ij = dj; … IiH = diH; IjH = djH)) позволяет выполнять изменение значений некоторых атрибутов кортежа. Для этого достаточно указать имя отношения, ключ записи кортежа, имя атрибута и его прежнее и новое значения. Но наиболее полно этот оператор использует запись всей строки таблицы с указанием всех значений атрибутов прежнего значения кортежа и новых значений атрибутов. 2 7) Реляционная алгебра. Основные бинарные операторы. см. вопрос 2 6)Оператор объединения (r1, r 2) (Union (отношение_1, отношение_ 2)) для двух отношений, имеющих одинаковые схемы, формирует новое отношение, объединяя все кортежи первого и второго отношений. При этом одинаковые кортежи двух отношений “сливаются” в один кортеж нового отношения. Оператор разности \(r1; r 2) (Difference (отношение_1, отношение_ 2)) для двух отношений, имеющих одинаковые схемы, формирует новое отношение, выбирая из первого отношения только те кортежи, которых нет во втором отношении. Оператор декартова произведения (r1; r 2) (Product (отношение_1, отношение_ 2)) формирует из двух отношений r1 и r2 арности n1 и n2 новое отношение арности (n1 + n 2). При этом первые n1 компонентов кортежа нового отношения r’ образованы, принадлежащими r1, а последние n2 компонентов – кортежами, принадлежащими отношению r2. Число кортежей нового отношения r’ определяется произведением числа кортежей первого и второго отношений, т. к. каждый кортеж первого отношения должен быть соединён со всеми кортежами второго отношения. 2 8) Реляционная алгебра. Дополнительные бинарные операторы. см. вопрос 2 6)Оператор пересечения (r1, r 2) (Intersection (отношение_1, отношение_ 2)) для двух отношений, имеющих одинаковые схемы, формирует новое отношение, выбирая только одинаковые кортежи из первого и второго отношений. Оператор естественного соединения (r1, r 2) (Join (отношение_1, отношение_ 2)) формирует из 2-х отношений r1 и r2, имеющих один или несколько одинаковых имён атрибутов, новое отношение r’, схема которого есть объединение атрибутов 2-х исходных отношений, а кортежи формируются из кортежей первого отношения, присоединяя кортежи 2-го отношения по одинаковым значениям одноимённых атрибутов. Для практического определения естественного соединения необходимо:a) найти декартово произведение 2-х отношений r1 и r2;b) совместить одноимённые столбцы декартова произведения;c) удалить строки, имеющие различные значения атрибутов в совмещённых столбцах. Оператор θ-соединения B(r1, r 2) (Join (отношение_1, отношение_2, условие)) формирует из 2-х отношений r1 и r2 арности n1 и n2 новое отношение r’ арности (n1 + n 2), обеспечивая условие. Для практического определения θ-соединения необходимо:a) найти декартово произведение 2-х отношений r1 и r2;b) соединить строки первой и второй таблиц отношений r1 и r2, если выполняется условие арифметического сравнения значений d1i и d2j-го атрибутов первого и второго отношений. 2 9) Реляционное исчисление (РИ) с переменными-кортежами. РИ с переменными-кортежами определяет способы и приёмы формирования выражения{t’|F(t)},где t – переменная-кортеж фиксированной длины;F(t) – формула логической функции, построенная из атомов и совокупности арифметических и логических операторов. Предметными переменными и предметными постоянными РИ являются кортежи. Для обозначения переменных кортежей дополнительно используем символы x и y, а для постоянных – u и v. Атом определяется следующими правилами: 1) если r – имя отношения, а x – переменный кортеж, то r(x) – атом; 2) если x и y – переменные кортежи, v  θ – арифметический оператор (знак сравнения), Ii и Ij – атрибуты, то x(Ii) v y(Ij), x(Ii) v kdi, kdi v y(Ij) – атомы; 3) никаких других атомов нет. При записи формул используют понятия “свободных” и “связных” переменных-кортежей, что определяется характером использования кванторов – логических операторов, переводящих одну высказывательную форму об отношении в другую. Различают кванторы общности – “все”, “всякий” и т. п. и существования – “некоторые”, “хотя бы один” и т. п. Переменная-кортеж в формуле является связанной, если ей предшествует квантор общности или существования по этой же переменной. В противном случае имеем свободную переменную – кортеж. Наличие связанной переменной формирует класс разрешённых формул. Формулы исчисления с переменными-кортежами могут быть построены из атомов рекурсивно: 1) всякий атом есть формула, т. е. F; 2) если F1 и F2 – формулы, то (F 1), (F1  F 2), (F1 & F 2) также формулы; 3) если x – переменный кортеж, F – формула, включающая x, то x(F) и x(F) также формулы; 4) никаких других формул нет. Итак {t’|F(t)} есть выражение РИ с переменными-кортежами, где t – единственная свободная переменная-кортеж в F(t). 30. Реляционное исчисление (РИ) на доменах. РИ на доменах строится на тех же операторах, что и РИ с переменными-кортежами (см. вопрос 2 9). Однако в этом исчислении не существует переменных-кортежей, а существуют переменные на доменах, которые являются лишь компонентами кортежей. Для обозначения переменных на доменах используем символы x и y, а для обозначения постоянных – kdi. Атом имеет вид: 1) если r – отношение со схемой Sch(r) = (I1, I2, … In), то r(x1, x2, … xn) – атом, где каждая Xi есть постоянная или переменная на доменах. 2) если x и y – переменные на доменах, v  θ – арифметический оператор (знак сравнения), то (x v y), (x v kdi), (kdi v y) – атомы; 3) никаких других атомов нет. r(x1, x2, … xn) указывает на то, что значения тех xi, которые являются переменными на доменах, должны быть выбраны так, чтобы был кортежем отношения r, а смысл атома (x v y) заключался в том, что x и y представляют собой значения, при которых (x v y) истинно. В записи формул также используют понятия “свободных” и “связных” переменных при использовании логических операторов – кванторов, переводящих одну высказывательную форму в другую. Правила для определения свободных и связанных переменных остаются теми же, что в исчислении переменных-кортежей. Формулы РИ с переменными на доменах могут быть построены из атомов рекурсивно: 1) всякий атом есть формула F; 2) если F1 и F2 – формулы, то (F 1), (F1  F 2), (F1 & F 2) также формулы; 3) если x – переменный на доменах, F – формула, включающая x, а I – атрибут из U, то F(x(I)) также формула; 4) никаких других формул нет. Разрешённые формулы РИ на доменах требуют, чтобы переменная, связываемая квантором, входила свободно в формулу, следующую за квантором. Выражения РИ переменных на доменах имеет вид:{|F(x1, x2, … xn)},где F(…) – разрешённая формула;xi – свободные переменные, входящие в F(…);I1, I2, … In – атрибуты из U. 3 1) Грамматика формального языка БНФ. Для строгого и точного описания синтаксиса языка удобно использовать какой-либо метаязык. Наиболее распространенным среди них является язык формул Бэкуса-Наура (язык БНФ или Бэкуса нормальная форма). На языке БНФ синтаксис языка описывается в виде некоторых формул, весьма похожих на обычные математические формулы. Введем условные обозначения: ::= - знак о том, что выражение, стоящее слева, может быть замещено выражением, стоящим справа ( ". . . состоит из. . . ");< . . > - синтаксическая переменная языка; " . . " - слово (лексема) языка <. . ><. . >. . - соединение синтаксических переменных союзом "и";<. . > | <. . >l . . - разделение синтаксических переменных разделителем "или"; " . . " <. . >. . I <. . > ". . ". . - соединение синтаксических переменных и лексем союзом "и" и разделение выражений и/или предложений языка разделителем "или"; " . . " " . . " . . - соединение лексем союзом "и" ". . " | ". . " | . . - разделение лексем разделителем "или";{ . . } - многократное повторение выражения, заключенного в фигурные скобки, включая нуль раз;[ . . . ] - одно- или нулькратное повторение выражения, заключенного в прямоугольные скобки. Тогда основная формула БНФ может быть представлена в виде X ::= Y1 | Y2 | Y3 |. . .,где X – выражение, определяемое только синтаксической переменной;Yi – выражение, определяемое набором синтаксических переменных и/или лексем, где I = 1, 2, 3, . . . При подстановке вместо X выражений Yi осуществляется вывод синтаксически правильной конструкции выражения или предложения, описываемого синтаксической переменной X. Следует обратить внимание, что в левой части каждого правила находится только одна синтаксическая переменная, а в правой выражение, включающее цепочки синтаксических переменных либо наборы лексем естественного языка. Знак "|" в правой части правил показывает возможность выбора значения синтаксической переменной, указанной в левой части.