Кук Д., Бейз Г. - Компьютерная математика, страница 9

Проверку этого утверя<дения оставляем в качестве упражвепня. Наконец, определяя отношение порядка на мпоясестве действительных чисел К. Рассмотрим десятичные представления двух действительных полон|игольных чисел: П ... ОИ» ° ° ° г(г~(1г(обМг .. » С ... Ос,... сгс,со'(1'(г 51 Если 4 е, и 6< т, для всех 1, то Р С и, следовательно, Р<С и С~Р. В противном случае: а) если а„чл0, с ч" 0 и ивы, то Р < С, если и < ж, и С <Р, если пг<п; б) если и т и с) чьсч но 4=с~ для всех 1 таких, что 1<1а=п, то из А< с, следует, что Р< С, и, обратно, если с» < ач то С Р; в) если т и и 4 с, для всех 1, но 6, чь т, для некоторых й и б,=ъ для всех 1 таких, что 0 <1< й, тогда С <Р, если Т,<б„и Р < С, если 6,< ц„.

Читатель может проверить зто самостоятельно. Отрицательные числа могут быть исследованы так же, как вЕ. г' Множество Х вместе с отношением порядка < называется частично упорядоченным множеством (обозначается (Х, <) ). Тогда любой злемент иы(Х, <) такой, что х< и и ус и, называется верхней границей х и у.

Аналогично, осли 1ы(Х, <), 1 < х и 1 < у, то 1 является нижней границей х и у. Множество всех верхних границ х и у является подмаолсеством Х и упорядочено отношевием а:. Если существует единственный наименьший элемент этого множества, т. е. если существует р ы ы(Х, ч ) такое, что хч р, у<у и р<и для любой верхней границы и, то р называют верхней гранью (зпр) х и у. Аналогична, если существует единственная наибольшая нижняя граница х и у, ее нааывают нижней вранью (ш1) х и у. Мы отложим изучение верхней и нижней граней до 2 5 гл.

5, где будут изучаться решетки. Наконец, заметим, что использование естественного порядка на К определяет новые множества, Их называют интервалами: [а, Ь] =(х: хыК, а<х~=Ы есть замкнутый интервал (отрегок) от а до Ь; ]а, Ь[ (х: хыК, а<х<Ы есть открытый интервал от а до Ь. В каждом случае числа а и Ь называются концевыми точками. Замкнутый интервал включает в себя концевые точки, а открытый нет. Удобно также определить полуоткрытые интервалы: [а, Ь[=(х: хыК, а<х< Ы, ]а, Ь] (х; хгиК, а<х<Ы.

52 Для удобства будем использовать следующие обозначения: ) —, а) (х: хна), 1 — ю, а[ (х: х<а), [а, [ (х: а<я), )а, со[ (х: а(х), ] — оо в[ Я. Хотя интервалы и множества чисел в общем-то не являются центральной частью нашего рассмотрения, мы увидим, что их удобно использовать время от времеви. У п р а ж н е я я е 2.5. 1. Пусть А — произвольное множество и р — отношение на множестве Р(А)ХУ(А), определенное следующим образом: (Р, ч)р(Х, У) тогда и только тогда, когда (Р~,О) и(ХйУ).

Является ли р отношением порядка) 2. Пусть А — произвольное множество и а — отношение на л. (А) Х а. (А), определенное следующим образом: (Р, Ч)о(Х, У) тогда и только тогда, когда Р Х Е У. Является ли и отношением порядка) Если да, то является ли зтот порядок полным) 3. Пусть г и я — отношения на №, определяемые соотношениями: (а, Ь)т(с, Ы) тогда и только тогда, когда а<с и Ь И; (а, Ь)я(с, И) тогда н только тогда, когда а<с и Ь~д. Являются ли т и я отношениями порядка) 4. Пусть я определено на положительных злементах (1 следующим образом: (а(Ь)я(с, И) тогда и только тогда, когда а» Ы< Ь е с, Показать, что я является полным отношением порядка.

$ б. Отношении на базах данных и структурах данных Как уже установлено, все вокруг определяется отно- шениями. Достаточно лишь взять отношение з на пере- менных (хп ..., х„) так, чтобы можно было построить 63 множество ((хь хз ..., Х„): з(хи хэ, ° ° .> х») истинно). Пусть задан набор (хи ..., х„), Отношение з(хн ..., х„) можно разрви«ига т. е.

выяснить, в(х1, ..., х„) истинно или ложно. Конечно, в не обязательно будет представлено «хорошейэ формулой. Нетрудно показать, что вместо отношения з, определяющего множество наборов длины и, любое множество таких наборов таки«е определяет отношение (и содержательные свойства з). Эти два подхода эквивалентны.

Определение, При обработке данных наборы из и элементов называют записями; элементы этих наборов называют полями. Записи, определяющие отношение, обычно содержатся в файле. Если потребовать, чтобы несколько файлов содержали совокупность записей, удовлетворяющих некоторым отношениям, то мы получим (относительную) базу данн«зх. Замечание. Для случая обработки данных мы сейчас употребили термин «полез.

В гл. 5 мы будем употреблять этот термин в математическом смысле, однако в данном случае это ке приводит к недорааумению. Таким образом, это дает нам первый реальный пример отношений, которые в большей мере связаны с вычислениями, в частности, с прикладными эадачамв. Тем не менее краткое обсуждение некоторых простейших свойств баз данных не только обеспечивает основу дальнейшего математического исследования отношений, но в проясняет некоторые факторы, понимание которых необходимо для эффективного управления системами баз данных.

Современная теория баз данных включает в себя изучение так называемых нормальных форм, однако обоснование некоторых из пих очевидно лишь в простых случаях. Мы рассмотрим только три формы для следующих задач: — вставить новый набор пз н элементов; — удалить набор из и элементов; — модифицировать набор, содержащий и элементов. Начнем с простейшей нормальной формы, Определение. Файлы в первой нормальной форм« (ДАХР), или — болев просто — норма шзованныв файлы, имеют записи фцксированной длины, состоящие из элементов, взятых нз множеств, чьи элементы далее не могут быть разбиты, и в каждый момент времени этот 54 файл может быть представлен как массив значений МХУ. Каждая запись, будучи набором из л алементов, мовсет быть записана как строка массива.

У П р и и е р 6.1. Рассмотрим отношение РАМ1 (см. выше), в котором мы собрали вместе родителей и детей. Каждая аапись содержит в указанном порядке фамилию и имена отца, матери и детей. Следовательно, мы имеем записи (Смит, Джой, Джойс, (Салли, Бен))ж РАМ1, (Браун, Фред, Лиза, (Люси) ) ж РАМ1. Теперь, если мы обоаначнм через Р и М множества от- цов и матерей, то из определения следует, что Джой(Смит)а )г, Джойс(Смит)ж М, Фред(Браун) ж и", Лиза (Браун) ж йг. Таким образом, Люси является членом семин Браун, но Салли и Бея не являются детьми семьи Смит.

Таи как в атой семье более одного ребенка, то соответствующая запись больше, и, следовательно, нарушены условия пер- вой нормальной формы. Иэ гАМ1 мы можем получить отношение РАМ2, по- строив его иэ Я, )т, М и С, где Я вЂ” множество фамилий, а С вЂ” множество детей, путем конструирования записей: (Смит, Джой, Днсойс, Сэлли), (Смит, Джой, Джойс, Бен), (Браун, Фред, Лиза, Люси). Отношение ГАМ2 находится в 1ХР и может быть пред- ставлено при помощи табл. 2.1. Таблица йд лебезим Салли Бев Люси Джойс Джойс Лвиа Джой д й Фред Сват Смит Браун Однако не совсем ясно, что будет, если, например, супругн Джонс не имеют детеИ Если мы хотим иметь в файле запись о пих, то следует пересмотреть структуру файла.

Это означает, что все следует начать сначала. Введем следующую терминологию. 55 Определение. При использовании таблицы для изображения отношения (файла с и-мернымн наборамн/записнми, записываемыми в виде строк) столбцы называются атрибутами. У Следовательно, ФАМИЛИЯ, ОТЕЦ, МАТЬ и РЕБЕНОК являются атрибутами различных полей в РАМ2. Длн получения доступа к записям в файле используются так называемые ключи.

Болев точно это может быть определено в терминах атрибутов. О п р е д е л е н и е. Атрибут или (упорядоченное)' множество атрибутов, чьи значения однозначно определяют запись в файле, называются ключом этого файла. (Заметим, что в файле может быть много различных ключей.) е Каждый ключ отношения/файла РАМ2 должен включать атрибут РЕБЕНОК. Перейдем к другим примерам. П р и м е р 6.2. Каждый владелец компьютера должен покупать к нему запасные части.

Поэтому мы можем рассмотреть файл, структура которого показана в табл. 2.2. Таблица З.г компания отдклннин АСЕ 1ВЬ РАТАМЕТЕ РК!!ЧТАСО %00Ь1ЕЗ ВТХ ОХОВ ВАТА ЬОЕВОН ЬОЕВОМ В1Вм!!тбням МА!ЧСНЕЗТЕК В!ЕМ!ВОНАМ ЬОЕВОН ОХУОВВ ЗМ1ТН !ОНЕЗ УО!ЧЕЗ ВКО!и!Ч ВВОтт!ч ЗМ1ТН %1ЬЗОН Атрибут КОМПАНИЯ является ключом в Я1)Р1; вся другая информация в файле доступна при посредстве ключа. Таким образом, например, можно навлечь атрибут ОТДЕЛЕНИЕ при помощи ключа ттООЫЕВ или же МЕНЕДЖЕР иа БТХ. г Определение.