Свойства коллекций
Материал из КинтВики
|
Терминология
Понятия "коллекция", "отношение", "выражение" считаются эквивалентными. Понятие "выражение" обычно используется там, где подчеркивается "алгебраичность" коллекции. Понятие "отношение" используется, если размерность коллекции больше 1.
Амплитуды
На пространстве значений алфавита можно определять коллекции (подмножества, домены), состоящие из элементов (значений) алфавита. Например, для алфавита
Alph = (a1, a2, a3)
можно задать следующие коллекции:
SubSetOfA12 = (a1, a2) SubSetOfA23 = (a2, a3) (1) SubSetOfA13 = (a1, a3) и т.д.
Свойства коллекций отличаются от свойств алфавита. Например, сложение SubSetOfA12 и SubSetOfA21 дает:
SetOfA = SubSetOfA12 + SubSetOfA21 = (a1, a2, a2, a3) = (a1, 2 a2, a3) (2)
Числовые коэффициенты перед элементами коллекции называются амплитудами. В коллекции SetOfA амплитуда элемента a2 равна 2. В табличной форме SetOfA для амплитуд выделяется отдельное поле:
<SetOfA> {
<Элемент | Амплитуда> {
a1 | 1,
a2 | 2,
a3 | 1
}
}
Отношение <SetOfA> удовлетворяет свойствам реляционного отношения,- все кортежи являются уникальными.
В общем виде одномерные коллекции (множества) значений, построенные на алфавите Alph, можно представить в следующей форме:
SetOfA(k) = k1*a1, k2*a2, k3*a3; (3)
Здесь k1, k2, k3 - амплитуды (коэффициенты) разложения коллекции (отношения) SetOfA(k) на алфавите Alph.
В информационных системах в основном используются целочисленные амплитуды элементов (1 и -1), но допустим любой числовой тип (в квантовой механике амплитудами состояний являются комплексные числа). Поскольку амплитуды всех кортежей принадлежат одному и тому же типу, то в операциях сложения и произведения отношений амплитуды подчиняются обычным арифметическим законам (сложения и умножения). То есть произведение двух амплитуд - это тоже число.
Кортежи, размерность коллекций
Элементы (как одного алфавита, так и разных) могут связываться, образуя кортеж. Операция связывания выражается через произведение (сцепление) элементов:
Кортеж = a1.b1.
Элементы в кортеже упорядочены, - их нельзя менять местами.
Количество элементов в "связке" определяет размерность кортежа. Совокупность кортежей одинаковой размерности образует коллекции. Например, в следующей коллекции кортежи имеют размерность 2:
SetOfAB = (a1.b1, a2.b1, a3.b2, a2.b2) (4)
Каждая пара элементов - это отдельный кортеж.
Сетевые множества - иерархии, графы
В традиционном (табличном) отношении размерность кортежей одна и та же для всего отношения. В общем случае (иерархия, дерево, сеть) размерность кортежей одного отношения может быть переменной:
Hie = (a1, a1.a11, a1.a12, a1.a11.a111, ...) (5)
Выражение (5) представляет собой отношение иерархии. Все элементы кортежа должны принадлежать одному общему алфавиту - быть однородными.
Под размерностью сетевого множества можно понимать максимальную размерность кортежа такого множества.
Нормальная форма реляционного выражения
В нормальной форме выражение представляется как сумма кортежей (дизъюнкция конъюнкций). При этом значения кортежей должны быть различными,- то есть выполнена свертка кортежей.
Пример нормальной формы коллекции - формула (4).
Эквивалентное выражение по значению SetOfAB
SetOfAB' = (a1.b1, 2*a2.b1, -a2.b1, a3.b2, a2.b2) (4')
условиям нормальности не удовлетворяет, поскольку содержит два одинаковых слагаемых (a2.b1) с разными амплитудами (2 и -1):
Любая коллекция (выражение, отношение) имеет единственную нормальную форму и всегда может быть приведено к нормальной форме.
Понятие мощности кортежа и коллекции
Для вычисления мощности произвольного реляционного выражения (коллекции) его необходимо привести к нормальной форме.
Если в коллекции амплитуды элементов отличны от 1, то представление коллекции как набора элементов не всегда имеет смысл. Правильнее представлять такие коллекции как функции - совокупность неких состояний (кортежей), каждое из которых имеет определенный вес (амплитуду).
Мощность кортежа определяется как квадрат его амплитуды (коэффициента). Например, мощность элемента a1 в коллекции SetOfA (3) равна k1*k1.
Мощность всей коллекции равна сумме мощности кортежей. Для множества SetOfA (3) имеем:
P(SetOfA) = k1^2 + k2^2 + k3^2. (6)
 |
