Relational Data Structure

Software Engineering

relations in RDM

Relations and tables

Keys of relations

condition
Relation 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

distinct). 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}

the 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

As a table

Graphical

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

R ∨ 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 }

a).

Symmetry: 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).

like 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.

Is 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.

attribute 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

the 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

following 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 .

POST
assistant,
professor,
…

Domains
NAME
…

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

of columns key unique identifier

identify 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.

of 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.

there 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.

of 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.

must 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.

Past-Ser Pasp-No
1 John СН

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

“by 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.

key 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.

a 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.

standard 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}]

1 CSF Ann 2 CEF 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 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

1 CSF Ann 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 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.

Dean
1 CSF Ann 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.

Dean
1 CSF Ann 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.

the 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.

curriculum of

SUBJECT(ID,Name)

LECTURE(TID,SID, Hours)