Thiết kế CSDL phân tán

PGS.TS. Đỗ Phúc Khoa Hệ thống thông tin Trường Đại học Công nghệ thông tin, ĐHQG-HCM

Distributed DBMS

Page 5. 1

Bài toán thiết kế

Quyết định bố trí dữ liệu và chương trình trên các vị trí của mạng máy tính cũng như thiết kế bản thân mạng.

 Nguyên tắc chung:

gồm:

 Bố trí phần mềm Hệ QTCSDLPT; và

 Bố trí các ứng dụng chạy trên CSDL.

Distributed DBMS

Page 5. 2

 Trong Hệ QTCSDLPT, việc bố trí ứng dụng bao

Các khía cạnh của bài toán

Access pattern behavior

dynamic

static

partial information

data Level of knowledge

data + program complete information

Distributed DBMS

Page 5. 3

Level of sharing

Thiết kế phân tán

 Thiết kế hệ thống từ đầu

 Các hệ thống đồng chất (homogeneous systems)

 Từ trên xuống (Top-down)

 Khi đã có CSDL ở một số vị trí

Distributed DBMS

Page 5. 4

 Từ dưới lên (Bottom-up)

Thiết kế từ trên xuống

Requirements Analysis

Objectives

User Input

View Design

View Integration

Conceptual Design

GCS

ES’s

Access Information

User Input

Distribution Design

GCS: Global conceptual schema

LCS’s

ES:External Schema

LCS:Local conceptual schema

Physical Design

LIS’s

Distributed DBMS

Page 5. 5

Các vấn đề của thiết kế phân tán

Tại sao phải phân mảnh dữ liệu?

Cách phân mảnh?

Mức độ phân mảnh?

Cách kiểm tra tính đúng đắn?

Cách cấp phát?

Các thông tin cần thiết?

Distributed DBMS

Page 5. 6

Phân mảnh dữ liệu

 Quan hệ

 views là tập con của quan hệ -> cục bộ  Cần truyền thông ( qua mạng) nhiều hơn- nếu quan hệ

 Chỉ để phân tán các quan hệ?  Đơn vị phân tán nào là hợp lý?

được lưu ở nơi khác với vị trí khởi động truy vấn  Các phân mảnh của quan hệ (quan hệ con)-thích hợp  Thực hiện đồng thời một số giao tác nhằm truy cập các

 Views không được định nghĩa trên một mảnh duy nhất

phần khác nhau của quan hệ

 Kiểm soát dữ liệu ngữ nghĩa (đặc biệt là ép thỏa toàn

sẽ yêu cầu nhiều xử lý.

Distributed DBMS

Page 5. 7

vẹn) là điều khó khăn

Các kiểu phân mảnh– ngang

PROJ

PNO

PNAME

BUDGET

LOC

PROJ1 : các projects có kinh phí

150000 Montreal New York New York New York New York

P1 Instrumentation P2 Database Develop. 135000 250000 P3 CAD/CAM 310000 Paris P4 Maintenance 500000 Boston P5 CAD/CAM

nhỏ hơn $200,000 PROJ2 : các projects có kinh phí lớn hơn hay bằng $200,000

PROJ1

PROJ2

LOC

LOC

PNO

PNAME

PNO

PNAME

BUDGET

BUDGET

P1 Instrumentation

150000 Montreal

P3 CAD/CAM

250000 New York

P2 Database Develop. 135000 New York

P4 Maintenance

310000 Paris

P5 CAD/CAM

500000 Boston

Distributed DBMS

Page 5. 8

Các kiểu phân mảnh– dọc

PROJ

PNO

PNAME

BUDGET

LOC

PROJ1: thông tin về kinh phí

của đề án

150000 Montreal New York New York New York New York

PROJ2: thông tin về tên và vị trí của đề án

P1 Instrumentation P2 Database Develop. 135000 250000 P3 CAD/CAM 310000 Paris P4 Maintenance 500000 Boston P5 CAD/CAM

PROJ1

PROJ2

PNO BUDGET

PNO

PNAME

LOC

P1 P2 P3 P4 P5

150000 135000 250000 310000 500000

Montreal P1 Instrumentation P2 Database Develop. New York New York P3 CAD/CAM Paris P4 Maintenance Boston P5 CAD/CAM

Distributed DBMS

Page 5. 9

Mức độ phân mảnh

Số hữu hạn các kiểu

Bộ

Quan hệ (không phân mảnh)

hay Thuộc tính Phân mảnh (ngang, dọc)

Phân mảnh đến mức độ nào sẽ quyết định đến hiệu năng truy vấn Tìm mức độ thích hợp để phân hoạch trong phạm vi

