CSE 4125: Distributed Database
Systems
Chapter - 2
Review of Databases and Computer
Networks
Rajon|AUST 1
Outline
Review of Database.
Review of Computer Networks.
Rajon|AUST 2
Review of Databases
Rajon|AUST 3
The Relational Model
Relations: Data stored in tables.
Attributes: Fixed number of columns.
Tuples: Dynamic number of rows.
Grade: Number of attributes.
Cardinality: Number of tuples.
Rajon|AUST 4
Rajon|AUST 5
Relational Schema
Representation of a relation.
Name of the relation and the attributes
appearing in it.
Example:
𝐸𝑀𝑃 (𝐸𝑀𝑃𝑁𝑈𝑀, 𝑁𝐴𝑀𝐸, 𝐴𝐺𝐸, 𝐷𝐸𝑃𝑇𝑁𝑈𝑀)
Rajon|AUST 6
KEYS
Subset of the attributes whose values are unique.
Example:
𝐸𝑀𝑃 (𝐸𝑀𝑃𝑁𝑈𝑀, 𝑁𝐴𝑀𝐸, 𝐴𝐺𝐸, 𝐷𝐸𝑃𝑇𝑁𝑈𝑀)
Rajon|AUST 7
Relational Algebra
A collection of operations.
Takes relation(s) as input.
Produces one relation as result.
Two types –
i. Unary: 1 input, 1 result
ii. Binary: 2 inputs, 1 result
Rajon|AUST 8
Unary: Selection
Example: SL A= a R
R S T Result
A B C
a 1 a a 1 a 1 a 1
b 1 b a 3 f 3 b 1
a 1 d 3 c 2
b 2 f 1 d 4
2 a 3
Rajon|AUST 9
Unary: Selection
Example: SL A= a R
R S T Result
A B C
a 1 a a 1 a 1 a 1 a 1 a
b 1 b a 3 f 3 b 1 a 1 d
a 1 d 3 c 2
b 2 f 1 d 4
2 a 3
Rajon|AUST 10
Unary: Projection
Example: PJ A,B R
R S T Result
A B C
a 1 a a 1 a 1 a 1
b 1 b a 3 f 3 b 1
a 1 d 3 c 2
b 2 f 1 d 4
2 a 3
Rajon|AUST 11
Unary: Projection
Example: PJ A,B R
R S T Result
A B C
a 1 a a 1 a 1 a 1 a 1
b 1 b a 3 f 3 b 1 b 1
a 1 d 3 c 2 b 2
b 2 f 1 d 4
2 a 3
Rajon|AUST 12
Binary: Union
Example: R UN S
R S T Result
A B C
a 1 a a 1 a 1 a 1
b 1 b a 3 f 3 b 1
a 1 d 3 c 2
b 2 f 1 d 4
2 a 3
Rajon|AUST 13
Binary: Union
Example: R UN S
R S T Result
A B C
a 1 a
a 1 a a 1 a 1 a 1
b 1 b
b 1 b a 3 f 3 b 1 a 1 d
a 1 d 3 c 2 b 2 f
a 3 f
b 2 f 1 d 4
2 a 3
Rajon|AUST 14
Binary: Difference
Example: R DF S
R S T Result
A B C
a 1 a a 1 a 1 a 1
b 1 b a 3 f 3 b 1
a 1 d 3 c 2
b 2 f 1 d 4
2 a 3
Rajon|AUST 15
Binary: Difference
Example: R DF S
R S T Result
A B C
b 1 b
a 1 a a 1 a 1 a 1
a 1 d
b 1 b a 3 f 3 b 1
b 2 f
a 1 d 3 c 2
b 2 f 1 d 4
2 a 3
Rajon|AUST 16
Binary: Cartesian Product
Example: R CP S
R S T Result
A B C
a 1 a a 1 a 1 a 1
b 1 b a 3 f 3 b 1
a 1 d 3 c 2
b 2 f 1 d 4
2 a 3
Rajon|AUST 17
Binary: Cartesian Product
Example: R CP S
R S T Result
A B C
a 1 a a 1 a
a 1 a a 1 a 1 a 1 b 1 b a 1 a
b 1 b a 3 f 3 b 1 a 1 d a 1 a
b 2 f a 1 a
a 1 d 3 c 2
a 1 a a 3 f
b 2 f 1 d 4 b 1 b a 3 f
a 1 d a 3 f
2 a 3
b 2 f a 3 f
Rajon|AUST 18
Binary: Join
Example: R JNR.C=T.C T
R S T Result
A B C
a 1 a a 1 a 1 a 1
b 1 b a 3 f 3 b 1
a 1 d 3 c 2
b 2 f 1 d 4
2 a 3
Rajon|AUST 19
Binary: Join
Example: R JNR.C=T.C T
R S T Result
A B C
a 1 a 1 a 1
a 1 a a 1 a 1 a 1
a 1 a 2 a 3
b 1 b a 3 f 3 b 1 b 1 b 3 b 1
a 1 d 3 c 2 a 1 d 1 d 4
b 2 f 1 d 4
2 a 3
Rajon|AUST 20
Binary: Natural Join
Example: R NJN T
R S T Result
A B C
a 1 a a 1 a 1 a 1
b 1 b a 3 f 3 b 1
a 1 d 3 c 2
b 2 f 1 d 4
2 a 3
Rajon|AUST 21
Binary: Natural Join
Example: R NJN T
R S T Result
A B C
a 1 a a 1 a 1 a 1 a 1 a 1
b 1 b a 3 f 3 b 1 a 1 d 4
a 1 d 3 c 2
b 2 f 1 d 4
2 a 3
Rajon|AUST 22
Binary: Semi-join
Example: R SJR.C=T.C T
R S T Result
A B C
a 1 a a 1 a 1 a 1
b 1 b a 3 f 3 b 1
a 1 d 3 c 2
b 2 f 1 d 4
2 a 3
Rajon|AUST 23
Binary: Semi-join
Example: R SJR.C=T.C T
R S T Result
A B C
a 1 a a 1 a
a 1 a 1 a 1
b 1 b
b 1 b a 3 f 3 b 1
a 1 d
a 1 d 3 c 2
b 2 f 1 d 4
2 a 3
Rajon|AUST 24
Binary: Natural Semi-join
Example: R NSJ T
R S T Result
A B C
a 1 a a 1 a 1 a 1
b 1 b a 3 f 3 b 1
a 1 d 3 c 2
b 2 f 1 d 4
2 a 3
Rajon|AUST 25
Binary: Natural Semi-join
Example: R NSJ T
R S T Result
A B C
a 1 a
a 1 a a 1 a 1 a 1
a 1 d
b 1 b a 3 f 3 b 1
a 1 d 3 c 2
b 2 f 1 d 4
2 a 3
Rajon|AUST 26
SQL
Result
Select NAME, AGE
From EMP
Where AGE>20 and DEPTNUM = 1
Select A, R.C Result
From R, T
Where R.B = T.B and D = 3
Rajon|AUST 27
SQL
Result
Select NAME, AGE
From EMP Jones 27
Where AGE>20 and DEPTNUM = 1 Mary 31
Select A, R.C Result
From R, T
Where R.B = T.B and D = 3 b f
Rajon|AUST 28
Application, Program and Query
Database Applications:
Sequence of operations requested by end users (not a
programmer).
Examples: read.
Database Programs:
Implementation of the application.
Query:
An expression in a suitable language.
Defines a portion of data contained in DB.
Rajon|AUST 29
Review of Computer Networks
Rajon|AUST 30
Computer Network
Computers (hosts/ sites)
capable of performing
autonomous work.
Connected by Communication
network (communication links
+ computers).
A process running at any site
can send a message to a
process running at another
site.
Rajon|AUST 31
Parameters of CN
Delay: Time with which the message is delivered.
Costs: Fixed costs + costs proportional to message
length.
Reliability: Probability of correct delivery of the
message.
Rajon|AUST 32
IMPs
Interface Message Processors:
Dedicated processors pair-wise connected by
communication links.
Routing: function of choosing path from source to
destination.
Rajon|AUST 33
Types of CNs
Point-to-point:
Pairs of sites/ hosts are directly connected.
Broadcast:
All sites/ hosts shares a single communication channel.
Rajon|AUST 34
Types of Broadcast
Satellite
Common bus
Rajon|AUST 35
Network Topologies
1. Star
2. Hierarchical
3. Ring
4. Completely connected
5. Irregular
Rajon|AUST 36
Protocols and Sessions
Protocols:
Rules followed by two or more processes for
communicating.
Example: making a phone call.
Sessions:
A session is established between two processes
and is held until all necessary messages have been
exchanged.
Example: conversation over a phone.
Rajon|AUST 37
The ISO/ OSI Reference Architecture
ISO : International Standards Organization
OSI: Open System Interconnection
Rajon|AUST 38
Application layer:
Algorithms and protocols.
Presentation layer:
Conversion of information.
Example: character code conversion from sender
end to receiver end.
Session layer:
Establishing and maintaining sessions.
Rajon|AUST 39
Transportation layer:
True source-to-destination layer.
Implements point-to-point channel between
source and destination.
To perform efficiently, it uses the services of –
Network layer.
Data-link layer.
Physical layer.
Rajon|AUST 40
Sample Questions
Rajon|AUST 41