Введение в системы БД (542480), страница 229
Текст из файла (страница 229)
Какие свойства должен иметь тип, чтобы он был допустимым как точечный тип? Прежде всего, нам известно, что интервал обозначается своими начальной и конечной точками и содержит, по крайней мере неформально, множество точек. Если можно определить полное множество точек, задав просто начальную точку е и конечную точку е, необходимо, чтобы можно было определить точку, которая непосредственно следует (в некотором установленном порядке) за точкой я. Такую непосредственно следующую точку называют наследником или преемником точки е. Условимся для простоты, что в качестве обозначения такой точки будет использоваться выражение е+1. Тогда функция, с помошью которой определяется точка е+1 по точке е, называется функцией следования для данного точечного типа (и точности).
Функция следования должна быть определена для каждого значения точечного типа, за исключением точки, определенной как "последняя". (Имеется и точка, определяемая как "первая", которая не является следуюшей за какой-либо точкой.) В7О Часть )'. Дополнительные аспекты Если точка яв1 определена как следующая за точкой я, необходимо установить, не следует ли точка я+1 за точкой е, в соответствии с тем же принятым порядком следования для точечного типа. Если это не так, точка я+1 действительно принадлежит интервалу ( я, е) и нужно переходить к следующей точке я+2. Этот процесс мы можем продолжать до тех пор, пока не перейдем к первой точке явл, которая следует за точкой е.
В результате такого прохода будут перебраны все точки интервала [ я, е]. Поскольку точка я+л фактически является преемником точки е, т.е. в действительное~и непосредственно следует за точкой е, можно утверждать, что единственное свойство, согласно которому тип РТ должен быть допустимым как точечный тип, равносильно тому, что для него должна быть определена функция следования. Короче говоря, должно быть установлено общее упорядочение для значений типа РТ (поэтому можно считать, что для всех пар значений РТ определены и доступны обычные операторы сравнения "<", ">" и т.д.). Кстати, вы, наверное, уже заметили, что хронологические данные больше конкретно не упоминаются.
И в оставшейся части главы речь также будет идти, в основном, об интервалах вообще, а не о конкретно хронологических интервалах, хотя в разделе 22.11 будут рассмотрены и конкретные вопросы, касающиеся именно хронологических данных. Дадим, наконец, точное определение. ° Пусть РТ вЂ” точечный тип. Тогда интервал (или значение интервала) 1 типа 1УТЕКЧЩРТ) — это скалярное значение, для которого определены два унарных оператора (ЯТаКТ и ЕМ0) и один бинарный оператор (1К), такие, что а) ЯТаКТ(1) и ЕК0(1) возвращают значения типа РТ; б) ЯТйКТ(1) < ЕК0(1); в) пусть р — некоторое значение типа РТ', тогда р 1Ы 1 истинно, если оба сравнения, ЯТАКТ(1) < р и р < ЕН0(1), дают в результате значения истина. Обратите внимание на обращение в этом определении к некоторой функции следования для типа РТ.
Также отметим, что начальная и конечная точки составляют возиолсное представление (в смысле главы 5) для значений типа ?КТЕКЧЬЬ(РТ) соответственно (поэтому в языке Твгог(а! В можно было бы обращаться к точкам ЯТАКТ и ЕН0 как ТНЕ ЯТаКТ и ТНЕ ЕМ0). И наконец заметим, что по определению интервалы всегда непустые, т.е. в любом заданном интервале всегда имеется по крайней мере одна точка. Следует подчеркнуть, что значение типа 1КТЕКЧКБ( РТ) является скалярным, т.е, оно не имеет компонентов, которые видны пользователю.
Действительно, оно имеет некоторое возможное представление (на самом деле даже несколько возможных представлений, как мы убедились в предыдущем разделе), и эти возможные представления имеют видимые для пользователя компоненты, но само значение интервала таких видимых компонентов не имеет. Иначе говоря, это означает, что интервалы инкапсулированы. 22.6. Скалярные операторы для интервалов В этом разделе будут определены некоторые полезные операторы, применяемые к значениям интервалов. Большинство из этих операторов более или менее понятны без дополнительных объяснений.
Рассмотрим интервальный тип 1КТЕКЧЫ(РТ). Пусть р бу- 871 Глава 22. Хронологические базы данньп дет значением типа РТ. Обозначения р+1, р+2 и т.д. по-прежнему будут использоваться для указания преемника р, преемника р+1 и т.д, В реальном языке для получения следующего значения может применяться некоторый оператор НЕХТ. Также будут использоваться обозначения р-1, р-2 и т.д. для указания значений, преемниками которых являются р, р-1 и тш. В реальном языке для получения предыдущего значения может использоваться некоторый оператор РВ1ОВ. Пусть р1 и р2 — значения типа РТ.
Определим оператор МАХ(р1,р2) как оператор, возвращающий значение р2, если р1<р2, и значение р1 в противном случае. Оператор И1Н(р),р2) возвращает значение р1, если р1<р2, и значение р2 в противном случае. Обозначения, которые использовались до сих пор, применялись лля операций интервальных выборок, по крайней мере в неформальном контексте. Например, в результате обращения к выборке интервалов [ 3, 5) и [ 3, б ) получим значения типа 1МТЕВЧАЬ(1НТЕОЕВ), которые будут содержать точки 3, 4 и 5.
В реальном языке может потребоваться явный синтаксис, например 1НТЕВЧАЬ( [3,5] ). Пусть 1! будет интервалом [в1, е1] типа 1НТЕВЧАЬ[РТ). Как указывалось выше, оператор ЯТАВТ(11) возвращает значение в1, а оператор ЕНО(11) — значение е1. Кроме того, определим оператор ЯТОР(11), который возвращает значение е1в1. Также обозначим через 12 еще один интервал [в2,е2) типа 1НТЕВЧАЬ(РТ).
Теперь дадим определение операторов сравнения интервалов. Замечание. Эти операторы также называются операторами Аллена, по имени автора [АПеп), впервые их предложившего [22.1]. В качестве упражнения можно попытаться начертить простые схемы, которые иллюстрируют эти операторы. ° Оператор сравнения 11=12 возвращает значение истина тогда и только тогда, когда в1ия2 и е1ве2. ° Оператор предшествования интервала 11 ВЕРОНЕ 12 возвращает значение истина тогда и только тогда, когда е1<в2. ° Оператор смежности интервалов 11 МЕЕТЯ 12 возвращает значение истина тогда и только тогда, когда в2ве1+1 или в1ие2+1. ° Оператор перекрытия интервалов 11 ОУЕВЬАРЯ 12 возвращает значение истина тогда и только тогда, когда в1<е2 и в2<е1. ° Оператор вхождения интервала 11 00В1НО 12 возвращает значение истина тогда и только тогда, когда в2<в1 и е2>е1з.
° Оператор начального интервала 11 БТАВТЯ 12 возвращает значение истина тогда и только тогда, когла в1=в2 и е1<е2. ° Оператор конечного интервала 1! Р1Н1ЯНЕБ 12 возвращает значение истина тогда и только тогда, когда е1=е2 и в1>в2. Замечание. Определения этих операторов иначе можно представить в терминах точек [соответствующего точечного типа). Например, можно сказать, что оператор 11 ОЧЕВЬАРЯ 12 возвращает значение истина тогда и только тогда, когда существует значение р типа РТ, такое, что оба выражения, р 1Н 11 и р 1М 12, истинны.
" В виде исключения в данном случае все >ге заметюи, что название оператора ОУЛ1ИО (в течение) здесь не подразумевает "в течение всего интервала времени ". 872 Часть ]г. дополнительные аспекты Следуя [22.3], можно также определить дополнительные операторы. ° Оператор слияния интервалов 11 МЕЕОЕЯ 12 возвращает значение истина тогда и только тогда, когда один из операторов, 11 МЕЕТЯ 12 или 11 0ЧЕЕ[дхРЯ 12, возвращает значение истина.
° Оператор содержания интервала 11 СОМТй1МЯ 12 возвращает значение истина тогда и только тогда, когда оператор 12 00Е1М6 11 возвращает значение истиназ. Чтобы получить длину (если можно так выразиться) интервала, используют оператор 00ЕАТ10М(1), который возвращает количество точек в интервале 1, например 00ййТ10М( [с[03,с[07] ) = 5. И ь аконец определим некоторые бинарные операторы для интервалов, которые возвращают интервалы. ° Результатом выполнения оператора объединения интервалов 11 УМ10М 12 является интервал [М1М(в1,а2),МАХ(е1,е2) ], если оператор 11 МЕМОЕЯ 12 возвращает значение истина; в противном случае операция объединения не определена. ° Результатом выполнения оператора пересечения интервалов 11 1МТЕКЯЕСТ 12 является интервал [МИ( а1, в2),М1М(е1,е2) ], если оператор 11 ОЧЕРЗАРЯ 12 возвращает значение истина; в противном случае операция пересечения не определена.
Замечание. Здесь операторы УМ10М и 1МТЕЕЯЕСТ представляют собой обычные операторы обработки множеств и не являются их специальными реляционными аналогами. В статье [22.3] они называются соответственно ЕМКОЕ и 1МТЕМЧЯЕСТ. 22.7.
Операторы обобщения для интервалов В этом разделе будут рассмотрены два чрезвычайно важных оператора: УБРОМ (развернуть) и СольЕБСЕ (свернуть). Они обрабатывают множество интервальных значений того же типа, что и их собственный операнд, и возвращают другое такое множество. Результат в обоих случаях можно рассматривать как определенную каноническую форму для исходного множества (о канонической форме читайте в разделе 17.3 главы ! 7).
Дальнейшее обсуждение будет основываться на следующих исходных данных. Пусть Х1 и Х2 представляют собой лва показанных ниже множества соответственно. ( [601,601], [003,с[05], [с[04,006] ) ( [001,с[01], [с[03,сй04], [605,х]05], [605,000] ) Нетрудно заметить, что Х1 и К2 — это не одно и то же множество. Почти так же легко заметить, что множество всех точек р, таких, которые содержатся в некотором интервале в Х1, то же самое, что и множество всех точек р, таких, которые содержатся в некотором интервале в Х2.
В это множество включены точки б01, бОЗ, б04, с(05 и бОб. Однако по соображениям, которые вскоре станут понятными, нас не так интересует множество самих точек, как соответствующее множество еднннчнык интервалов. Назовем его ХЗ. Е Возможно, в этом случае более подходящим названием оператора было бы 1ИСЬУОЕБ (вкхючает1, тогда можно было бы использовать ключеаое слово СО!ЕТА1!ЕБ (содержит! длл оператора, обратного оператору 1д( определив его как 1 СО!ЕТАЕ!чв р, что равносильно р 1!ч 1. 873 Глава 22. Хронологические базы данных ( [с)01,с)01), [с[0З,с)0З), [004,004), [005,г)05[, [004,004) ) Говорят, что интервал ХЗ вЂ” зто развернутая форма интервала Х1 (и Х2).
В общем случае, если К является множеством интервалов и все они имеют олин и тот же тип, развернутая форма множества Х вЂ” это множество всех интервалов вида [р, р), где р— точка в некотором интервале из множества Х. Отметим, что множества Х1, Х2 и ХЗ имеют разную кардинальность, т.е. отличаются количеством элементов. В нашем примере получилось так, что множество ХЗ, т.е. развернутая форма, имеет наибольшую кардинальность среди всех трех множеств примера. Но можно легко найти такое множество Х4, которое имеет ту же развернутую форму, что и множество Х1, но кардинальность которого больше кардннальностн множества ХЗ (упражнение лля читателя). Также легко можно найти более интересное, и единственное, множество Х5, которое имеет ту же развернутую форму, но минииально возможную карлинальность.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
