Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Composition of binary relations .






Given two relations: a ⊆ A ´ B and β ⊆ B ´ C.

The composition aβ of relations a and β is a relation, specified on a pair of sets A and C s so that a(aβ)c is true only if there exists an element yÎ B such that aay and yβ c are both true. (Note: aÎ A, cÎ C.)

If a relation a ⊆ A ´ B and relation β ⊆ C ´ D and B ≠ C then the composition of such relations is considered to be not defined.

Examples of compositions:

a ⊆ N ´ N β ⊆ N ´ N where N is the set оf natural numbers.

a = {(a, b)|a ∈ N, b = a2};

β = {(b, c)|b ∈ N, c = 3b};

a(aβ)c = {(a, c)| a ∈ N, c = 3a2}.

Composition aβ of relations a and β can be specified by graphs:

a β aβ

 

The property of the composition: a β ≠ β a.

If a relation a is defined on a pair of sets A, B then its reverse relation a-1 is defined on the pair of sets B and A. a-1 contains all such pairs (b, a) for which aab is true. That means: ba-1a (is true) ⇔ a a b (is true).

Examples of reverse relations:

< -1 = >;

, to be a son'-1 = ' to be a parent';

'to be debter'-1 =" to be a creditor";

[detэ] ['kreditэ]

 

H/t. Given a set A = {0, 1, 2, 3} and two relations (<, =) specified on A. It is necessary to represent these relations as a set of ordered pairs, and also their union, intersection, difference, complement, composition and their reverse relations.

 

Practical application of relations and relational operations

 

In the previous topic we studied operation on relations. One may ask if they have any practical application.

An answer to the question:

A set of relations together with operations defined on these relations constitute the relational algebra. This algebra is used for analysis and design of relational databases.

In relational databases, relations are presented by means of tables.

For example, for some enterprise, there might be a relational database with such tables – relations R1 and R2:

Then the relation “enterprise section R3 recipient” is defined as a composition of relations “enterptise section (R1 ● R2) recepent”.

The relational algebra makes it possible to define new relations by means of operations (-, U, ∩, etc.) without paying attention to technical details: (how to sort data, how to store data, how to retrieve it and so on. Using relational operations, a database designer can concentrate just on input and output data.

 

A vocabulary for the topic “Equivalence”
(Binary relations and their properties)

Equivalence [ik’wi: vә lә ns] – эквивалентность,

Reflexive [ri’fleksiv] – рефлективный,

Anti-reflexive [‘æ nti’rifleksiv] – антирефлексивный,

Symmetrical [ si’metrical] – симметричный,

Transitive [‘træ nzitiv] – транзитивный,

Nontransitive [non’træ nzitiv] – нетранзитивный,

A partition [pɑ ː ˈ tɪ ʃ ə n] – разбиение,

Nonintersecting - непересекающийся,

To put into a correspondence – ставить в известность,

Strict (antireflexive) order – строгий порядок,

Partial order – частичный порядок,

Tolerance – толерантность,

Etc. = et cetera [¶t’setr¶] – и так далее.


 

Topic: Equivalence

In real world there are most various relations between very different objects. Examples: “an object a is heavier than an object b ”, “a person x and a person y were born in the same town”, “an enterprise Z produces the product t ”, etc.

All such binary relations can be characterized by means of a small set of deep level properties.

A binary relation α is called reflexive if

∀ x ∈ A, x α x

Examples: a ≤ b, “x and y have the same color of eyes”, , etc.

A binary relation α is called antireflexive if

∀ x ∈ A,

Examples: a < b, “ a is a son of b” etc.

A relation α is called symmetric if

∀ x, y ∈ A, x α y (implies) y α x

Examples: the relation of kindred, the relation to belong to the same academic group, etc.

A relation is called antisymmetric if

∀ x, y ∈ A, x α y and y α x è x = y

Examples: a≤ b, etc.

A relation is called transitive if

∀ x, y, z ∈ A, xα y and yα z è xα z

Example: the relation “to be older”, the relation of kindred, etc.

A relation α is called non-transitive if

∀ x, y, z ∈ A xα y and yα z è xα z

Examples: the relation “to be a son”, the relation “to be a debtor”, etc.

A binary relation α is called equivalence if it reflexive, symmetric and transitive.

Examples of binary relations that are equivalences:

“to be a relative”, “to have the same weight”, “to study at the same academic group”, etc.

The relation of equivalence is a formal substitute of such everyday notions as “to be interchangeable”, “to be identical with”, “to be indistinguishable from”, etc.

This relation defines a feature (a property) that enables to make a partition of a set A into disjoint subsets. Within each subset elements are indistinct on the basis of that feature.

A system S={ , of non- empty subsets of the given set A is called a partition of A if ⊆ A, =Ø, U U…U =A, i, j Î {1, 2, …, k}, i ¹ j.

The subsets are called equivalent classes of the partition/clssification S.

A binary relation σ can be put into a correspondence with each partition of A if it is assumed by definition that xσ y is true iff x, yÎ .

This relation σ is equivalence:






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.