Iii республикалық студенттік ғылыми-практикалық конференциясының баяндамалар жинағЫ
жүктеу/скачать 13,94 Mb.
|
- Бұл бет үшін навигация:
- Строение алгебры функциональных данных
Литература Павлюк И.И. Карибаева Т.Н. о понятии группы и основных ее свойствах // Материалы международной научной конференции молодых ученых студентов “VII Сатпаевские чтения”. Павлодар.2007.С. 304-308. 2. Каргаполов М.И., Мерзляков Ю.И. Основы теории групп // М.:Наука 1982 г. 288с. УДК 517.51
Обозначим через Str (T) множество всех функциональных данных. B этом множестве имеется особый элемент — нигде не определенная функция, которая будет обозначаться символом . B Str(T) можно вести порядок, положив fg, если deff defg и f(A) = g(A) для любого А deff. Другими словами, fg, если g является продолжением функции f или, что то же самое f есть сужение g. Введенный порядок можно интерпретировать как отношение "большой информативности": так как g является продолжением f, то g сообщает" большой информации", чем f.
B алгебре Str(T) можно выполнять операций над данными. Однако сами элементы алгебры слишком "малы"; чтобы умножить данные f1, f2 , ..., fn на одно и то же согласование α или на одну и ту же переоценку , надо n раз указать операцию умножения. Одновременно над данными не определены теоретико-множественные операции, которые важны при информационном поиске. Поэтому целесообразно расширить алгебру Str(T). Обозначим через File (T) множество конечных подмножеств функциональных данных. Теоретико-множественные операции объединения, пересечения и разности превращают File(T) и дистрибутивную решетку с относительными дополнениями. Нулем служит пустое множество , а дополнением подмножества R1 до R служит разность R\R1. Элементы множества File (T) назовем файлами. Пусть R = { f1, f2 , ..., fn } File (T). Через at(R) обозначим объединение областей определения функциональных данных из R, т.е. at (R) Положим теперь по определению R {f1| f1R}, End (N), R {f1| f1R}, Ev(V) B частности, если R = ф, то ф = ф = ф для любых и . Эти определение распространяют умножение, введенное для согласований, функциональных данных и переоценок, на множества функциональных данных. Выполняются следующие дополнительные соотношения: (R1R2)=R1R2, (R1R2) = R1R2; (R1R2)R1R2, (R1R2) R1R2; (R1\R2)R1\R2, (R1\R2) R1\R2; B этих соотношениях End (N), R1, R2 File (T), Ev (V). Элемент R можно считать "образом" R относительно действия . Теперь введем новую операцию "взятия прообраза" R1 в R2 относительно : *(R1,R2) {f R2 I αfR1}. Другими словами, *(R1,R2) состоит из тех элементов из R2, которые после умножения слева на а попадают R1. Очевидно, что *(R1,R2) *(R1αR2, R2}. Аналогично для любой переоценки βEv (V) положим β*(R1,R2) {f R2 I βfR1}. Введенные операции превращают множество File (T) в универсальную алгебру, сигнатура которой содержит символы нульарной операции ф, бинарных операций , , \, а*, β* и унарных операций α, β, где α End (N), βEv(V). Эту алгебру назовем алгеброй файлов. Таким образом, алгебра File (T) является дистрибутивной решеткой с относительными дополнениями, на которую действуют два моноида End(N) и Ev(V). Относительно этих действий в File(T) можно брать прообразы одного элемента в другом. Подчеркнем, что сигнатура алгебры File (T) зависит от остова Т: она определяется разбиением T на классы эквивалентности и выбором доменов в V. Выбор остова и, следовательно, сигнатуры — одно из средств построения подходящей для приложений модели данных. Зафиксируем остов TNxV и образуем алгебру File(T). Через G(N) и G(V) обозначим соответственно множества биективных согласований и переоценок. Легко проверить, что эти множества являются группами. Два файла R1 и R2 называются N-эквивалентными (V-эквивалентными), если существует такое согласование α G(N), что αR1= R2 (такая переоценка β G(V), что R1β= R2) ; обозначения: R1 Файлы R1 и R2 называются N-V-эквивалентными, если R2 = αR1β для некоторых согласования α и переоценки β; обозначение: R1 Из N-эквивалентности файлов следует их N-V-эквивалентность: действительно, если R2 = αR1 , то R2 = αR11V , где 1V — тождественная переоценка. Аналогичное замечание справедливо для V-эквивалентных файлов.
Определим бинарное отношение i, i = 1, . . . , n, между данными из R:fjifk тогда и только тогда, когда Aidef fj deffk и fj (Ai) = fk (Ai).;' jк; fjifj для любого j = 1,...,m. Отношение i очевидно является отношением эквивалентности. Таким образом, множество R превращено в конечную модель, сигнатура которой содержит n символов 1, 2, . . . , n. Эта модель удовлетворяет аксиомам, выражающим тот факт, что все i — эквивалентности: i =  =β , где , как всегда, обозначает отношение тождества. Еще одно важное свойство семейства эквивалентностей i заключается в том, что их пересечение равно отношению тождества:  .
Предложение 3. Пусть в множестве VT основных значений остова T N x V хотя бы один домен Dom А, AN бесконечен. Тогда для произвольной конечной модели (M, 1,…, n), удовлетворяющей аксиомам (3.24) и (3.25), существует такой файл R File(T), который изоморфен M как модель с общей сигнатурой. Проиллюстрируем это на примере. Пусть M={а1,а2,а3,а4}, 1={{а1,а2},{а3,а4}}, 2={{а1.а3}, {а2,а4}}, 3 ={{а1,а4}, {а2,а3}}. Эквивалентности 1, 2, 3 заданы теми разбиениями множества М, которые они определяют. Очевидно, что 123 =M. Допустим, что DomA состоит из натуральных чисел, и построим файл R, самым экономным образом выбирая различные значения функций f1, …, f4
Другое представление для множества M получим, выбирая самым неэкономным способом значения функций :
Полученные представления не являются N — V-эквивапентными, так как в первом из них функция f1 при любых умножениях на биективные согласования и переоценки будет переходить в функцию с единственным значением, а во втором представлении такой функции нет. Однако если бы домены для A1, A2, A3 не пересекались, то представления оказались бы N — F-эквивалентными. Вообще, любые N— F-эквивалентные файлы изоморфны как модели. До сих пор игнорировалось то обстоятельство, что файл R является в действительности многоосновной моделью, поскольку неэквивалентным именам атрибутов соответствуют разные домены. Другими словами, эквивалентности p,- разбиты на непересекающиеся группы, в которые входят эквивалентности, отвечающие именам с общим доменом. Допуская, что в модели (M, 1, …, n) также задано разбиение эквивалентностей на l непересекающихся групп и предполагая, что в T имеется l бесконечных доменов, можно показать в точности также, как и выше, что для M найдется такой изоморфный файл R, что разбиение эквивалентностей на группы в M и R совпадают. При помощи умножения на подходящее согласование можно "продублировать" некоторые значения в функциональном данном. Точно также при помощи согласований можно "продублировать" целые файлы. Именно, пусть дан файл R и at(R) = {A1,A2,…, An} .Для каждого Ai обозначим через  имя, эквивалентное Ai и не входящее в at(R),j = 1, 2,... , k. Определим теперь согласование , для которого
var = {   ,…,   ,   ,... , ,...,   , …,   }
и (
жүктеу/скачать 13,94 Mb. Достарыңызбен бөлісу:
|
) = Ai. Тогда файл R состоит из R и k копий R. Он выглядит следующим образом:
