Relational Data Structure

in RDM
Relations and tables
Keys of relations

is an association between any number of entities.

Like subject Is more Supply Who What First Second Who Whom What Q-ty
John DBMS 5 3 П1 К7 table 200
Peter С 17 5 П3 К14 door 150
Ann XML 2 1 П18 К9 window 1000

Relation R, defined on these sets, is a set of ordered n-tuples (d1, d2,…, dn), such that d1 ∈ D1, …, dn ∈ Dn

Lets given sets D1, D2,…, Dn (does not obligatory distinct). Cartesian product of these sets, denoted as D1 × D2 ×…× Dn, is a set of all possible tuples (d1, d2,…, dn), such that di ∈ Di, i = 1,n.
R is a relation on the sets D1, D2,…, Dn, if:
R ⊆ D1 × D2 ×…× Dn = {(d1, d2,…, dn) ⏐ di ∈ Di, i = 1,2,…,n}

relation R .
- n is a degree of the relation R or its arity.
- Number of tuples in a relation is called cardinality.
- Tuple is a row of the relation.

D1 D2 … Dn
R a11 a12 … a1n a22 a22 … a2n . . . ak1 ak2 … akn

Domains

Degree, arity

Cardinality

Relation name

Relation

Tuple

logical condition: R(x,y,...,z) = {(x,y,...,z) | φ(x,y,...,z)}

∨ t ∈ S}
Intersection: R ∩ S = {t | t ∈ R & t ∈ S}
Negation: ¬R = {t | t ∉ R}
Cartesian product: R × S = {(r,s) | r ∈ R & s ∈ S }

Relation R is symmetric if ∀a∀b (R(a, b) ⇒ R(b, a))
Transitivity: Relation R transitive if: ∀a∀b∀с (R(a, b) & R(b, с) ⇒ R(a, c)).
Antisymmetry: Relation R is antisymmetric if:
∀a∀b (R(a, b) & R(b, a) ⇒ a = b).

himself), symmetric (if b looks like d, then d looks like b), but not transitive (if have chain of pairs of similar persons it does not mean that persons at the ends of this chain are similar).
Relation Is-Higher(x,y) is transitive but not reflexive and symmetric.
Relation Is-Equal (=) is reflexive, symmetric and transitive.
Relation Teach(x,y) is not reflexive, symmetric and transitive.

More Is More 5 3 3 5 17 5 5 17

In relational data structure order of “columns” is not essential. It is achieved at the expense of introducing of the concept “attribute”.

Attribute – is semantically sensible names of the relation columns.

of a relation has a name.
The set of allowed values for each attribute is called the domain of the attribute.
Different attributes may have the same domain.
Attribute values are required to be atomic, that is, indivisible.

Properties of the relation schema:
Every schema has a name.
Attribute names in schema must be unique.
Order of attributes in schema is not fixed

only difference – the order of columns in the relation is not important.

Properties of a relation instance:
Order of attributes is arbitrary, but it is defined by a relation schema.
Order of tuples is arbitrary (tuples may be located in an arbitrary order)
Tuples must be unique within the instance

properties:
Name of the relations in relational schema must be unique

As relational structure the set of the relational schema and its instance (state).

The relational schema is a set of the schemas of relations: R1(A1,…,An)
R2(B1,…,Bk)
…
Rn(K1,…,Km)

Instance of relational schema is a set of instances of the relations in relational schema .

SALARY
…

Teachers: No: Name: Post: Salary: ID NAME POST SALARY
1 John assistant 700 2 Ann senior assist. 800 3 Bob analyst 500 4 Tom professor 900

Attributes

Relation schema

Relation instance

Domains

columns key unique identifier

the tuples of the relation.

Assertion. Any relation has a key.

Example: In the relation STUDENT(No, Name, Course) set of attributes (No, Name, Course) are key because tuples of any relation are unique.

Assertion. Any relation may has many keys.

one attribute.

The key compound if it consists of several attributes.

Example. In the relation:
STUDENT(ID-No, Name, Pasp-ser, Pasp-No, Course)
ID-No is a simple key and pair of attributes (Pasp-ser, Pasp-No) is a compound key.

is a subset of this key that is also a key. Redundant key is also called superkey.

Example. In the relation:
STUDENT(ID-No, Name, Pasp-ser, Pasp-No, Course) key (Pasp-ser, Pasp-No, Course) is redundant key because its subset (Pasp-ser, Pasp-No, Course) is also a key

