Iii республикалық студенттік ғылыми-практикалық конференциясының баяндамалар жинағЫ



бет51/184
Дата08.06.2018
өлшемі13,94 Mb.
#41389
1   ...   47   48   49   50   51   52   53   54   ...   184

Литература

  1. Павлюк И.И. Карибаева Т.Н. о понятии группы и основных ее свойствах //

Материалы международной научной конференции молодых ученых студентов “VII Сатпаевские чтения”. Павлодар.2007.С. 304-308.

2. Каргаполов М.И., Мерзляков Ю.И. Основы теории групп // М.:Наука 1982 г. 288с.

УДК 517.51
Строение алгебры функциональных данных
Жубайдолла Е. А.

Атырауский государственный университет им. Х. Досмухамедова. Атырау
Научный руководитель – Абиров А. Х. к.-ф.м.н доцент
Работа посвящена описанию алгебраических систем, которые естественно назвать моделями данных.

Обозначим через Str (T) множество всех функциональных данных. B этом множестве имеется особый элемент — нигде не определенная функция, которая будет обозначаться символом . B Str(T) можно вести порядок, положив fg, если deff  defg и f(A) = g(A) для любого А  deff. Другими словами, fg, если g является продолжением функции f или, что то же самое f есть сужение g.

Введенный порядок можно интерпретировать как отношение "большой информативности": так как g является продолжением f, то g сообщает" большой информации", чем f.

Предложение 1. Порядок  превращает Str(T) в полурешетку по пересечениям с наименьшим элементом . Объединение f  g существует тогда и только тогда, когда f (A) =g (A) для каждого A  def f  defg.

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) . Используя множество at (R), можно объединить отдельные табличные представления данных из R в общее табличное представление.

Положим теперь по определению

R  {f1| f1R}, End (N), R  {f1| f1R}, Ev(V)

B частности, если R = ф, то ф = ф = ф для любых  и .

Эти определение распространяют умножение, введенное для согласований, функциональных данных и переоценок, на множества функциональных данных. Выполняются следующие дополнительные соотношения:

(R1R2)=R1R2, (R1R2) = R1R2; (R1R2)R1R2,

(R1R2) R1R2; (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 αfR1}. Другими словами, *(R1,R2) состоит из тех элементов из R2, которые после умножения слева на а попадают R1. Очевидно, что *(R1,R2)  *(R1αR2, R2}. Аналогично для любой переоценки βEv (V) положим β*(R1,R2)  {f R2 I βfR1}. Введенные операции превращают множество File (T) в универсальную алгебру, сигнатура которой содержит символы нульарной операции ф, бинарных операций , , \, а*, β* и унарных операций α, β, где α End (N), βEv(V).

Эту алгебру назовем алгеброй файлов. Таким образом, алгебра File (T) является дистрибутивной решеткой с относительными дополнениями, на которую действуют два моноида End(N) и Ev(V). Относительно этих действий в File(T) можно брать прообразы одного элемента в другом. Подчеркнем, что сигнатура алгебры File (T) зависит от остова Т: она определяется разбиением T на классы эквивалентности и выбором доменов в V. Выбор остова и, следовательно, сигнатуры — одно из средств построения подходящей для приложений модели данных.

Зафиксируем остов TNxV и образуем алгебру File(T). Через G(N) и G(V) обозначим соответственно множества биективных согласований и переоценок. Легко проверить, что эти множества являются группами. Два файла R1 и R2 называются N-эквивалентными (V-эквивалентными), если существует такое согласование α G(N), что αR1= R2 (такая переоценка β G(V), что R1β= R2) ; обозначения: R1  R2 (R1  R2). Ввиду того, что G(N) и G(V) — группы, отношения  и  действительно являются отношениями эквивалентности. Друг от друга N-эквивалентные файлы отличаются только именами столбцов в соответствующих таблицах; V-эквивалентные файлы имеют общее множество имен столбцов и одинаковое число данных, в которых согласованным образом изменены значения, причем разные значения заменены разными значениями.

Файлы R1 и R2 называются N-V-эквивалентными, если R2 = αR1β для некоторых согласования α и переоценки β; обозначение: R1  R2 Строение N-V-эквивалентных файлов полностью определяется числом столбцов и строк в соответствующих таблицах, а также условиями совпадения отдельных значений, а не самими значениями.

Из N-эквивалентности файлов следует их N-V-эквивалентность: действительно, если R2 = αR1 , то R2 = αR11V , где 1V — тождественная переоценка. Аналогичное замечание справедливо для V-эквивалентных файлов.

Предложение 2. Для всякого файла R1 существует такой N-эквивалентный файл R2, что at(R1)  at(R2) = Ф-

Определим бинарное отношение i, i = 1, . . . , n, между данными из R:fjifk тогда и только тогда, когда Aidef 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 А, AN бесконечен. Тогда для произвольной конечной модели (M, 1,…, n), удовлетворяющей аксиомам (3.24) и (3.25), существует такой файл R  File(T), который изоморфен M как модель с общей сигнатурой.

Проиллюстрируем это на примере. Пусть

M={а1234}, 1={{а12},{а34}}, 2={{а13}, {а24}}, 3 ={{а14}, {а23}}.

Эквивалентности 1, 2, 3 заданы теми разбиениями множества М, которые они определяют. Очевидно, что 123 =M. Допустим, что DomA состоит из натуральных чисел, и построим файл R, самым экономным образом выбирая различные значения функций f1, …, f4



R

A1

A2

A3

f1

1

1

1

f2

1

2

2

f3

3

1

2

f4

3

2

1

Другое представление для множества M получим, выбирая самым неэкономным способом значения функций :



R1

A1

A2

A3

f1

1

2

3

f2

1

4

5

f3

6

2

5

f4

6

4

3

Полученные представления не являются 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 = { ,…, , ,... , ,..., , …, }

и () = Ai. Тогда файл R состоит из R и k копий R. Он выглядит следующим образом:



A1

A2



An

















}

f1(A1)



fm(A1)



f1(A2)



Fm(A2)





f1(An)



Fm(An)



f1(A1)



Fm(A1)



f1(A2)



Fm(A2)





f1(An)



Fm(An)





f1(A1)



Fm(A1)



f1(A2)



Fm(A2)





f1(An)



fm(An)






Достарыңызбен бөлісу:
1   ...   47   48   49   50   51   52   53   54   ...   184




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет