Relational Algebra Operations

Set Difference

• Contains all tuples in R, but not in S, expressed as R - S = {tlti Rand ti S}

Relational Algebra

• Specifies how to derive results using operators and operands on relations

Union Operation

• Contains tuples in R or S, without duplicates, expressed as (RÈ S-{t| t Ror t S})

Cartesian (Cross) Product Operation

• R x S results in a relation of degree (k1 + k2)
• Consists of (n1 * n2)-tuples
• Each tuple is a concatenation of one tuple from R with one from S

Projection Operation

• Produces a vertical slice of a relation, notated as (PA1,.,An(R)=(#[A1,..., An] | AR})

Selection Operation

• Produces a horizontal subset of the operand relation, notated as (sF(R)={tR ard F(A) is true})

Outer-Join

• Guarantees tuples from one or both relations appear in the final result even if the join condition isn't met
• Attributes set to NULL for non-matching attributes

Natural Join

• Equi-join of relations R and S over common attribute(s)
• Projects out one copy of the common attributes

Computer Network

• An interconnected collection of autonomous computers which exchange information

Relational Calculus

• Specifies properties for the result of a query

Tuple Relational Calculus

• SQL is an example( at least in the simple form)

Domain Relational Calculus

• Query takes the form x1, x2,..., xnIF(x1, x2,..., xn)
• F is a well-formed formula and x1, x2,..., xn are free variables
• QBE is an example.

Point-to-Point (Unicast) Scheme Communication

• Involves one or more direct or indirect links between each pair of nodes
• Communication only occurs between two nodes

Wide Area Network (WAN)

• Experiences long delays due to distance
• Has heterogeneity of transmission media with speeds of 150Mbps to 10Gbps (OC192 on the backbone)

Network Components

• Hosts (nodes, end systems), switches and communication links

Broadcast Scheme Communication

• Messages transmitted over a shared channel and received by all nodes
• Each node checks the address and ignores messages not intended for it

Types of Network Topologies

• Star, ring, and mesh

Local Area Network (LAN)

• Speeds of 10-1000 Mbps
• Short delays, low noise, and limited geographic scope, generally < 2km

Packet Switched Communication

• Messages are divided into fixed-size packets
• Each packet is routed from source to destination

Communication Protocol

• Software to ensures error-free, reliable, and efficient communication between hosts

Communication Alternatives

• Twisted pair, coaxial, and microwave

TCP/IP Protocol

• Includes application, transport, network, and individual networks

Capacity - Bandwidth

• Refers to the amount of information transmitted over a channel in a given time unit

Circuit Switching

• Dedicated channel established between sender and receiver for the duration of the session

The Level of Knowledge in DDBS

• The quantity of information about how users access data

Level of Sharing

• Data sharing and data-plus program sharing

Three Orthogonal Dimensions of Organization in DDBS

• Level of sharing, pattern behavior, and level of knowledge

The Placement of Applications

• The placement of distributed DBMS software and applications on the database

Main Problem of DDBS Design

• Making decisions about the placement of data and programs across a computer network
• Possibly designing the network

Patern Behavior

• Static and dynamic alternatives

The Degree of Fragmentation

• Ranges from no fragmentation, to fragmentation to the level of individual tuples (horizontal) or attributes (vertical)

Top-Down Design

• Starts from the general and moves to the specific

Top-Down and Bottom-Up Design

• Two approaches for developing any DDBS sharing the goal of uniting the system by describing interaction between processes.

Bottom-Up Design

• Design presented when databases already exist at several sites

Fragmenting a DDB

• Either the relation isn't replicated and is stored at only one site
• Or it is replicated at all or some sites, former results in unnecessarily high volume of remote data accesses
• The latter (unnecessary replication) are reasons to do this

The First Part of a Framework for Top-Down Design Process

• Requirement analysis, View design and Conceptual design

Replicated and Non-Replicated Alternatives

• Fully replicated: each fragment at each site
• Partially replicated: each fragment at some of the sites

A Replicated Alternative

• Assuming a properly fragmented database, one must decide on the allocation of fragments to various network sites using these

Dividing It Horizontally or Dividing It Vertically

• Relation instances are essentially tables
• So the issue is finding alternative ways of dividing a table into smaller ones

Test Correctness

• Completeness, Reconstruction, and Disjointness are three Fragmentation Rules
• Ensure database doesn't undergo semantic change

Primary Horizontal Fragmentation

• Horizontal fragment Ri of relation R consists of tuples satisfying minterm predicate mi

Information Requirements to DDBS

• Logical organization of database, location of applications, access characteristics and properties of computer system at each site

Vertical Fragmentation

• Splitting is completed through this

Access Frequencies

• The frequency at which a user application qi accesses data

Minterm Selectivities

• The number of tuples of the relation accessed by a user query using a given minterm predicate mi

Primary Horizontal Fragmentation (PHF)

• Is performed using predicates defined on the original relation

Derived Horizontal Fragmentation (DHF)

• The partitioning of a relation results from predicates defined on another relation

Completeness of Simple Predicates

• A set of simple predicates Pr is complete if accesses to tuples of minterm fragments defined on Pr requires tuples of the same minterm fragment
• They have the same probability of being accessed by an application