называется элементарной подсистемой  1, а  1 – элементарным расширением  , если:

(а) Â - подсистема Â 1,

(б) тождественное отображение Â в Â 1 является элементарным.

Пример 7.1. Пусть о и р— отношения на N такие, что

о=={(х, а-+1): дет, р={[х2, х): хе=Ю. Тогда

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

Современная теория баз данных включает в себя изучение так называемых нормальных форм, однако обоснование некоторых из них очевидно лишь в простых случаях. Мы рассмотрим только три формы для следующих задач:

— вставить новый набор из п элементов;

Пример 5.1. Пусть задано произвольное множество А. Тогда отношение s на У (А) есть тривиальное отношение порядка. {X s X для всех X; если Х s Y и Y s X, то Х - У; Х s Y и Y s Z => Х s Z.) II

Отношение порядка р на А называется полным, если. для любых х, у <= А или хру, или урх (или же выполняются оба).

Гомоморфизм j : Â 1 ® Â 2 назовем сильным, если выполняется

(г) если Â 2 ╞ R n ( j (b1),…, (j (bn)), то существуют b1’,…, bn’ Î M 1 такие, что j (b1)= j (b1’) ,…, j (bn) = j (bn’) и Â 1 ╞ R n (b1’ ,…, bn’).

Взаимно однозначное соответствие j между М1 и М2 назовем изоморфизмом между Â 1 и Â 2, если j и j-1 ¾ гомоморфизмы. Если Â 1 изоморфна Â 2, то пишем Â 1 ~ Â 2.