Xem mẫu
- Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XIV về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR), TP. HCM, ngày 23-24/12/2021
DOI: 10.15625/vap.2021.0083
MỘT SỐ TÍNH CHẤT CỦA LƯỢC ĐỒ KHỐI CÂN BẰNG
TRÊN KHỐI VÀ LÁT CẮT
Trịnh Đình Thắng1, Đỗ Thị Lan Anh1, Trần Minh Tuyến2, Nguyễn Thị Hà3
1
Đại học Sư phạm Hà Nội 2, 2Đại học Công đoàn, 3Trường Trung học Phổ thông Nguyễn Viết Xuân
thangdhsp2@hpu2.edu.vn, dothilananh@hpu2.edu.vn, tuyentm@dhcd.edu.vn, hant.nvx@gmail.com
TÓM TẮT: Bài báo này phát biểu và chứng minh một số tính chất của lược đồ khối cân bằng khi thực hiện các phép toán trên
các lược đồ khối và lược đồ lát cắt. Mối quan hệ giữa lược đồ khối cân bằng với giao của các khóa trên các lược đồ khối và lát cắt.
Khi các khối suy biến thành quan hệ thì các tính chất của lược đồ khối cân bằng lại trở thành các tính chất của lược đồ quan hệ cân
bằng. Ngoài ra một số tính chất của mối quan hệ giữa lược đồ khối cân bằng và khóa cũng được phát biểu và chứng minh ở đây.
Từ khóa: Lược đồ khối cân bằng, lược đồ lát cắt, khóa của lược đồ khối, lược đồ cân bằng và khóa.
I. GIỚI THIỆU
Mô hình dữ liệu dạng khối là một mở rộng của mô hình dữ liệu quan hệ. Việc mở rộng sang mô hình dữ liệu
dạng khối giúp cho việc biểu diễn dữ liệu động, có cấu trúc phi tuyến và đáp ứng nhu cầu thực tế tốt hơn. Tuy nhiên,
việc chuyển từ biểu diễn dữ liệu phẳng sang dạng khối cũng sẽ phức tạp hơn. Để xây dựng một khối dữ liệu tốt trên
thực tế thì việc xác định khóa của lược đồ khối là vô cùng quan trọng. Trên khối thì số thuộc tính chỉ số nhiều hơn hẳn
so với số thuộc tính của quan hệ nên việc xác định khóa của nó cũng phức tạp hơn. Từ khó khăn này mà việc nghiên
cứu để tìm ra cách xác định khóa của khối nhanh hơn, đơn giản hơn là điều cần thiết. Việc nghiên cứu các tính chất của
lược đồ khối cân bằng cũng nằm trong hướng nghiên cứu này. Việc chuyển từ lược đồ khối ban đầu sang lược đồ khối
cân bằng sẽ giúp xác định khóa của lược đồ khối ban đầu nhanh hơn và dễ hơn vì khi đó số thuộc tính chỉ số đã giảm đi
đáng kể.
Các nghiên cứu trước đây [1], [5] đã đưa ra khái niệm về lược đồ khối cân bằng và chứng minh một số tính chất
cơ bản của khái niệm này. Tuy nhiên, việc nghiên cứu về mối quan hệ giữa tính cân bằng với các phép toán trên lược
đồ khối và khóa của khối còn chưa được quan tâm nhiều. Nội dung của bài báo này phát biểu và chứng minh một số
kết quả mới về mối quan hệ đó. Các kết quả nghiên cứu về lược đồ khối cân bằng sẽ giúp ích nhiều cho việc xây dựng
các khối dữ liệu trên thực tế.
II. MÔ HÌNH DỮ LIỆU DẠNG KHỐI
A. Khối, lát cắt của khối
Định nghĩa II.1 [1]
Gọi R = (id; A1, A2,..., An) là một bộ hữu hạn các phần tử, trong đó id là tập chỉ số hữu hạn khác rỗng, Ai
(i=1..n) là các thuộc tính. Mỗi thuộc tính Ai (i=1..n) có miền giá trị tương ứng là dom(Ai). Một khối r trên R, kí hiệu
r(R) gồm một số hữu hạn phần tử mà mỗi phần tử là một họ các ánh xạ từ tập chỉ số id đến các miền trị của các thuộc
tính Ai (i=1..n).
Nói một cách khác:
t∈ r(R) ⇔ t = { ti : id → dom(Ai)}i=1..n .
Ta kí hiệu khối đó là r(R) hoặc r(id; A1, A2,..., An ), đôi khi nếu không sợ nhầm lẫn ta kí hiệu đơn giản là r.
Định nghĩa II.2 [1]
Cho R = (id; A1, A2,..., An ), r(R) là một khối trên R. Với mỗi x∈ id ta kí hiệu r(Rx) là một khối với Rx = ({x};
A1, A2,..., An ) sao cho:
tx∈ r(Rx) ⇔ tx = {tix = ti } i=1..n , t∈ r(R), t = { ti : id → dom(Ai)}i=1..n .
x
ở đây tax(x) = ti(x) , i =1..n.
Khi đó r(Rx) được gọi là một lát cắt trên khối r(R) tại điểm x.
B. Phụ thuộc hàm
Sau đây, để cho đơn giản ta sử dụng các kí hiệu:
x(i) = (x; Ai ) ; id(i) = {x(i) | x ∈ id}.
Ta gọi x(i) (x ∈ id, i = 1..n) là các thuộc tính chỉ số của lược đồ khối R = (id; A1,A2,...,An ).
- 406 MỘT SỐ TÍNH CHẤT CỦA LƯỢC ĐỒ KHỐI CÂN BẰNG TRÊN KHỐI VÀ LÁT CẮT
Định nghĩa II.3 [2] n
Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R; X, Y ⊆ id ( i ) , X → Y là kí hiệu một phụ thuộc hàm.
i =1
Một khối r thoả X → Y nếu ∀ t1, t2 ∈ R sao cho t1(X) = t2(X) thì t1(Y) = t2(Y).
Giả sử ta có: f: X → Y ∈ F là một phụ thuộc hàm, khi đó ta kí hiệu:
LS(f) = X, RS(f) = Y,
∀ f ∈ F: LS(F) = LS ( f ) , RS(F) = RS ( f ).
f∈F f∈F
Định nghĩa II.4 [2]
Cho lược đồ khối α=(R,F), R=(id; A1, A2,..., An), F là tập các phụ thuộc hàm trên R.
Khi đó bao đóng của F kí hiệu F+ được xác định như sau:
F+ = { X → Y | F ⇒ X → Y } .
Nếu X = {x(m)} ⊆ id(m) , Y = {y(k)} ⊆ id(k) thì ta kí hiệu phụ thuộc hàm X → Y đơn giản là x(m) → y(k) .
Khối r thoả x(m) → y(k) nếu ∀ t1, t2 ∈ r sao cho t1(x(m)) = t2(x(m)) thì t1(y(k)) = t2(y(k)) .
Trong đó: t1(x(m)) = t1(x; Am), t2(x(m)) = t2(x; Am) ,
t1(y(k)) = t1(y; Ak ), t2(y(k)) = t2(y; Ak ) .
C. Bao đóng của tập thuộc tính chỉ số
Định nghĩa II.5 [3]
n
Cho lược đồ khối α=(R,F), R=(id; A1, A2,..., An ), F là tập các phụ thuộc hàm trên R. Với mỗi X ⊆ id (i ) , ta
định nghĩa bao đóng của X đối với F kí hiệu X+ như sau: i =1
X+ = {x(i) , x ∈ id, i = 1..n | X → x(i) ∈ F+ } .
Cho R = (id; A1, A2,..., An ), ta kí hiệu các tập phụ thuộc hàm trên R:
Fh ⊆ { X → Y | X = x (i )
, Y = x
j∈B
( j)
, A, B ⊆ {1,2,...,n} và x ∈ id },
i∈ A
n n
Fhx = Fh ∩ x
i =1
(i )
= { X → Y ∈ Fh | X, Y ⊆ x (i )
}.
i =1
D. Khoá của lược đồ khối α = (R,F)
Định nghĩa II.6 [4]
n
Cho lược đồ khối α = (R,F), R = (id; A1, A2,..., An ), F là tập các phụ thuộc hàm trên R, K ⊆ . K gọi
là khoá của lược đồ khối α nếu nó thoả 2 điều kiện:
id
i =1
(i )
- K → x ∈ F , ∀x ∈ id, i = 1..n.
(i) +
- ∀K’ ⊂ K thì K’ không có tính chất a).
Nếu K là khoá và K ⊆ K’’ thì K’’ gọi là siêu khoá của lược đồ khối R đối với F.
E. Phép dịch chuyển lược đồ khối
Định nghĩa II.7 [4][6]
n
Cho hai lược đồ khối α= (R,F), β = (S,G), X ⊆ id (i ) , X ={x(i), x∈ id, i ∈ A}, A ⊆ {1,2, ..., n}. Ta nói lược
i =1
đồ β nhận được từ lược đồ α qua phép dịch chuyển theo tập thuộc tính X , nếu sau khi loại bỏ các thuộc tính trong X
ở lược đồ α thì ta thu được lược đồ β.
Để kí hiệu phép dịch chuyển từ lược đồ α thành lược đồ β theo tập thuộc tính X ta viết: β = α \ X.
Thao tác loại bỏ X từ lược đồ α thành lược đồ β như sau:
1. Tính S = R \X, R = (id; A1, A2,..., An ), ở đây ta loại bỏ các thuộc tính Ai (i ∈ A) trong R, thủ tục này có độ
phức tạp là O(nk), với k là số phần tử của A. n
2. Với mỗi phụ thuộc hàm từ M->N trong F, với M, N ⊆ id ta tạo một phụ thuộc hàm mới M\X -> N\X
(i )
i =1
trong G.
- Trịnh Đình Thắng, Đỗ Thị Lan Anh, Trần Minh Tuyến, Nguyễn Thị Hà 407
ơ
3. Thủ tục này được kí hiệu là G = F \ X và có độ phức tạp O(mnk) với m là số lượng các phụ thuộc hàm trong F.
Từ đó ta thấy độ phức tạp của phép dịch chuyển β = α \ X = (R\X, F\X) là O(mnk), do vậy nó là tuyến tính theo
chiều dài của dữ liệu vào.
Sau khi thực hiện thủ tục G = F\X thì:
+ Nếu G chứa các PTH tầm thường (dạng X->Y, X ⊇ Y) thì ta loại chúng khỏi G.
+ Nếu G chứa các PTH trùng nhau thì ta loại bớt các PTH này (G không chứa các PTH trùng nhau).
Ta có các nhận xét sau:
Nhận xét II.1:
n
Cho hai lược đồ khối α = (R,F), β = (S,G), X ⊆ id
i =1
(i )
, X ={x(i), x∈ id, i ∈ A}, A ⊆ {1,2, ..., n}. Lược đồ β
nhận được từ lược đồ α qua phép dịch chuyển theo tập thuộc tính X: β = α \ X.
Khi đó, nếu id ={x} thì lược đồ khối α suy biến thành lược đồ quan hệ và phép dịch chuyển theo tập thuộc tính
X trong trường hợp này lại trở thành phép dịch chuyển theo tập thuộc tính X từ lược đồ quan hệ α về lược đồ quan
hệ β trong mô hình dữ liệu quan hệ.
Nhận xét II.2:
n
Cho hai lược đồ khối α = (R, Fh), β = (S, Gh), X ⊆ id
i =1
(i )
, X ={x(i), x∈ id, i ∈ A}, A ⊆ {1,2, ..., n}. Khi đó nếu
lược đồ β nhận được từ lược đồ α qua phép dịch chuyển theo tập thuộc tính X nghĩa là β = α \ X thì:
S = R \ X, Gh = Fh \ X = Fhx \ X.
x∈id n
Từ đó ta có: Ghx = Fhx \ (X ∩ x ), ∀ x∈ id.
i =1
(i )
Như vậy, việc dịch chuyển trên khối trong trường hợp này lại được chuyển về việc dịch chuyển trên các lát cắt,
mà trong mỗi lát cắt thì việc này chính là việc dịch chuyển lược đồ quan hệ trong mô hình dữ liệu quan hệ.
III. LƯỢC ĐỒ KHỐI CÂN BẰNG
A. Lược đồ khối cân bằng
Định nghĩa III.1 [5]
Lược đồ khối α = (R,F), R = (id; A1, A2, ... , An ) được gọi là cân bằng nếu tập phụ thuộc hàm F thỏa mãn hai
tính chất sau:
(i) Hợp của tất cả các vế trái của các phụ thuộc hàm trong F bằng hợp của tất cả các vế phải của nó và
n
bằng id (i ) .
i =1
(ii) F có dạng thu gọn tự nhiên.
Như ta đã biết, F có dạng thu gọn tự nhiên có nghĩa là F thỏa các điều kiện sau:
- F không chứa các phụ thuộc hàm tầm thường, nghĩa là các phụ thuộc hàm có dạng:
X → Y ∈ F và X ⊇ Y.
- Hai vế trái và phải của mọi phụ thuộc hàm trong F không giao nhau:
∀ f ∈ F: LS(f) ∩ RS(f) = ∅ .
- Các vế trái của mọi phụ thuộc hàm trong F khác nhau đôi một, nghĩa là :
∀ f, g ∈ F: LS(f) = LS(g) ⇔ f = g.
Nhận xét III.1:
Cho lược đồ khối α = (R,F), R = (id; A1, A2, ... , An ) là lược đồ cân bằng. Khi đó, nếu id ={x} thì lược đồ khối
cân bằng α suy biến thành lược đồ quan hệ cân bằng trong mô hình dữ liệu quan hệ.
B. Các tính chất của lược đồ khối cân bằng
Mệnh đề III.1: [5]
Cho lược đồ khối α = (R, Fh ), R = (id; A1, A2, ... , An ) là lược đồ cân bằng. Khi đó ∀ x ∈ id, lược đồ của lát cắt
tại điểm x: αx= (Rx, Fhx ) cũng là lược đồ cân bằng.
- 408 MỘT SỐ TÍNH CHẤT CỦA LƯỢC ĐỒ KHỐI CÂN BẰNG TRÊN KHỐI VÀ LÁT CẮT
Mệnh đề III.2: [5]
Cho lược đồ khối α = (R, Fh ), R = (id; A1, A2, ... , An ). Khi đó nếu ∀ x ∈ id, lược đồ của lát cắt tại điểm x: αx=
(Rx, Fhx ) là lược đồ cân bằng thì α = (R, Fh ) cũng là lược đồ cân bằng.
Từ các mệnh đề 2.1 và 2.2 ta rút ra điều kiện cần và đủ sau về lược đồ cân bằng:
Mệnh đề III.3: [5]
Cho lược đồ khối α = (R,Fh ), R = (id; A1, A2, ... , An ). Khi đó α = (R,Fh ) là lược đồ cân bằng khi và chỉ khi
∀ x ∈ id, lược đồ của lát cắt tại điểm x: αx= (Rx, Fhx ) là lược đồ cân bằng.
Mệnh đề III.4: [5]
Cho lược đồ khối α = (R,Fh ), R = (id; A1, A2, ... , An ). Khi đó:
a) Nếu n =1 thì ∀ x ∈ id, αx=(Rx,Fhx ) và α = (R,Fh ) là các lược đồ không cân bằng.
b) Nếu α= (R,Fh ) là lược đồ cân bằng thì giao của các khóa trong lược đồ αx=(Rx,Fhx ), ∀ x∈ id là UI x = ∅ .
c) Nếu α= (R,Fh ) là lược đồ cân bằng thì giao của các khóa trong nó là UI = ∅.
Mệnh đề III.5: [5]
Cho lược đồ khối α = (R,Fh ), R = (id; A1, A2, ... , An ), Fh là tập đầy đủ các phụ thuộc hàm.Lược đồ khối β =
(V,Gh ) là lược đồ khối sau khi chuyển về dạng cân bằng của lược đồ khối α = (R,Fh ). Khi đó, ta có: Key(α) = UI ⊕
Key(β).
IV. KẾT QUẢ NGHIÊN CỨU
A. Tính cân bằng với phép toán các lược đồ khối
Mệnh đề IV.1
Cho các lược đồ khối α1= (R1,Fh1 ), α2= (R2,Fh2 ), R1 = ( id1; A1, A2, ... , An ), R2 = ( id2; A1, A2, ... , An ), n>1, α =
α1 ∪ α2, α’ = α1 ∩ α2 , α= (R,Fh ), α’= (R’,F’h ) , R = ( id1 ∪ id2; A1, A2, ... , An ), R’ = ( id1 ∩ id2; A1, A2, ... , An ), Fh =
Fh1 ∪ Fh2, F’h = Fh1 ∩ Fh2. Khi đó nếu α1, α2 là các lược đồ khối cân bằng thì α , α’ cũng là lược đồ khối cân bằng.
Chứng minh
Theo giả thiết ta có α1= (R1,Fh1 ), R1 = ( id1; A1, A2, ... , An ) là lược đồ khối cân bằng, nên áp dụng kết quả của
mệnh đề II.3 ta suy ra: ∀ x ∈ id1, α1x= (R1x, Fh1x ) là lược đồ khối cân bằng. (1)
Mặt khác, theo giả thiết ta lại có: α2= (R2,Fh2 ), R2 = ( id2; A1, A2, ... , An ) cũng là lược đồ khối cân bằng,
nên áp dụng kết quả của mệnh đề II.3 ta suy ra: ∀ x ∈ id2, α2x= (R2x, Fh2x ) là lược đồ cân bằng. (2)
Từ (1) và (2) ta suy ra:
∀ x ∈ id1 ∪ id2 thì αx = α1x khi x ∈ id1 và αx = α2x khi x ∈ id2 , đều là các lược đồ khối cân bằng.
Thêm nữa:
∀ x ∈ id1 ∩ id2 thì αx = α1x = α2x là các lược đồ khối cân bằng.
Do đó áp dụng tính chất cần và đủ của mệnh đề II.3 ta suy ra α và α’ là các lược đồ khối cân bằng.
Ví dụ IV.1: Cho các lược đồ khối α1= (R1,Fh1 ), α2= (R2,Fh2 ), R1 = ( id1; A1, A2, A3, A4 ), R2 = ( id2; A1, A2,
A3, A4 ), id1 = {x,y}, id2 = {y,z}, Fh1 = { x(1) → x(3)x(4), x(2) → x(3)x(1), x(2) x(3) → x(1), x(4) → x(2), y(1) → y(3)y(4), y(2)
→ y(3)y(1), y(2) y(3) → y(1), y(4) → y(2)}, Fh2 = { y(1) → y(3)y(4), y(2) → y(3)y(1), y(2) y(3) → y(1), y(4) → y(2), z(1) → z(3)z(4),
z(2) → z(3)z(1), z(2) z(3) → z(1), z(4) → z(2)}.
Với các lược đồ khối α1= (R1,Fh1 ), α2= (R2,Fh2 ) được cho như ỏ trên, kiểm tra dễ dàng ta thấy chúng đều thỏa
hai tính chất của lược đồ khối cân bằng. Vậy α1= (R1,Fh1 ), α2= (R2,Fh2 ) là các lược đồ khối cân bằng.
Khi đó ta có: α = α1 ∪ α2, α = (R,Fh ), R = (id1 ∪ id2; A1, A2, A3, A4 ), Fh = Fh1 ∪ Fh2,
R = ({x,y,z}; A1, A2, A3, A4 ),
Fh = { x (1)
→ x x , x(2) → x(3)x(1), x(2) x(3) → x(1), x(4) → x(2), y(1) → y(3)y(4), y(2) → y(3)y(1), y(2) y(3) → y(1),
(3) (4)
y(4)
→ y(2),
z(1) → z(3)z(4), z(2) → z(3)z(1), z(2) z(3) → z(1), z(4) → z(2)}.
- Trịnh Đình Thắng, Đỗ Thị Lan Anh, Trần Minh Tuyến, Nguyễn Thị Hà 409
Kiểm tra lược đồ khối α ta dễ thấy đây là lược đồ khối cân bằng.
Tương tự với lược đồ khối α’= (R’,F’h ) , R’ = ( id1 ∩ id2; A1, A2, A3, A4 ), F’h = Fh1 ∩ Fh2,
R’ = ({y}; A1, A2, A3, A4 ),
F’h = { y(1) → y(3)y(4), y(2) → y(3)y(1), y(2) y(3) → y(1), y(4) → y(2)}.
Kiểm tra lược đồ khối α’ ta cũng dễ dàng thấy đây là lược đồ khối cân bằng.
Vậy ta suy ra α và α’ là các lược đồ khối cân bằng.
Mệnh đề IV.2
Cho các lược đồ khối α1= (R1,Fh1 ), α2= (R2,Fh2 ), …, αk= (Rk,Fhk ), R1 = ( id1; A1, A2, ... , An ), R2 = ( id2; A1,
A2, ...,An ),… ,
k k k
Rk = ( idk; A1, A2, ... , An ), n>1, α = α i , α’ = α
i =1
i , α= (R,Fh ), α’= (R’,F’h ) , R = ( id i ; A1, A2, ... ,
i =1 i =1
An ), R’ =
k k k
( id i ; A1, A2, ... , An ), Fh = F hi , F’h = F
i =1
hi . Khi đó nếu α1, α2,…, αk là các lược đồ khối cân bằng thì
i =1 i =1
α , α’ cũng là lược đồ khối cân bằng.
Chứng minh
Theo giả thiết ta có α1= (R1,Fh1 ), R1 = ( id1; A1, A2, ... , An ) là lược đồ khối cân bằng, nên áp dụng kết quả của
mệnh đề II.3 ta suy ra: ∀ x ∈ id1, α1x= (R1x, Fh1x ) là lược đồ cân bằng. (1)
Mặt khác, theo giả thiết ta lại có: α2= (R2,Fh2 ), R2 = ( id2; A1, A2, ... , An ) cũng là lược đồ khối cân bằng, nên áp
dụng kết quả của mệnh đề II.3 ta suy ra: ∀ x ∈ id2, α2x= (R2x, Fh2x ) là lược đồ cân bằng. (2)
….
Tương tự, theo giả thiết ta có: αk= (Rk,Fhk ), Rk = ( idk; A1, A2, ... , An ) cũng là lược đồ khối cân bằng, nên áp
dụng kết quả của mệnh đề II.3 ta suy ra: ∀ x ∈ idk, αkx= (Rkx, Fhkx ) là lược đồ cân bằng. (k)
Từ (1), (2),…, (k) ta suy ra:
k
∀ x ∈ idi thì αx = αix khi x ∈ idi ,i = 1, 2,…, k đều là các lược đồ khối cân bằng.
i =1
Thêm nữa:
k
∀ x ∈ idi thì αx = αix , i = 1, 2,…, k đều là các lược đồ khối cân bằng.
i =1
Do đó áp dụng tính chất cần và đủ của mệnh đề II.3 ta suy ra α và α’ là các lược đồ khối cân bằng.
Mệnh đề IV.3
Cho các lược đồ khối α1= (R1,Fh1 ), α2= (R2,Fh2 ), R1 = ( id1; A1, A2, ... , An ), R2 = ( id2; A1, A2, ... , An ), n>1, α =
α1 ∪ α2, α= (R,Fh ), R = ( id1 ∪ id2; A1, A2, ... , An ), Fh = Fh1 ∪ Fh2 . Khi đó nếu α1, α2 là các lược đồ khối cân bằng thì:
∀ x ∈ id1 ∪ id2: giao của các khóa trong lát cắt x của lược đồ khối α là UIx = ∅.
Chứng minh
Theo giả thiết ta có α1= (R1,Fh1 ), α2= (R2,Fh2 ), R1 = ( id1; A1, A2, ... , An ), R2 = ( id2; A1, A2, ...,An ) là các lược
đồ khối cân bằng, nên áp dụng kết quả của mệnh đề III.1 ở trên ta suy ra lược đồ khối α là lược đồ khối cân bằng.
Do lược đồ khối α là lược đồ khối cân bằng và ta có:
α= (R,Fh ), R = ( id1 ∪ id2 ; A1, A2, ... , An ),
nên áp dụng kết quả của mệnh đề II.4 ta suy ra:
∀ x ∈ id1 ∪ id2 thì giao của các khóa trong lát cắt x của lược đồ khối α là UIx = ∅.
Mệnh đề IV.4
Cho các lược đồ khối α1= (R1,Fh1 ), α2= (R2,Fh2 ), …, αk= (Rk,Fhk ), R1 = ( id1; A1, A2, ... , An ), R2 = ( id2; A1,
A2, ...,An ),… ,
k
F
i =1
hi
- 410 MỘT SỐ TÍNH CHẤT CỦA LƯỢC ĐỒ KHỐI CÂN BẰNG TRÊN KHỐI VÀ LÁT CẮT
Rk = ( idk; A1, A2, ... , An ), n>1, α = k , α= (R,Fh ), R = ( k
; A1, A2, ... , An ), Fh = . Khi đó nếu αi ,
i=1, 2, …,n i =1
αi id i
i =1
∀ x ∈ idi : giao của các khóa trong lát cắt x của lược đồ khối α là UIx = ∅.
k
là các lược đồ khối cân bằng thì
i =1
Chứng minh
Theo giả thiết ta có α1= (R1,Fh1 ), α2= (R2,Fh2 ), …, αk= (Rk,Fhk ), R1 = ( id1; A1, A2, ... , An ), R2 = ( id2; A1,
A2, ...,An ),
…, Rk = ( idk; A1, A2, ... , An ) là các lược đồ khối cân bằng, nên áp dụng kết quả của mệnh đề III.2 ở trên ta suy
ra lược đồ khối α là lược đồ cân bằng.
Do lược đồ khối α là lược đồ khối cân bằng và ta có:
k
α= (R,Fh ), R = ( id ; A1, A2, ... , An ),
i =1
i
nên áp dụng kết quả của mệnh đề II.4 ta suy ra:
k
∀ x ∈ idi thì giao của các khóa trong lát cắt x của lược đồ khối α là UIx = ∅.
i =1
B. Tính cân bằng với khóa của các lược đồ khối
Mệnh đề IV.5
Cho lược đồ khối α = (R,Fh ), R = (id; A1, A2, ... , An ), n>1, Fh là tập đầy đủ các phụ thuộc hàm. Lược đồ khối β
= (V,Gh ) là lược đồ khối sau khi chuyển về dạng cân bằng của lược đồ khối α = (R,Fh ). Khi đó, ta có:
∀ x ∈ id : Key(αx) = UIx ⊕ Key(βx).
Chứng minh
Theo giả thiết ta có lược đồ khối β = (V,Gh ) là lược đồ sau khi chuyển về dạng cân bằng của lược đồ khối α =
(R,Fh ), R = (id; A1, A2, ... , An ), Fh là tập đầy đủ các phụ thuộc hàm. Do đó áp dụng kết quả của mệnh đề II.5 ta có:
Key(α) = UI ⊕ Key(β), (1)
ở đây UI là giao các khóa trong lược đồ khối α = (R,Fh ).
Mặt khác, theo tính chất của phép dịch chuyển lược đồ khối và tập các khóa trên khối thì từ (1) ta suy ra:
∀ x ∈ id : Key(αx) = UIx ⊕ Key(βx),
ở đây UIx là giao các khóa của lược đồ lát cắt αx.
Ví dụ IV.2: Cho lược đồ khối α = (R,Fh ), R = (id; A1, A2, ... , A6 ), id = {a,b}, Fh = {a(1)a(5)→ a(4), a(2)a(3)→
a a , a(6)→ a(3), a(5)→ a(2), a(5)→ a(3), b(1)b(5)→ b(4), b(2)b(3)→ b(3)b(5), b(6)→ b(3), b(5)→ b(2), b(5)→ b(3)}.
(3) (5)
Áp dụng công thức tính UI trong lược đồ khối α = (R,Fh ), ta có: UI = { a(1)b(1)a(6)b(6)} với UIa = {a(1)a(6)}, UIb =
(1) (6)
{b b },
Sau khi chuyển lược đồ khối α = (R,Fh ) về dạng cân bằng ta được lược đồ khối β = (V,Gh ) với V = {id; A2,
A5}, Gh = { a(2)→ )a(5), a(5)→ a(2), b(2)→ )b(5), b(5)→ b(2)}.
Với lược đồ khối cân bằng β = (V,Gh ) ta thấy ngay: Key(βa) = { a(2)a(5)}, Key(βb) = { b(2),b(5)}.
Áp dụng kết quả của mệnh đề III.5 ta có: ∀ x ∈ {a,b} : Key(αx) = UIx ⊕ Key(βx), do đó:
Key(αa) = {a a } ⊕ { a(2)a(5)} = a(1)a(6)a(2)a(5),
(1) (6)
và Key(αb) = {b(1)b(6)} ⊕ { b(2)b(5)} = b(1)b(6)b(2)b(5).
Mệnh đề IV.6
Cho các lược đồ khối α1= (R1,Fh1 ), α2= (R2,Fh2 ), R1 = ( id1; A1, A2, ... , An ), R2 = ( id2; A1, A2, ... , An ), n>1, α
= α1 ∪ α2,, α= (R,Fh ), R = ( id; A1, A2, ... , An ), id = id1 ∪ id2 , Fh = Fh1 ∪ Fh2 , Fh là các tập phụ thuộc hàm đầy đủ,
id1 ∩ id2 = ∅. Các lược đồ khối β1= (V1,Gh1 ), β2= (V2,Gh2 ) là các lược đồ khối tương ứng sau khi chuyển về dạng cân
bằng của các lược đồ khối α1 và α2, β = β1 ∪ β2. Khi đó ta có:
Key(α) = UI ⊕ Key(β).
- Trịnh Đình Thắng, Đỗ Thị Lan Anh, Trần Minh Tuyến, Nguyễn Thị Hà 411
Chứng minh
Theo giả thiết ta có α1= (R1,Fh1 ), R1 = ( id1; A1, A2, ... , An ), β1= (V1,Gh1 ) là lược đồ khối sau khi chuyển về
dạng cân bằng của lược đồ khối α1, nên áp dụng kết quả của mệnh đề III.5 ở trên ta suy ra:
∀ x ∈ id1 : Key(α1x) = UI1x ⊕ Key(β1x). (1)
Mặt khác, theo giả thiết ta cũng có α2= (R2,Fh2 ), R2 = ( id2; A1, A2, ... , An ), β2= (V2,Gh2 ) là lược đồ khối
sau khi chuyển về dạng cân bằng của lược đồ khối α2, nên áp dụng kết quả của mệnh đề III.5 ở trên ta suy ra:
∀ x ∈ id2 : Key(α2x) = UI2x ⊕ Key(β2x). (2)
Ta lại có: ∀ x ∈ id1 : UIx = UI1x , Key(βx) = Key(β1x). (3)
∀ x ∈ id2 : UIx = UI2x , Key(βx) = Key(β2x). (4)
Từ (1), (2), (3) và (4) ta suy ra:
∀ x ∈ id : Key(αx) = UIx ⊕ Key(βx).
Do đó áp dụng tính chất của khóa trên lược đồ khối ta có:
Key(α) = UI ⊕ Key(β).
Ví dụ IV.3: Cho lược đồ khối α1 = (R1,Fh1 ), R1 = (id1; A1, A2, ... , A6 ), id1 = {a,b}, Fh1 = {a(1)a(5)→ a(4),
a a → a(3)a(5), a(6)→ a(3), a(5)→ a(2), a(5)→ a(3), b(1)b(5)→ b(4), b(2)b(3)→ b(3)b(5), b(6)→ b(3), b(5)→ b(2), b(5)→ b(3)}.
(2) (3)
α2 = (R2,Fh2 ), R2 = (id2; A1, A2, ... , A6 ), id2 = {c,d}, Fh2 = {c(1)c(5)→ c(4), c(2)c(3)→ c(3)c(5), c(6)→ c(3), c(5)→ c(2),
c → c(3), d(1)d(5)→ d(4), d(2)d(3)→ d(3)d(5), d(6)→ d(3), d(5)→ d(2), d(5)→ d(3)}.
(5)
Áp dụng công thức tính UI1 trong lược đồ khối α1 = (R1,Fh1 ), ta có: UI1 = { a(1)b(1)a(6)b(6)} với UI1a = {a(1)a(6)},
UI1b = {b(1)b(6)}.
Sau khi chuyển lược đồ khối α1 = (R1,Fh1 ) về dạng cân bằng ta được lược đồ khối β1 = (V1,Gh1 ) với V1 = {id1;
A2, A5}, Gh1 = { a(2)→ )a(5), a(5)→ a(2), b(2)→ )b(5), b(5)→ b(2)}.
Với lược đồ khối cân bằng β1 = (V1,Gh1 ) ta thấy ngay: Key(β1a) = { a(2)a(5)}, Key(β1b) = { b(2)b(5)}.
Áp dụng công thức tính UI2 trong lược đồ khối α2 = (R2,Fh2 ), ta có: UI2 = { c(1)d(1)c(6)d(6)} với UI2c = {c(1)c(6)},
UI2d = {d(1)d(6)},
Sau khi chuyển lược đồ khối α2 = (R2,Fh2 ) về dạng cân bằng ta được lược đồ khối β2 = (V2,Gh2 ) với V2 = {id2;
A2, A5}, Gh2 = { c(2)→)c(5), c(5)→ c(2), d(2)→)d(5), d(5)→ d(2)}.
Với lược đồ khối cân bằng β2 = (V2,Gh2 ) ta thấy ngay: Key(β2c) = { c(2)c(5)}, Key(β2d) = { d(2)d(5)}.
Áp dụng kết quả của mệnh đề IV.6 ta có:
Key(α) = { a(1)b(1)a(6)b(6) c(1)d(1)c(6)d(6)} ⊕ { a(2)a(5) b(2)b(5) c(2)c(5) d(2)d(5)} ,
Key(α) = { a(1)b(1)a(6)b(6) c(1)d(1)c(6)d(6)a(2)a(5) b(2)b(5) c(2)c(5) d(2)d(5)}.
V. KẾT LUẬN
Những kết quả về lược đồ khối cân bằng, mối quan hệ giữa lược đồ khối cân bằng và khóa đã giúp ích nhiều
cho việc tìm các khóa của lược đồ khối. Vì mọi lược đò khối đều có thể chuyển về lược đồ khối cân bằng qua thuật
toán cân bằng nên sử dụng mối quan hệ giữa khóa của lược đồ ban đầu với khóa của lược đồ cân bằng sau dịch chuyển
ta dễ dàng tính khóa của lược đồ khối ban đầu. Trong trường hợp khối suy biến thành quan hệ thì những kết quả này lại
trở thành các kết quả đối với quan hệ trong mô hình dữ liệu quan hệ. Một số kết quả được xét trong trường hợp riêng
của tập các phụ thuộc hàm F trên lược đồ khối như tập phụ thuộc hàm Fh, tập phụ thuộc hàm Fh đầy đủ,... Trên cơ sở
của các kết quả này ta có thể triển khai tiếp quá trình nghiên cứu khi các tập phụ thuộc hàm không còn bị ràng buộc
nhiều như các tập dạng Fh đã nói ở trên. Các kết quả nghiên cứu về lược đồ khối cân bằng đã góp phần làm hoàn chỉnh
thêm lí thuyết thiết kế mô hình cơ sở dữ liệu dạng khối.
TÀI LIỆU THAM KHẢO
[1] Trịnh Đình Thắng, Trần Munh tuyến, Các phụ thuộc logic trong mô hình dữ liệu dạng khối, NXB Khoa học và Kỹ thuật, Hà
Nội, 2020.
[2] Trịnh Đình Thắng, Một số kết quả về bao đóng, khóa và phụ thuộc hàm trong mô hình dữ liệu dạng khối, Kỷ yếu Hội thảo quốc
gia lần thứ IV “Một số vấn đề chọn lọc của công nghệ thông tin”, (245-251), Hải Phòng 05-07/06/2001.
- 412 MỘT SỐ TÍNH CHẤT CỦA LƯỢC ĐỒ KHỐI CÂN BẰNG TRÊN KHỐI VÀ LÁT CẮT
[3] Trịnh Đình Thắng, Trần Minh Tuyến, Phép dịch chuyển lược đồ khối và vấn đề biểu diễn bao đóng, khóa trong mô hình dữ liệu
dạng khối, Kỷ yếu Hội thảo quốc gia lần thứ XIII “Một số vấn đề chọn lọc của công nghệ thông tin và truyền thông”, (276-
286), Hưng Yên, 19-20/08/2010.
[4] Trịnh Đình Thắng, Trần Minh Tuyến, Khóa và các tập thuộc tính nguyên thủy, phi nguyên thủy với phép dịch chuyển lược đồ
khối, Kỷ yếu Hội thảo quốc gia lần thứ 13 "Một số vấn đề chọn lọc của công nghệ thông tin và truyền thông", (159-170), Cần
Thơ, 07-08/10/2011.
[5] Trịnh Đình Thắng, Trần Minh Tuyến, Lược đồ cân bằng, vế trái cực tiểu và khóa với phép dịch chuyển lược đồ khối, Kỷ yếu
Hội thảo quốc gia lần thứ XV "Một số vấn đề chọn lọc của công nghệ thông tin và truyền thông", (174-179), Hà Nội, 03-
04/12/2012.
[6] Tran Minh Tuyen, Trinh Dinh Thang, Nguyen Xuan Huy, Some properties of the positive boolean dependencies in the database
model of block form, Journal of Computer Science and Cybernetics, V.31, N.2, (159-169), Viet Nam, 2014.
SOME PROPERTIES OF THE BALANCED BLOCK SCHEMA ON THE BLOCKS AND SLICES
Trinh Dinh Thang, Do Thi Lan Anh, Tran Minh Tuyen, Nguyen Thi Ha
ABSTRACT: This paper states and proves some properties of the balanced block schema when performing operations on
block and slices schemas. The relationship between the balanced block scheme and the intersection of key on the blocks and slices.
When blocks degenerate into reletions, then properties of the balanced block schema again become properties of the balanced
relational schema. In addition, some properties of the relationship between the balanced block scheme and the key are stated and
proven here.
nguon tai.lieu . vn
