Оптимизация запросов в системах баз данных

       

Реляционное исчисление


(Кортежное) реляционное исчисление, как оно было введено Коддом [Codd 1971, 1972], - это нотация для определения результата запроса через описание его свойств. Представление запроса в реляционном исчислении состоит из двух частей: целевой список (target list) и выражение выборки (selection expression).

Выражение выборки специфицирует содержимое отношения, происходящего в результате выполнения запроса, средствами предикатов первого порядка (т.е. обобщенных булевских выражений, возможно, содержащих кванторы существования и всеобщности). В целевом списке определяются свободные переменные, встречающиеся в предикате, и специфицируется структура результирующего отношения. В Примере 2.1 демонстрируется представление реляционного исчисления с использованием синтаксиса языка программирования баз данных Pascal/R [Schmidt 1977].

Пример 2.1. Имена профессоров, опубликовавших какую-либо статью в 1981 г.

[<e.ename> OF EACH e IN employees: e.status = professor AND SOME p IN papers (e.enr = p.enr AND p.year = 1981)]

В целевом списке, т.е. подвыражении, предшествующем двоеточию, область определения (свободной) переменной e ограничивается элементами отношения "employees". Поэтому отношение "employees" называется отношением области определения (range relation) переменной e. Спецификация атрибута цели "<e.ename>" показывает, что в результате запроса останутся только имена служащих.

Выражение выборки - предикат, следующий за двоеточием - определяет ограничения на свободную переменную. Первое ограничение является ограничивающим, или одноместным термом (monadic term), ограничивающим свободную переменную теми записями "employees", значением столбца status которых является значение "professor". Это ограничение связывается через AND с соединительным, или

двуместным термом (dyadic term), связывающим "employees" с "papers", и еще одним одноместным термом, еще более ограничивающим результат теми служащими, которые опубликовали какую-либо статью в 1981 г.
Обычно допускаемыми в термах операциями сравнения являются =, `, <, >, d и e.

В отличие от односортового исчисления предикатов, в реляционном исчислении разрешаются переменные, привязанные к разным сортам (отношениям области определения); например, переменная e связана с "employees", а переменная p - с "papers". Последствия многосортовости реляционного исчисления в отношение преобразования запрсов обсуждаются в разд. 3.1.

Кроме логической операции AND, в предикатах могут использоваться и операции OR и NOT. Предикаты реляционного исчисления полностью определяются следующими рекурсивными правилами:

  • Атомарные предикаты:

  • (Одноместный или двуместный) терм является атомарным предикатом.


  • TRUE является атомарным предикатом.


  • FALSE является атомарным предикатом.

  • Атомарный предикат является предикатом. Пусть A - предикат, r - переменная элемента, и rel - отношение. Тогда

  • SOME r IN rel(A),


  • ALL r IN rel(A)

    также являются предикатами.

  • Пусть A и B - предикаты. Тогда

  • NOT (A) (отрицание),


  • A AND B (конъюнкция),


  • A OR B (дизъюнкция)

    являются предикатами.

  • Никакие другие формулы предикатами не являются.


  • Реляционное исчисление было введено в [Codd 1972] как мерило реляционной мощности. Форма представления называется реляционно полной, если в ней допускается определение результата любого запроса, определяемого выражением реляционного исчисления. Ясно, что реляционная полнота должна рассматриваться как минимальное требование в отношении выразительной мощности. Часто приводимым примером концептуально простого запроса, выходящим за пределы реляционной полноты, является запрос "найти имена служащих, отчитывающихся перед менеджером Смитом на любом уровне", предусматривающий, что в одном отношении моделируется иерархия служащий (через атрибуты name и manager) [Pirotte 1979]. Кроме того, запросы в сегодняшних приложениях часто содержат агрегации, которые неаозможно выразить в чистом реляционном исчислении. Однако реляционное исчисление довольно легко расширяется агрегатными функциями [Klug 1982b; Maier and Warren 1981].


    Содержание раздела







    Forekc.ru
    Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий