Рис. 4.26. Мультимножество

4.6.1 Причины использования мультимножеств

Анализ вопросов эффективной реализации отношений показывает, что использование мультимножеств может увеличить скорость операций на отношениях. Например, еслн мультимножество допускается в качестве результата проекции, с каждым кортежем можно работать независимо. Если же результатом является множество, необходимо сравнивать результат проекции из нежелательных компонентов каждого кортежа с результатом проецирования всех остальных кортежей, чтобы убедиться в том, что такая проекция ранее не встречалась. Если же результатом является мультимножество, мы просто проецируем каждый кортеж и добавляем его к результату; при этом не требуется никакого сравнения проецированных кортежей.

! Нпражнеиие 4.5.4. Пусть R п S-отношения, а С- ограниче1гне ссылочной аелостности, согласно которому, если R содержит кортеж со значениями v vj,v в отдельных атрибутах /1 Ai, .... /4, то в должен быть кортеж, имеющий те же значении v \ч. v в отдельных атрибутах Bi, В . Выразите ограничение С в реляционной алгебре.

1\ Упрожнение 4.5.5. Пусть R - отношение, и функциональная зависимость /) .4,... А В включает в себя атрибуты R. Выразите в реляционной алгебре ограничение, согласно которому эта функциональная зависимость должна быть истинной в R.

4.6 Реляционные операции на мультимножествах

Несмотря иа то что множество кортежей (т.е. отношение) является простой моделью данных в том их виде, в каком они могут входить в БД. коммерческие системы БД редко (и вртд ли когда-либо вообще) строятся исключительно на основе множеств. В некоторых ситуациях допускается, что отношения, входящие в систему БД, содержат дублирующиеся кортежи. Напоминаем, что .множество , содержащее несколько вхождений какого-либо своего элемента, нйъыъгеуса мультимножеством. В этом разделе рассматриваются отношения, являющиеся мультимножествами, а не множествами, т.е. один и тот же кортеж может входить в одно и то же отношение несколько раз. Термином множество обозначается отношение без повторяющихся кортежей, а термином мультимножество - отношение, содержащее (или не содержащее) повторяющиеся кортежи.

Пример 4.47. Огнон;енне на рис. 4,28 -это мультимножество кортежей, в которое кортеж (1,2) вхо,аит трижды, а кортеж (3, 4) один раз. Если бы оно было основано на множестве, iiyroio бьшо бы удалить из него два вхождения кортежа (1,2). В отношении, основанном на мультимножестве, действительно допустимо повторение вхождений некоторого кортежа, но. как и во множествах, порядок кортежей не имеет значения. □

Рис. 4.29, ЛЛупьтидлножесгво для примеро 4.48

Пример 4.48. Мультимножество, изображенное на рис. 4.28, может быть результатом проекции отношения из рис. 4.29 на атрибуты А w В при условии, что результат -это мультимножество. Если же применить обычный оператор проекции реляционной алгебры, а значит, удалить дубликаты кортежей, получается только отношение

Результат в виде мультимножества по размеру больше этого отношения, котя вычисляется бысгрее, так как необязательно сравнивать каждый кортеж (!,2) или (1,3) с построенными ранее кортежами.

Более того, если проекция отношения применяется для получения статистического значения (как было показано в разделе 5.5) типа среднего значения А в отношении, показанном на рис. 4.29, для анализа проецированного отношения нельзя применять модель множества. Для множества среднее значение А равно 2. так как А имеет только два раз.чичных значения: 1 и 3, средним значением которых является 2. Если же этот столбец на рис. 4.29 считается мультимножеством {1, 3, 1, ]}, получается правильное среднее значение А для четырех кортежей - 1,5. □

Когда результатом является мультимножество, можно сэкономить время и при вычислении объединения отношений. Если в результате вычисления R\jSдолжно получитызя множество, необходимо проверять, является ли каждый кортеж из S членом R. Если он входит в R, то он не вносится в объединение, если не входит в Л, вносится в объединение. А при допущении мультимножества в качестве результата его можно получить, просто копируя все кортежи из Л и 5 независимо от того, входят ли они одновременно в оба отношения.

4.6.2 Объединение, пересечение и разность мультимножеств

При объединении двух мультимножеств берстся сумма вхождений каждого из кортежей. То есть, если Л - мультимножество, в которое кортеж t входит п раз, а S мультимножество, в которое кортеж / входит от раз, в мультимножество Л и .S кортеж t входит л и раз. При этом пит порознь или одновременно могут равняться 0.

При пересечении мультимножеств R v S, в которые кортеж / входит п к т раз соответственно, в RrxS кортеж г входит min( , т) раз. При вычислении разности R~Sмультимножеств Rv\ Sкортеж входит ъ R S тах(0, л - от) раз. То есть, если в R вхожаений / больше, чем в то число вхождений 1в R-S равно числу вхождений f в R минус число вхождений Тв S. Если же число вхождений / в .S не меньше числа вхождений if в Л, то f вообще не входит в R S. С интуитивной точки зрения каждое вхождение / в S аннулирует одно вхождение в R.

Мультимноэкественные операции на множествах

Представьте себе два множества - R и S. Любое множество может мыслиться как мультимножество, в котором случайно оказалось только по одному вхождению каждого элемента. Пусть выполняется пересечение RrS, но R н S считаются мультимножествами и применяется правило пересечения мультимножеств. Результат получается такой же, как и тогда, когда R \л S являются множествами. То есть, еслн R \к S мыслятся как мультимножества, число вхождений кортежа / в Лп 5 равно минимальному из чисел его в.хождений в Л и pS. Поскольку R и S на самом деле множества, / может входить в каждое из них только О или I раз. Независимо от того, применяются ли правила пересечения множеств или мультимножеств, оказывается, гго / может входить в Лп 5 не более одного раза и ходит в пересечение именно один раз, когда он входит и в Л, и в Л! Применение правила разности мультимножеств Л- ?или J - Л тоже лает точно такой же результат, как и применение правила разности множеств.

Однако объединение ведет себя ио-разному в зависимости стг того, считаются ли Л и S множсстаами или мульти.множествами. Если для вычисления объединения R\jS применяется правило для мультимножеств, результат может не бьп-ь множеством, даже еслн Я и 5- множества. В частности, если кортеж t входит в Я и Л, то он входит в Л.j дважды, когда Л и 5- мультимножества. Если же применяется операция над множествами, / входит ъ Ru S только один раз. Отсюда следует вывод: производя объединение, внимательно следите за тем, что именно объединяется - множества или мультимножества.

Пример 4.49. Пусть Л-отношение, изображенное на рис 4.28, т.е. мультимножество, в которое кортеж (1,2) входит трижды, а кортеж (3,4) один раз. Пусть .S-мультимножество:

1 2

Тогда Rkj S-это мультимножество, в которое (1, 2) входит четыре раза (три вхождения из R и одно вхождение нз 5). (3. 4) входит ipn раза и (5, 6) один раз. Пересечение это мультимножество:

А \ В

3 4

В которое (1,2) и (3, 4) входят по одному разу. То есть. (1.2) входит трижды в Л и один раз в 5, а min(3, 1)= 1, значит, (1,2) входит в RriS только один раз. Аналогачно. (3.4) в.\-однт в RrS {\,2)= 1 раз. Кор1х;ж (5,6) входящий один раз в J и не входящий в R, в.ходит min(0, 1) = О раз в Rr.S.