Distributed DBMS

Page 5. 10

Tính đúng đắn trong phân mảnh

 Tính đầy đủ (completeness)

 Phân rã quan hệ R thành các mảnh R1, R2, ..., Rn là đầy đủ nếu và chỉ nếu mỗi mục dữ liệu trong R đều có thể tìm thấy trong quan hệ Ri nào đó.  Tính tái tạo (reconstruction)

 Nếu quan hệ R được phân rã thành các mảnh R1, R2, ...,

Rn, thì sẽ tồn tại một toán tử quan hệ  sao cho:

R = 1≤i≤nRi

 Nếu quan hệ R được phân rã thành các mảnh R1, R2, ...,

Rn, và mục dữ liệu di thuộc về Rj, thì di không thuộc về bất kỳ mảng nào khác Rk (k ≠ j ).

Distributed DBMS

Page 5. 11

 Tính rời nhau (disjointness)

Các cách cấp phát

 Không nhân bản (non-replicated)

 Phân hoạch: mỗi mảnh nằm trên một vị trí, đây là bản sao

 Nhân bản (replicated)

 Nhân bản đầy đủ: một mảnh ở một vị trí ( full replication),

duy nhất của một mảnh trên mạng.

 Nhân bản từng phần: mỗi mảnh ở vài vị trí ( partial

toàn bộ CSDL đều tồn tại ở từng vị trí.

 Quy tắc:

replication)

1 read - only queries update queries

Distributed DBMS

Page 5. 12

If thì nên nhân bản , otherwise nhân bản có thể phát sinh vấn đề

So sánh các kiểu nhân bản

Full-replication

Partial-replication

Partitioning

Same Difficulty

Easy

QUERY PROCESSING

Same Difficulty

DIRECTORY MANAGEMENT

Easy or Non-existant

Moderate

Difficult

Easy

CONCURRENCY CONTROL

RELIABILITY

Very high

High

Low

Realistic

REALITY

Possible application

Possible application

Distributed DBMS

Page 5. 13

Các yêu cầu về thông tin

 thông tin về CSDL

 thông tin về ứng dụng

 Thông tin về mạng truyền thông

 Thông tin về hệ thống máy tính

Distributed DBMS

Page 5. 14

 Có 4 nhóm:

Phân mảnh

 Phân mảnh ngang nguyên thủy (PHF)

 Phân mảnh ngang được suy(DHF)

 Phân mảnh ngang (HF)

 Phân mảnh dọc (VF)

Distributed DBMS

Page 5. 15

 Phân mảnh hỗn hợp (HF)

Phân mảnh ngang nguyên thủy PHF – yêu cầu thông tin

Với link L1

 Quan hệ

Owner(L1)=SKILL

SKILL

Member(L1)=EMP

TITLE, SAL

L 1

EMP

PROJ

ENO, ENAME, TITLE

PNO, PNAME, BUDGET, LOC

L 3

Quan hệ nằm tại đuôi của link là owner và qhệ nằm tại đầu (có mũi tên) của link là member

L 2 ASG

ENO, PNO, RESP, DUR

 Lực lượng của từng quan hệ: card(R)

Distributed DBMS

Page 5. 16

 Thông tin về CDSL

Phân mảnh ngang nguyên thủy PHF – Yêu cầu thông tin

 simple predicates : Cho R[A1, A2, …, An], vị từ đơn pj là

pj : Ai Value

với {=,<,≤,>,≥,≠}, ValueDi và Di là domain của Ai. Với quan hệ R, chúng ta định nghĩa Pr = {p1, p2, …,pm} Ví dụ: các vị từ đơn giản

 Thông tin về ứng dụng

 minterm predicates : Cho R và Pr={p1, p2, …,pm}

định nghĩa M={m1,m2,…,mr} là

M={ mi|mi = pjPrpj* }, 1≤j≤m, 1≤i≤z

với pj* = pj hay pj* = ¬(pj).

Distributed DBMS

Page 5. 17

PNAME = "Maintenance" BUDGET ≤ 200000

Phân mảnh ngang nguyên thủy PHF – Yêu cầu về thông tin

Ví dụ: minterm predicates

m1: PNAME="Maintenance" BUDGET≤200000

m2: NOT(PNAME="Maintenance") BUDGET≤200000

m3: PNAME= "Maintenance" NOT(BUDGET≤200000)

m4: NOT(PNAME="Maintenance") NOT(BUDGET≤200000)

Distributed DBMS

Page 5. 18