Nonredundant key is called minimal.

them are called candidate keys.

Example. Relation:
STUDENT (ID-No, Name, Pasp-ser, Pasp-No, Course) has two minimal (that is why candidate) keys:
ID-No
Pasp-ser, Pasp-No

Among set of all candidate (minimal) keys only one is selected as a primary key.

never be duplicated. That is they are unique within a relation. But there may be duplicates in parts of compound primary key.
Primary key cannot have NULL values.
Additional properties:
Every relation must have one and only one primary key.
Primary key do not influence attribute order.
Primary keys do not influence tuple order.

СН 951945 2 Ann СН 917327 3 Bob СК 917327 4 Tom ВО 111223
5 Albert ВО 111223 6 Ben МК NULL 7 Dick NULL 457328

Components of a primary may not be unique

This tuple violates primary key constraint because it contains duplicate value of the primary key

The last two tuples violate primary key constraint because they contain NULL values

values”.

Foreign key is one or more attributes of a relation that are used to reference to tuples of other relation.
Relation that is references to other relation is called child relation.
Relation that is referenced by other relation is called parent relation.

Child relation may references only to primary key (or unique key) of the parent relation.

cannot reference to absent values of the primary key of the parent relation. It is so called referential integrity constraint of the foreign key.
Additional properties:
Foreign key can contain duplicate values.
Foreign key can contain NULL values.

tuple is added or updated referential constraint is tested and if it is violated the corresponding action (adding/updating) is rejected.
When a tuple is deleted referential constraint cannot be violated.
Manipulating by tuples of a parent relation :
When a tuple is added referential constraint cannot be violated.
When deleting of updating:
Tuple deleting/updating is not done if there are references from child relation, that violate referential integrity constraint.
Deleting/updating tuple of parent relation causes deleting/updating tuples of a child relation that references the tuple of the parent relation.
Deleting/updating tuple of parent relation causes setting NULL values to corresponding tuples of a child relation .
Deleting/updating tuple of parent relation causes setting DEFAULT values to corresponding tuples of a child relation.

SQL:

ON DELETE {RESTRICT | CASCADE | SET NULL | SET DEFAULT}
ON UPDATE {RESTRICT | CASCADE | SET NULL | SET DEFAULT}

Supporting referential integrity constraints in SQL Oracle:

[ON DELETE {CASCADE | SET NULL}]

3 CTF Peter

Department No Name Head FacNo
1 SE John 1 2 DBMS Dick 1 3 CAD Kate 2 4 PL Lucy NULL

ON DELETE RESTRICT

This tuple cannot be deleted because it is referenced by tuples of a child relation

This tuple may be deleted because it is not referenced

ON UPDATE RESTRICT

The “No” attribute of these tuples cannot be updated because they are referenced by foreign keys of a child relation

This tuple may be changed including “No” attribute

3 CTF Peter

Department No Name Head FacNo
1 SE John 1 2 DBMS Dick 1 3 CAD Kate 2 4 PL Lucy NULL

ON DELETE CASCADE

When deleting this tuple the following tuples of parent relation are also deleted.

ON UPDATE CASCADE

When “No” attribute of this tuple is changed the following values of “FacNo” atribute are also changed.

2 SEF Dick 3 CTF Peter

Department No Name Head FacNo
1 SE John 1 2 DBMS Dick 1 3 CAD Kate 2 4 PL Lucy NULL

ON DELETE SET NULL

On deleting this tuple the following values of “FacNo” attribute are set to NULL.

ON UPDATE SET NULL

When “No” attribute of this tuple is changed the following values of “FacNo” atribute are set to NULL.

2 SEF Dick 3 CTF Peter

Department No Name Head FacNo
1 SE John 1 2 DBMS Dick 1 3 CAD Kate 2 4 PL Lucy NULL

ON DELETE SET DEFAULT

On deleting this tuple the following values of “FacNo” attribute are set to default value.

ON UPDATE SET DEFAULT

When “No” attribute of this tuple is changed the following values of “FacNo” atribute are set to default value.

primary key of the relation where it is defined.

Teacher No Name Pasp-Ser Pasp-No ChiefNo
1 Ann СН 951945 4 2 Dick СН 917327 4 3 Peter СК 917327 7 4 John ВО 111223 7 5 Kate ВО 111224 4 6 Lucy МК NULL 7 7 Mary NULL 457328 NULL

It allows to model hierarchy structure that is defined on one relation.

of