Мощности (квадрат амплитуды) кортежей в диапазоне [0; 1] могут отражать степень связанности элементов. Такое представление позволяет реализовать нечеткую логику. |
Пространство представления отношения
Если размерность кортежей отношения больше единицы, то отношение может быть представлено в различных пространствах. Любое отношение может быть представлено в заданном пространстве как сумма базовых элементов (векторов) с определенными значениями коэффициентов.
Пространство представления отношения - это алфавит, который определяет базовые элементы (векторы) отношения.
Например, для отношения SetOfAB (4) можно указать следующие потенциальные пространства:
- пространство элементов ai (алфавит A),
- пространство элементов bj (алфавит B),
- пространство кортежей (ai.bj) (алфавит A.B).
Определение пространства коллекции позволяет указать, какие элементы отношения играют роль базовых векторов (алфавита), а какие - коэффициентов перед векторами.
Собственное пространство
Одно и то же отношение может быть выражено в разных пространствах, но некоторые пространства являются выделенными. Введем понятие собственное пространство отношения. Собственное пространство отношения обладает следующим свойством: свертка нормальной формы отношения по векторам собственного пространства не меняет форму отношения. То есть в собственном пространстве нормальная форма является устойчивой к операции свертки.
Для одного и того же отношения может быть определено несколько собственных пространств. Собственное пространство минимальной размерности является ключом отношения.
Собственное пространство двумерного отношения SetOfAB (4) также является двумерным и определяется произведением атрибутов (A.B). Но часто размерность собственного пространства меньше размерности всего отношения. Например, в отношении SetOfA_b (4") собственное пространство одномерно (значения атрибута A):
SetOfA_b = (a1.b1, a2.b1, a3.b2, a4.b2) (4")
Сворачивая нормальную форму (4") в пространстве "A", мы получаем ту же самую форму. Но в пространстве "B" коэффициенты при базовых векторах (b1 и b2) не удовлетворяют свойствам нормализованного отношения (представляют собой сумму элементов a).
SetOfA_b = ((a1+a2).b1, (a3+a4).b2)
В иерархическом (и сетевом) выражении также могут быть выделены элементы пространства и элементы коэффициентов (k):
HieSet = (k1*a1, k11*a1.a11, k12*a1.a12, k111*a1.a11.a111, ...)
Пример определения пространств представления отношения
Рассмотрим отношение, отражающее цвет фигуры, в котором у фигуры может быть один только цвет (амплитуды всех кортежей - единица):
<Цвет фигур> {
< Фигура . Цвет > {
Квадрат . Красный,
Круг . Синий,
Эллипс . Красный,
Ромб . Желтый,
}
}
Собственным пространством данного отношения являются значения атрибута <Фигура>. Соответственно, атрибут <Цвет> отражает собой значения коэффициентов при базовых векторах. Амплитуды в данном отношении равны 1.
<Цвет фигур> {Квадрат.Красный, Круг.Синий, Эллипс.Красный, Ромб.Желтый};
Данная форма является нормальной формой отношения.
Но можно выбрать в качестве пространства значения атрибута <Цвет>. Тогда форма отношения примет ненормализованный вид:
<Цвет фигур> {Красный.(Квадрат + Эллипс), Синий.Круг, Желтый.Ромб};
|
Приведение выражения к определенному пространству представления используется при операциях между выражениями. Операции имеют смысл только между выражениями, приведенными к одному пространству. |