Phân mảnh ngang nguyên thủy PHF – yêu cầu về thông tin

 Độ tuyển hội sơ cấp: minterm selectivities:

sel(mi)  Số các bộ (tuple) của quan hệ được câu truy vấn truy

 Thông tin ứng dụng

 Tần số truy cập: access frequencies: acc(qi)

 Tần số truy cập dữ liệu của ứng dụng qi.

 Cũng có thể xác định tần số truy cập cho minterm

cập. Câu truy vấn được chỉ định bằng minterm predicate mi.

Distributed DBMS

Page 5. 19

predicate.

Phân mảnh ngang nguyên thủy Primary Horizontal Fragmentation

Định nghĩa :

(R ), 1 ≤ j ≤ w Rj = Fj

Do vậy,

Với Fj là công thức chọn, thích hợp là minterm predicate.

Distributed DBMS

Page 5. 20

Phân mảnh ngang Ri của quan hệ R gồm tất cả các bộ của R thỏa minterm predicate mi.  Cho tập các minterm predicates M, có nhiều phân mảnh ngang của quan hệ R ứng với nhiều minterm predicates. Tập các phân mảng ngang cũng được gọi là minterm fragments.

Phân mảnh ngang nguyên thủy PHF – Thuật toán

Quan hệ R, tập các vị từ đơn Pr

Cho: Kết quả: Tập các mảnh của R = {R1, R2,…,Rw}

thỏa quy tắc phân mảnh.

Yêu cầu :

Pr phải đầy đủ (complete) xem slide tiếp theo

Pr phải tối tiểu (minimal)

Distributed DBMS

Page 5. 21

Tính đầy đủ của các Simple Predicates

 Tập các simple predicates Pr được gọi là đầy đủ nếu và chỉ nếu các truy cập đến các bộ (tuple) của các mảnh hội tối thiểu (minterm fragments) được định nghĩa theo Pr phải thỏa yêu cầu với một ứng dụng bất kỳ, hai bộ của cùng một minterm fragment phải có cùng xác suất truy cập

Cho PROJ[PNO,PNAME,BUDGET,LOC], trên quan hệ này có hai ứng dụng.

(1) (2)

Tìm các kinh phí của từng đề án tại từng vị trí. Tìm các đề án có kinh phí nhỏ hơn $200000.

Distributed DBMS

Page 5. 22

 Ví dụ :

Tính đầy đủ của các Simple Predicates

Theo (hình 5.8 trang 124 sách GK),

Pr={LOC=“Montreal”,LOC=“New York”,LOC=“Paris”}

Là không đầy đủ vì ứng dụng (2). Xác suất truy vấn hai bộ P2,P3 là khác nhau trong mảnh PROJ2

Ta cần sửa đổi

Pr ={LOC=“Montreal”,LOC=“New York”,LOC=“Paris”,

BUDGET≤200000,BUDGET>200000}

Thì Pr đầy đủ.

Distributed DBMS

Page 5. 23

Tính tối tiểu của vị từ đơn

mảnh f thành các mảnh con fi và fj) thì cần phải có một ứng dụng truy cập fi và fj với các xác suất trên các bộ của mảnh đó là khác nhau. Nói cách khác, simple predicate phải liên ứng (relevant) với việc tạo ra phân mảnh.

 Để một vị tự phát sinh phân mảnh, (vd, biến

ứng thì Pr is tối tiểu (minimal).

acc(mi): tần số truy cập của ứng dụng

≠

acc(mi) ––––– card(fi)

acc(mj) ––––– card(fj)

Distributed DBMS

Page 5. 24

 Nếu tất cả các predicates của tập Pr đều có liên

Tính cực tiểu của vị từ đơn

Ví dụ :

BUDGET≤200000,BUDGET>200000}

Là tối tiểu (ngoài ra nó còn đầy đủ).

Tuy vậy, nếu thêm

Đầy đủ: xác suất truy cập các bộ giống nhau

Pr ={LOC=“Montreal”,LOC=“New York”, LOC=“Paris”,

Thì Pr không cực tiểu vì vị từ này không có liên ứng với Pr (không có ứng dụng nào truy cập khác nhau trên các mảnh được tạo ra).

Tối tiểu: các vị từ đều có liên đới.

Liên đới: có ứng dụng truy cập khác nhau trên các mảnh tạo ra.

Distributed DBMS

Page 5. 25

PNAME = “Instrumentation”

Thuật toán COM_MIN

quan hệ R và tập các vị từ Pr Cho: Kết quả: Tập đầy đủ và tối tiểu các vị từ đơn Pr'

cho Pr

Quy tắc 1: Quan hệ hay mảnh được phân thành ít nhất là hai phần khác nhau và được ít nhất một ứng dụng truy cập các bộ với xác suất khác nhau.

Distributed DBMS

Page 5. 26

Thuật toán COM_MIN

Khởi tạo :

 Tìm pi Pr sao cho pi phân hoạch R theo quy tắc 1 ; Pr Pr – pi ; F fi  Gọi Pr' = pi Lặp lại việc thêm các vị từ vào Pr' cho đến khi

nó đầy đủ

 Tìm pj Pr sao cho pj phân hoạch fk được định

nghĩa theo minterm predicate trên Pr' theo quy tắc 1

 Đặt Pr' = Pr'  pi ; Pr Pr – pi; F  F  fi  Nếu pk Pr' là không liên ứng thì

Distributed DBMS

Page 5. 27

Pr'  Pr' – pk F  F – fk

Thuật toán PHORIZONTAL

Dùng COM_MIN để phân mảnh. Nhập: Xuất:

quan hệ R và tập các vị từ đơn Pr tập các minterm predicates M ấn định cách phân mảnh quan hệ R.

 Pr'  COM_MIN (R,Pr)  Xác định tập M các minterm predicates  Xác định tập I các phép kéo theo giữa các pi  Pr  Khử các minterms mâu thuẫn khỏi M

Distributed DBMS

Page 5. 28

Phân mảnh ngang nguyên thủy PHF – Ví dụ (1/2)

 Ứng dụng: Kiểm tra thông tin lương và quyết định tăng

lương.

 Các bản ghi của Nhân viên được lưu ở 2 vị trí  ứng dụng chạy ở 2 vị trí mỗi nơi xử lý các mẫu tin có lương thấp hơn hay bằng 30000 và một nơi khác xử lý các mẫu tin có lương cao hơn 30000.

 Các vị từ đơn được dùng để phân hoạch quan hệ PAY là:

 Cho các quan hệ ứng viên: PAY và PROJ.  Phân mảnh quan hệ PAY

p1 : SAL ≤ 30000 p2 : SAL > 30000 Thuật toán COM-MIT Pr={p1, p2} Với i = 1 , ta tìm được p1 thỏa quy tắc 1: phân quan hệ PAY

Distributed DBMS

Page 5. 29

thành 2 phần là phần thỏa SAL ≤ 30000 và phần không thỏa SAL ≤ 30000, hai phần này được truy cập khác nhau bởi ứng dụng.

Phân mảnh ngang nguyên thủy PHF – Ví dụ (2/2)

Pr‘ <- p1 Pr = {p2} F ={f1} , f1 là mảnh hội sơ cấp theo p1 Trong Pr còn p2 , nhưng p2 không thể phân hoạch mảnh

 Các Minterm predicates

f1 do đó Pr‘ = { p1 } là đầy đủ và tối thiểu

Distributed DBMS

Page 5. 30

m1 : (SAL ≤ 30000) m2 : NOT(SAL ≤ 30000)  (SAL > 30000)

PHF – Ví dụ: phân mảnh ngang cho quan hệ PAY

PAY1 PAY2

SAL SAL TITLE TITLE

Mech. Eng. 27000 Elect. Eng. 40000

Distributed DBMS

Page 5. 31

Programmer 24000 Syst. Anal. 34000

PHF – Ví dụ phân mảnh nganh quan hệ PROJ

 Các ứng dụng:

 Tìm tên và kinh phí của các đề án theo vị trí -location

 Truy cập thông tin đề án theo kinh phí ( budget )

Một ví trí truy cập ≤ 200000, vị trí khác truy cập

(LOC) Được phát sinh ỏ 3 vị trí

>200000  Các vị từ đơn  Cho ứng dụng (1)

p1 : LOC = “Montreal” p2 : LOC = “New York” p3 : LOC = “Paris”  Cho ứng dụng (2)

Distributed DBMS

Page 5. 32

p4 : BUDGET ≤ 200000 p5 : BUDGET > 200000

Phân mảnh ngang nguyên thủy PHF – Ví dụ

 Dùng thuật toán COM-MIN ta có  Pr = Pr' = {p1,p2,p3,p4,p5}

 Phân mảnh quan hệ PROJ tiếp theo

 Minterm fragments còn lại sau khi khử

m1 : (LOC = “Montreal”)  (BUDGET ≤ 200000)

m2 : (LOC = “Montreal”)  (BUDGET > 200000)

m3 : (LOC = “New York”)  (BUDGET ≤ 200000)

m4 : (LOC = “New York”)  (BUDGET > 200000)

m5 : (LOC = “Paris”)  (BUDGET ≤ 200000)

m6 : (LOC = “Paris”)  (BUDGET > 200000)

Distributed DBMS

Page 5. 33

Phân mảnh ngang nguyên thủy PHF – Ví dụ

PNO PNAME

BUDGET

LOC

PNO PNAME

BUDGET

LOC

P2

135000 New York

P1

Instrumentation 150000 Montreal

Database Develop.

PROJ2 PROJ1

PNO PNAME

BUDGET

LOC

PNO PNAME

BUDGET

LOC

P3 CAD/CAM

250000

New York

P4

Maintenance

310000

Paris

Distributed DBMS

Page 5. 34

PROJ4 PROJ6

Phân mảnh ngang nguyên thủy PHF – Tính đúng đắn

 Tình đầy đủ

 Do Pr' là đầy đủ và tối tiểu, các vị từ chọn là đầy đủ

 Tái tạo

 Nếu quan hệ R được phân mảnh thành FR = {R1,R2,…,Rr}

 Rời nhau

 Các minterm predicates làm cơ sở cho phân mảnh cần phải

R = Ri FR Ri

Distributed DBMS

Page 5. 35

rời nhau từng đôi.

Phân mảnh ngang được suy Derived Horizontal Fragmentation

 Mỗi link là một equijoin.  Có thể hiện thực Equijoin bằng semijoins.

SKILL

TITLE, SAL

Quan hệ nằm tại đuôi của link là owner và qhệ nằm tại đầu (có mũi tên) của link là member

L1

EMP

PROJ

ENO, ENAME, TITLE

PNO, PNAME, BUDGET, LOC

Member(L1)= EMP

L2

L3

ASG

ENO, PNO, RESP, DUR

Distributed DBMS

Page 5. 36

 Được xác định theo quan hệ member của link dựa trên phép chọn được chỉ định trên owner của nó .

Phân mảnh ngang được suy DHF – Định nghĩa

Chon link L với owner(L)=S và member(L)=R, các mảnh ngang được suy của R được định nghĩa như sau:

Ri = R

F Si, 1≤i≤w

Với w là số lớn nhất các mảnh được xác định trên R và

(S) , Si là các phân mảnh ngang của owner

Si = Fi

Với Fi là công thức theo đó xác định phân mảnh ngang nguyên thủy Si.

Distributed DBMS

Page 5. 37

Phân mảnh ngang được suy DHF – Ví dụ

Given link L1 where owner(L1)=SKILL and member(L1)=EMP

SKILL

TITLE, SAL

where

L1

EMP

EMP1 = EMP SKILL1 EMP2 = EMP SKILL2

ENO, ENAME, TITLE

SKILL1 = SAL≤30000(SKILL) SKILL2 = SAL>30000(SKILL)

ENO

ENAME

TITLE

ENO

ENAME

TITLE

E3 E4 E7

A. Lee J. Miller R. Davis

Mech. Eng. Programmer Mech. Eng.

E1 E2 E5 E6 E8

J. Doe M. Smith B. Casey L. Chu J. Jones

Elect. Eng. Syst. Anal. Syst. Anal. Elect. Eng. Syst. Anal.

Distributed DBMS

Page 5. 38

EMP1 EMP2

Phân mảnh ngang được suy DHF – Tính đúng đắn

 Toàn vẹn tham chiếu  Cho R là quan hệ member của link có owner là quan

hệ S được phân mảnh thành FS = {S1, S2, ..., Sn}. Ngoài ra gọi A là thuộc tính kết nối giữa R và S. Thì với từng bộ t của R, tồn tại bộ t' của S sao cho

t[A]=t'[A]

 Tính đầy đủ

 Giống phân mảnh ngang nguyên thủy.

 Tái tạo

 Chi có join graphs giữa owner và các member

fragments.

Distributed DBMS

Page 5. 39

 Rời nhau

Phân mảnh dọc Vertical Fragmentation

Distributed DBMS

Page 5. 40

Phân mảnh dọc Vertical Fragmentation

 Phương pháp luận thiết kế ( bài ôn về PTH, thiết kế

CSDL)

 Gom cụm vật lý

 Đã được nghiên cứu trong ngữ cảnh tập trung

Hai tiếp cận:

 nhóm

 Các thuộc tính tới phân mảnh

 tách

 Quan hệ tới phân mảnh

Distributed DBMS

Page 5. 41

 Khó hơn phân mảnh ngang vì có nhiều cách.

Phân mảnh ngang Vertical Fragmentation

 Các mảnh chồng nhau Overlapping fragments

 Gom nhóm ( grouping )

 Các mảnh không chồng nhau

 Tách ( splitting )

Ta không xem xét các thuộc tính khóa được nhân bản là có

chồng nhau.

Tiện lợi:

Dễ ép thỏa các Phụ thuộc hàm

Distributed DBMS

Page 5. 42

(kiểm tra ràng buộc...)

VF – Yêu cầu thông tin

 Các ái lực thuộc tính (Attribute affinities)

 Độ đo phản ánh các thuộc tính quan hệ gần nhau  Nhận được từ dữ liệu sử dụng ban đầu

 Giá trị sử dụng thuộc tính (Attribute usage values)  Cho tập các truy vấn Q = {q1, q2,…, qq} chạy trên quan

 Thông tin ứng dụng

hệ R[A1, A2,…, An],

use(qi,Aj) =

 1 nếu thuộc tính Aj được tham chiếu bới truy vấn qi  0 ngược lại 

Distributed DBMS

Page 5. 43

use(qi,•) được định nghĩa tương ứng

VF – Định nghĩa use(qi,Aj)

q2: SELECT PNAME,BUDGET

FROM PROJ

Xét 4 truy vấn cho quan hệ PROJ q1: SELECT BUDGET FROM PROJ WHERE PNO=Value

q4: SELECT SUM(BUDGET)

q3: SELECT PNAME FROM PROJ WHERE LOC=Value

FROM PROJ WHERE LOC=Value

Gọi A1= PNO, A2= PNAME, A3= BUDGET, A4= LOC A2

A4 A1 A3

q1 1 0 0 1

0 1 1 0

q2 q3 0 1 0 1

Distributed DBMS

Page 5. 44

1 0 0 1 q4

VF – Độ đó ái lực aff(Ai,Aj)

Độ đo ái lực thuộc tính giữa 2 thuộc tính Ai và Aj của quan hệ R[A1, A2, …, An] ứng với tập quan hệ Q = (q1, q2, …, qq) được định nghĩa như sau:

all queries that access Ai and Aj

(query access) aff (Ai, Aj) 

all sites

Distributed DBMS

Page 5. 45

access frequency of a query  query access  access execution

VF – tính aff(Ai, Aj)

Giả sử từng truy vấn trong ví dụ trước truy cập

trong từng lần thực hiện.

Giả định tần số truy cập

S1 S2 20 15 q1 S3 10

Thì

5 0 0

aff(A1, A3) = 15*1 + 20*1+10*1

25 25 25 q 2 q3

= 45 ( dòng q1) Các ma trận ái lực thuộc tính AA is

1

2

0 3 0 q4

3

5 53 45

4

Distributed DBMS

Page 5. 46

A A A A 4 3 2 1 0 45 0 45 5 75 0 80 3 3 78 0 75 A A A A

VF – Thuật toán gom cụm

của thuộc tính để tạo các cụm có các thuộc tính ứng với cụm có độ ái lực cao hơn cụm khác

 Lấy ma trận ái lực AA và tổ chức lại các thứ tự

 Thuật toán năng lượng liên kết - Bond Energy Algorithm (BEA) được dùng để gom cụm các thực thể. BEA tìm thứ tự các thực thể ( trong trường hợp này là các thuộc tính) sao cho độ đo ái lực toàn cục sau

AM  (affinity of Ai and Aj with their neighbors)

i

j

là cực đại.

Distributed DBMS

Page 5. 47

Thuật toán năng lượng liên kết Bond Energy Algorithm

Nhập: Ma trận AA

Xuất: Ma trận ái lực gom cụm CA là một sắp xếp

của các hoán vị AA

Khởi tạo: Đặt và cố định một trong các cột của AA

vào CA.

Lặp: Đặt n-i cột còn lại vào i+1 vị trí còn lại trong ma trận CA. Đối với từng cột, chọn vị trí đóng góp (contri bution) lớn nhất vào độ đo ái lực toàn cục.

Sắp thứ tự dòng:Sắp xếp các dòng theo thứ tự cột.

Distributed DBMS

Page 5. 48

Thuật toán năng lượng liên kết Bond Energy Algorithm

Vị trí “tốt nhất”? Xác định mức đóng góp của bố trí:

cont(Ai, Ak, Aj) = 2bond(Ai, Ak)+2bond(Ak, Al) –2bond(Ai, Aj)

Với

n

aff(Az,Ax)aff(Az,Ay) bond(Ax,Ay) =



z 1

Distributed DBMS

Page 5. 49

BEA – Ví dụ

Xét ma trận AA và ma trận tương ứng CA sau đây với A1 và A2 đã được đặt. Đặt A3:

A

A

2

2

3

4

1

5 5

A1 0 80

2

CA =

AA =

3

5 75

5 75

53 3

45 0 45 0

A A 1 0 45 80 0 45 0

A 0 75 3 78

A A A A

4

Thứ tự (0-3-1) :

Thứ tự (1-3-2) :

cont(A0,A3,A1) = 2bond(A0 , A3)+2bond(A3 , A1)–2bond(A0 , A1) = 2* 0 + 2* 4410 – 2*0 = 8820

cont(A1,A3,A2) = 2bond(A1 , A3)+2bond(A3 , A2)–2bond(A1,A2)

Thứ tự (2-3-4) :

= 2* 4410 + 2* 890 – 2*225 = 10150

Distributed DBMS

Page 5. 50

cont (A2,A3,A4) = 1780

BEA – Ví dụ

Do vậy ma trận CA có dạng

A1 A3 A2

45 45 0

0 5 80

45 53 5

Distributed DBMS

Page 5. 51

0 3 75

BEA – Ví dụ

Sau khi đặt A4, dạng cuối cùng của ma trận CA (sau khi tổ chức dòng) là

A A

1 45

2 0

4 0

1

A AA 3 45

3

A 45 53 5 3

2

A 0 5 80 75

4

Distributed DBMS

Page 5. 52

A 0 3 75 78

VF – Thuật toán

Cách chia tập các thuộc tính gom cụm {A1, A2, …, An} thành hai (hay nhiều hơn) các tập {A1, A2, …, Ai} và {Ai, …, An} sao cho không có (hay có tối thiểu) các ứng dụng truy cập cả hai (hay nhiều hơn một) của các tập hợp.

… . . . Am A1 A2 A3 Ai Ai+1

A1 A2

TA

Ai

Ai+1

BA

Distributed DBMS

Page 5. 53

Am

VF – Algorithm

Định nghĩa

TQ = tập các ứng dụng chỉ truy cập TA BQ = tập các ứng dụng chỉ truy cập BA OQ = tập các ứng dụng chỉ truy cập vừa TA và BA

và

CTQ = tổng số các truy cập đến các thuộc tính bởi các ứng dụng

chỉ truy cập TA

CBQ = tổng số các truy cập đến thuộc tính bởi ứng dụng chỉ

truy cập BA

COQ = tổng số các truy cập đến thuộc tính bởi ứng dụng truy

cập cả TA và BA

Sau đó tìm điểm dọc theo đường chéo làm cực đại

CTQCBQCOQ2

Distributed DBMS

Page 5. 54

VF – Algorithm

Có hai vấn đề:

 Tạo Cluster ở điểm giữa ma trận CA

 Dịch lên một dòng và dịch trái một cột, áp dụng thuật toán

 Làm điều này cho tất cả các dịch chuyển khả dĩ

 Chi phí O(m2)

 Nhiều hơn 2 clusters

 Phân hoạch theo m-cách

 Thử với 1, 2, …, m–1 điểm tách dọc theo đường chéo và

tìm điểm phân hoạch tốt nhất

 Chi phí O(2m)

Distributed DBMS

Page 5. 55

tìm điểm tốt nhất cho từng điểm

VF – Correctness

A relation R, defined over attribute set A and key K, generates the

vertical partitioning FR = {R1, R2, …, Rr}.

 Completeness

 The following should be true for A:

A = ARi

 Reconstruction

 Reconstruction can be achieved by

R = K

Ri Ri FR

 Disjointness

 TID's are not considered to be overlapping since they are maintained

 Duplicated keys are not considered to be overlapping

Distributed DBMS

Page 5. 56

by the system

Phân mảnh hỗn hợp Hybrid Fragmentation

R 

HF

HF

R1 

VF  R11

VF  R12

R2  VF VF   R23 R22

VF  R21

Distributed DBMS

Page 5. 57

Bố trí phân mảnh theo các vị trí

 Phát biểu bài toán

mảnh các vị trí trên mạng ứng dụng, truy vấn

F = {F1, F2, …, Fn} S ={S1, S2, …, Sm} Q = {q1, q2,…, qq} Tìm phân bố “tối ưu” của F trên S.

 Tối ưu

 Chi phí cực tiểu

 Truyền thông + bộ nhớ + xử lý ( đọc & cập nhật)  Chi phí theo thời gian (thông thường)

 Công năng

Thời gian đáp ứng và/hay kết quả

 Ràng buộc

 Ràng buộc trên từng vị trí (bộ nhớ & xử lý)

Distributed DBMS

Page 5. 58

Cho :

Yêu cầu thông tin

 Thông tin về CSDL

 Sựa lựa chọn các bộ truy vấn của các mảnh  Kích thước của mảnh

 Thông tin về ứng dụng

 Kiểu truy cập và số truy cập  Tính cục bộ của truy cập

 Thông tin về mạng truyền thông  Đơn giá lưu trữ dữ liệu tại vị trí  Đơn giá xử lý tại một vị trí  Thông tin về hệ thống máy tính

 Băng thông  latency  Tổn phí truyền thông

Distributed DBMS

Page 5. 59

Cấp phát

Cấp phát tập tin(FAP) so với cấp phát CSDL (DAP):

 Các phân mảnh không phải là các tập tin riêng rẻ

 Cần duy trì các mối quan hệ

 Truy cập đến CSDL thường phức tạp hơn

 Không thể áp dụng mô hình truy cập tập tin từ xa

 Mối quan hệ giữa cấp phát và xử lý truy vấn

 Cần xem xét việc ép thỏa ràng buộc toàn vẹn

 Cần xem xét kiểm soát đồng hành

Distributed DBMS

Page 5. 60

Yêu cầu thông tin

 Thông tin về CSDL

 Sựa lựa chọn các bộ truy vấn của các mảnh  Kích thước của mảnh

 Thông tin về ứng dụng

 Số các truy cập đọc của truy vấn đến một mảnh  Số các truy cập cập nhật của truy vấn đến một mảnh  Ma trận biểu thị các truy vấn cập nhật mảnh  Ma trận tương tự để đọc  Vị trí nguyên thủy của từng truy vấn

 Thông tin vị trí

 Đơn giá lưu trữ dữ liệu tại vị trí  Đơn giá xử lý tại vị trí

 Thông tin về mạng

 Chi phí truyền thông/khung sườn (frame) giữa 2 vị trí  Kich thước khung sườn

Distributed DBMS

Page 5. 61

Mô hình cấp phát

Dạng tổng quát

min(Total Cost)

thỏa mãn

ràng buộc về thời gian đáp ứng ràng buộc về bộ nhớ ràng buộc xử lý

Biến quyết định

xij 

1 nếu mảnh Fi được lưu ở vị trí Sj   0 ngược lại 

Distributed DBMS

Page 5. 62

Mô hình cấp phát

 Tổng chi phí

all queries

query processing cost 

all fragments

cost of storing a fragment at a site

all sites

 Chi phí bộ nhớ (của Fj tại vị trí Sk)

 Chi phí xử lý truy vấn (cho một truy vấn)

processing component + transmission component

Distributed DBMS

Page 5. 63

(unit storage cost at Sk)  (size of Fj) xjk

Mô hình cấp phát

 Chi phí xử lý truy vấn Processing component

 Access cost

access cost + integrity enforcement cost + concurrency control cost

all fragments

(no. of update accesses+ no. of read accesses) 

all sites

 Integrity enforcement and concurrency control costs

 Can be similarly calculated

Distributed DBMS

Page 5. 64

xijlocal processing cost at a site

Mô hình cấp phát

 Chi phí xử lý truy vấn Thành phần truyền thông

 Cost of updates

Chi phí xử lý cập nhật + chi phí xử lý đọc

all fragments

update message cost 

all sites

all fragments

acknowledgment cost

all sites

 Retrieval Cost

all fragments

cost of retrieval command  ( minall sites

Distributed DBMS

Page 5. 65

cost of sending back the result)

Mô hình cấp phát

 Thời gian đáp ứng

 Ràng buộc

execution time of query ≤ max. allowable response time

 Ràng buộc bộ nhớ (for a site)

for that query

all fragments

storage requirement of a fragment at that site 

 Ràng buộc xử lý (for a site)

storage capacity at that site

all queries

processing load of a query at that site 

Distributed DBMS

Page 5. 66

processing capacity of that site

Mô hình cấp phát

 FAP is NP-complete

 DAP also NP-complete

 Các phương pháp giải

 Vị trí kho hoàng duy nhất (for FAP)

 Bài toán xếp ba lô (knapsack problem)

 Kỹ thuật nhánh và cận (branch and bound

techniques)

 Bài toán luồng (network flow)

Distributed DBMS

Page 5. 67

 Các Heuristics dựa trên

Mô hình cấp phát

 Giá đình tất các các phân hoạch ứng viên đều đã biết;

chọn phân hoạch “tốt nhất”

 Bỏ đi các đầu tiên

 Trượt cửa sổ trên các mảnh

Distributed DBMS

Page 5. 68

 Cố gắng giảm không gian lời giải