Luận văn Thạc sĩ Khoa học máy tính: Phép dịch chuyển lược đồ khối trong mô hình dữ liệu dạng khối

ĐẠI HỌC THÁI NGUYÊN

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

NGÔ VĂN ĐỊNH

PHÉP DỊCH CHUYỂN LƢỢC ĐỒ KHỐI TRONG MÔ HÌNH DỮ LIỆU DẠNG KHỐI

LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Thái Nguyên - 2015

ĐẠI HỌC THÁI NGUYÊN

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

NGÔ VĂN ĐỊNH

PHÉP DỊCH CHUYỂN LƢỢC ĐỒ KHỐI TRONG MÔ HÌNH DỮ LIỆU DẠNG KHỐI

CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH

MÃ SỐ: 60 48 0101

LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH

Ng êi h íng dÉn khoa häc

TS LÊ VĂN PHÙNG

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Thái Nguyên - 2015

LỜI CẢM ƠN

Để hoàn thành luận văn này tôi đã nhận đƣợc sự giúp đỡ tận tình của

thầy hƣớng dẫn khoa học, của các thầycô trƣờng Đại học Công nghệ thông tin

và truyền thông - Đại học Thái Nguyên. Tôi xin chân thành cảm ơn các thầy

cô trƣờng Đại học Công nghệ thông tin và truyền thông - Đại học Thái

Nguyên đã tạo điều kiện học tập, nghiên cứu và giúp đỡ tôi rất nhiều trong

quá trình làm luận văn. Đặc biệt tôi xin cảm ơn thầyTS Lê Văn Phùng đã tận

tình hƣớng dẫn, chỉ bảo tôi trong suốt quá trình học tập, nghiên cứu đề tài và

giúp đỡ tôi hoàn thành bản luận văn này.

Thái Nguyên, ngày 15 tháng 5 năm 2015

Học viên

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Ngô Văn Định

LỜI CAM ĐOAN

Tôi xin cam đoan đây là kết quả nghiên cứu của tôi dƣới sự hƣớng dẫn

khoa học của TS. Lê Văn Phùng.

Các số liệu, kết quả nêu trong luận văn là trung thực và chƣa từng đƣợc

Học viên

ai công bố trong bất kỳ công trình nào khác.

Ngô Văn Định

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

MỤC LỤC

Trang

MỤC LỤC .......................................................................................................... i

DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT .................................. iii

DANH MỤC CÁC HÌNH ................................................................................ iv

MỞ ĐẦU ........................................................................................................... 1

CHƢƠNG 1. MÔ HÌNH DỮ LIỆU DẠNG KHỐI .......................................... 4

1.1. Một số mô hình dữ liệu tiêu biểu ........................................................... 4

1.1.1. Mô hình dữ liệu quan hệ .................................................................. 4

1.1.2. Mô hình hƣớng đối tƣợng ................................................................ 4

1.1.3. Mô hình dữ liệu dạng khối .............................................................. 5

1.2. Khối, lƣợc đồ khối và các đặc trƣng cơ bản ........................................... 5

1.2.1. Khái niệm khối và lƣợc đồ khối ...................................................... 5

1.2.2. Các phép tính cơ bản trên khối ........................................................ 8

1.2.3. Khái niệm phụ thuộc hàm .............................................................. 15

1.2.4. Bao đóng của tập thuộc tính chỉ số ................................................ 16

1.2.5. Khóa của lƣợc đồ khối R đối với tập F trên R ............................... 19

1.2.6. Các dạng chuẩn, tựa chuẩn và tựa chuẩn hóa trên lƣợc đồ khối ... 22

1.2.7. Khái niệm về phủ và phủ tối thiểu của tập phụ thuộc hàm ........... 31

Kết luận chƣơng 1 ....................................................................................... 33

CHƢƠNG 2. PHÉP DỊCH CHUYỂN LƢỢC ĐỒ KHỐI .............................. 34

2.1. Phép dịch chuyển lƣợc đồ quan hệ ....................................................... 34

2.1.1. Định nghĩa ..................................................................................... 34

2.1.2. Thuật toán dịch chuyển lƣợc đồ quan hệ ....................................... 35

2.1.3. Bổ đề về siêu khoá trong phép dịch chuyển lƣợc đồ quan hệ ....... 39

2.1.4. Dịch chuyển lƣợc đồ quan hệ về dạng cân bằng ........................... 40

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

2.2. Phép dịch chuyển lƣợc đồ khối ............................................................ 43

2.2.1. Định nghĩa ..................................................................................... 43

2.2.2. Sự khác biệt giữa phép chuyển dịch lƣợc đồ khối so với phép dịch

chuyển lƣợc đồ quan hệ ........................................................................... 45

2.2.3 Một số thuật toán dịch chuyển lƣợc đồ khối .................................. 46

2.2.4. Biểu diễn bao đóng qua phép dịch chuyển .................................... 48

2.2.5. Biểu diễn khóa qua phép dịch chuyển ........................................... 51

2.2.6. Ví dụ .............................................................................................. 55

Kết luận chƣơng 2 ....................................................................................... 56

CHƢƠNG 3. CHƢƠNG TRÌNH THỬ NGHIỆM ......................................... 58

3.1. Bài toán thử nghiệm ............................................................................. 58

3.2. Phân tích và thiết kế chƣơng trình thử nghiệm .................................... 59

3.2.1. Thủ tục dịch chuyển ...................................................................... 59

3.2.2. Biểu diễn khóa qua phép dịch chuyển ........................................... 60

3.2.3. Thiết kế chƣơng trình .................................................................... 60

3.3. Cài đặt và thực hiện chƣơng trình thử nghiệm ..................................... 60

3.3.1. Yêu cầu hệ thống ........................................................................... 60

3.3.2. Hệ thống dữ liệu vào/ra ................................................................. 61

3.3.3. Hệ thống giao diện ......................................................................... 61

3.3.4. Kết quả thử nghiệm chƣơng trình và đánh giá .............................. 62

Kết luận chƣơng 3 ....................................................................................... 67

KẾT LUẬN ..................................................................................................... 68

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

TÀI LIỆU THAM KHẢO ............................................................................... 69

iii

DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT

Luận văn này dùng thống nhất các ký hiệu và chữ viết tắt sau:

Ký hiệu Ý nghĩa

CSDL

Dom(A) cơ sở dữ liệu miền giá trị của thuộc tính A

LĐQH lƣợc đồ quan hệ

r hoặc r(R) khối r trên tập R

lát cắt của r(R) tại điểm x. Rx

phụ thuộc hàm

các thuộc tính chỉ số của lƣợc đồ khối (x id, i = 1..n)

PTH x(i) = (x, Ai) id(i)= {x(i)|x id} tập các thuộc tính chỉ số của lƣợc đồ khối.

Fh tập các phụ thuộc hàm trên R

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Fhx tập các phụ thuộc hàm trên Rx

Trang

DANH MỤC CÁC HÌNH

Hình 1.1 Biểu diễn khối SANPHAM 7

Hình 1.2Ví dụ về phép hợp 10

Hình 1.3Ví dụ về phép giao 10

Hình 1.4 Ví dụ về phép trừ 11

Hình 3.1 Giao diện chính của chƣơng trình 61

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Hình 3.2 Giao diện nhập dữ liệu 62

MỞ ĐẦU

1. Lí do chọn lựa đề tài

Ngày nay, công nghệ thông tin đã trở thành một nhân tố không thể

thiếu đƣợc trong mọi lĩnh vực của đời sống xã hội. Sự bùng nổ nhu cầu xây

dựng các hệ thống thông tin, mà trƣớc hết là các hệ thống thông tin quản lý đã

trở thành hƣớng nghiên cứu và quan tâm của rất nhiều nhà khoa học cũng nhƣ

ngƣời sử dụng. Các hệ thống cơ sở dữ liệu (CSDL) đã lần lƣợt xuất hiện. Vào

những năm 60, thế hệ đầu tiên của cơ sở dữ liệu ra đời dƣới dạng các mô hình

thực thể - liên kết (có đặc điểm nhận dạng đối tƣợng), mạng phân cấp. Tiếp

đến là vào những năm 70 thế hệ thứ hai của CSDL ra đời. Đó là mô hình quan

hệ do E. F. Codd đề xuất. Loại mô hình này đã đánh dấu mốc quan trọng về

cơ sở lý thuyết của các hệ thống CSDL. Sở dĩ mô hình này đƣợc đánh giá cao

hơn cả vì nó đƣợc xây dựng dựa trên một cơ sở toán học chặt chẽ. Tuy nhiên,

do các quan hệ có cấu trúc phẳng (tuyến tính) nên mô hình này chƣa đủ đáp

ứng đối với các ứng dụng phức tạp, các cơ sở dữ liệu có cấu trúc phi tuyến,…

Trong những năm gần đây, việc nghiên cứu nhằm mở rộng mô hình

quan hệ đƣợc nhiều nhà khoa học quan tâm. Theo hƣớng nghiên cứu này đã

có một số hƣớng mở rộng mô hình quan hệ đƣợc đề xuất nghiên cứu nhƣ: mô

hình dữ liệu đa chiều; khối dữ liệu; kho dữ liệu; mô hình dữ liệu dạng khối...

Trong đó, ở mô hình dữ liệu dạng khối, các khối là khái niệm cơ bản đƣợc mở

rộng từ các quan hệ trong mô hình quan hệ, các khối này có thể biểu diễn các

dữ liệu có tính chất động (biểu diễn các dữ liệu có thuộc tính thay đổi theo

thời gian, không gian…) có khả năng đáp ứng tốt đối với nhiều lớp bài toán

phức tạp.

Trong mô hình quan hệ, để giảm tính phức tạp của việc xác định bao

đóng, khóa trong các cơ sở dữ liệu lớn, phức tạp, ngƣời ta đã đề xuất phép

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

dịch chuyển lƣợc đồ quan hệ (LĐQH). Trong mô hình cơ sở dữ liệu dạng

khối, việc xác định khóa và bao đóng càng khó khăn hơn, chính vì vậy mà

phép dịch chuyển lƣợc đồ khối đã đƣợc đề xuất với mục đích tƣơng tự.

Mục tiêu của đề tài là tìm hiểu kỹ thuật thu gọn lƣợc đồ khối dựa trên

phép dịch chuyển lƣợc đồ khối và phƣơng pháp biểu diễn bao đóng và khóa

của lƣợc đồ khối thông qua phép dịch chuyển với độ phức tạp thấp hơn so với

phƣơng pháp tìm bao đóng và khóa thông thƣờng. Đồng thời, nghiên cứu

thuật toán và cài đặt chƣơng trình thử nghiệm với thuật toán dịch chuyển lƣợc

đồ khối và biểu diễn khóa của lƣợc đồ khối qua phép dịch chuyển.

2. Mục đích nghiên cứu

Mô hình dữ liệu dạng khối là một mở rộng của mô hình quan hệ với các

khối cho phép biểu diễn các dữ liệu có tính chất động (biểu diễn các dữ liệu

có thuộc tính thay đổi theo thời gian). Tuy nhiên, các nghiên cứu về mô hình

dữ liệu này còn chƣa nhiều.

Đối với các cơ sở dữ liệu khối lớn và phức tạp, việc xác định khóa và

bao đóng là một việc khó. Nhờ việc dịch chuyển lƣợc đồ khối, việc tính bao

đóng và khóa có thể trở nên đơn giản hơn.

3. Nhiệm vụ nghiên cứu

- Nghiên cứu tổng quan về mô hình dữ liệu dạng khối; một số khái

niệm và thuật toán liên quan.

- Nghiên cứu phép dịch chuyển lƣợc đồ khối trong mô hình dữ liệu

dạng khối và một số thuật toán dịch chuyển lƣợc đồ khối.

- Áp dụng thuật toán dịch chuyển trong bài toán thực tế

4. Đối tƣợng và phạm vi nghiên cứu:

Đối tƣợng nghiên cứu: Mô hình dữ liệu dạng khối.

Phạm vi nghiên cứu: Phép dịch chuyển lƣợc đồ khối nhằm giảm

nhẹ độ phức tạp trong việc tính bao đóng và khóa của khối.

5. Phƣơng pháp nghiên cứu

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

- Phƣơng pháp nghiên cứu lý luận.

- Phƣơng pháp phân tích - tổng hợp.

- Phƣơng pháp chuyên gia.

6. Những đóng góp mới của đề tài

- Hệ thống hóa các khái niệm cơ bản về mô hình dữ liệu dạng khối; các

phép toán và thuật toán liên quan trên mô hình dữ liệu dạng khối.

- Tìm hiểu phép dịch chuyển lƣợc đồ khối trong mô hình dữ liệu dạng

khối và một số thuật toán dịch chuyển lƣợc đồ khối.

- Áp dụng thuật toán đó trên để xây dựng chƣơng trình minh họa khả

năng dịch chuyển khối và biểu diễn khóa qua phép dịch chuyển.

7. Cấu trúc luận văn

Các nội dung nghiên cứu của đề tài luận văn đƣợc cấu trúc thành 3

chƣơng nhƣ sau:

Chƣơng 1. Mô hình dữ liệu dạng khối

Giới thiệu tóm tắt về các mô hình dữ liệu. Các khái niệm cơ bản về mô

hình dữ liệu dạng khối nhƣ: Định nghĩa khối, lát cắt, lƣợc đồ khối...; các phép

tính trên khối.

Một số khái niệm về bao đóng, khóa, phụ thuộc hàm... trong mô hình

dữ liệu dạng khối. Tìm hiểu một số thuật toán tìm bao đóng và khóa của lƣợc

đồ khối.

Chƣơng 2. Phép dịch chuyển lƣợc đồ khối

Giới thiệu sơ lƣợc về phép dịch chuyển LĐQH trong mô hình quan hệ

và một số vấn đề liên quan.

Tìm hiểu về phép dịch chuyển và thuật toán dịch chuyển lƣợc đồ khối

trong mô hình dữ liệu dạng khối. Đƣa ra phƣơng pháp biểu diễn bao đóng và

khóa của lƣợc đồ khối thông qua phép dịch chuyển.

Chƣơng 3. Chƣơng trình thử nghiệm

Tiến hành cài đặt các thuật toán dịch chuyển lƣợc đồ khối trong mô

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

hình dữ liệu dạng khối.

CHƢƠNG 1. MÔ HÌNH DỮ LIỆU DẠNG KHỐI

1.1. Một số mô hình dữ liệu tiêu biểu

1.1.1. Mô hình dữ liệu quan hệ

Khái niệm toán học làm nền tảng cho mô hình quan hệ là các quan hệ

theo lý thuyết tập hợp. Đó là tập con của tích Đề-Các của một danh sách các

miền, mỗi miền đơn giản là một tập các giá trị. Ta có thể xem một quan hệ

nhƣ một bảng, trong đó mỗi hàng là một bộ và mỗi cột là một thuộc tính.

Ta cũng có thể biểu diễn một sơ đồ thực thể-liên kết trong mô hình

quan hệ. Khi đó, các dữ liệu của sơ đồ thực thể-liên kết đƣợc biểu diễn bởi hai

loại quan hệ:

- Một tập thực thể E có thể đƣợc biểu diễn bởi một quan hệ mà LĐQH

của nó chứa tất cả các thuộc tính của tập thực thể đó. Mỗi bộ của quan hệ biểu

diễn một thực thể trong thể hiện của E.

- Mối liên hệ giữa các tập E1, E2,.., Ek đƣợc biểu diễn bởi một quan hệ

có LĐQH chứa các thuộc tính trong các khóa của E1, E2,.., Ek. Bằng cách đặt

lại tên cho các thuộc tính nếu cần, ta đảm bảo rằng không có hai tập thực thể

trong danh sách có các thuộc tính cùng tên, ngay cả khi hai tập thực thể này

chỉ là một.

1.1.2. Mô hình hướng đối tượng

Mô hình dữ liệu hƣớng đối tƣợng có một số đặc điểm sau:

Đặc tính nhận dạng đối tƣợng (Object identity): Các thành phần chúng

xử lý điển hình là những mẩu tin, có địa chỉ duy nhất giống nhƣ trong mô

hình mạng và mô hình phân cấp.

Các đối tƣợng phức (Complex object): cho phép xây dựng một kiểu

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

mới bằng thao tác tạo lập mẫu tin hoặc tạo lập tập hợp.

Phân cấp theo kiểu (Type hierachy): Cho phép những kiểu có thể có

những kiểu con và có thuộc tính riêng.

Tất cả các cấu trúc đối tƣợng (object structure) đƣợc định nghĩa trong

mô hình này rất gần với tập các lƣợc đồ cho các mẫu tin cơ sở dữ liệu trong

mô hình phân cấp.

Một mô hình hƣớng đối tƣợng không bị giới hạn trong khái niệm kiểu

đối tƣợng. Khái niệm cơ bản thực sự là lớp (class), đó là một kiểu đối tƣợng

làm cấu trúc dữ liệu nền tảng và một tập hợp các phƣơng pháp (method), đó là

các thao tác đƣợc thực hiện trên các đối tƣợng có cấu trúc thuộc về lớp đó.

Mô hình hƣớng đối tƣợng gắn liền với mô hình phân cấp theo nghĩa là

nếu đƣợc cho trƣớc một lƣợc đồ phân cấp nào đó, ta có thể mô phỏng nó

trong mô hình hƣớng đối tƣợng bằng cách xem các con của một nút (gồm tất

cả các con là các kiểu mẫu tin ảo) trong lƣợc đồ phân cấp nhƣ là các trƣờng

trong một cấu trúc đối tƣợng ứng với n. Các cấu trúc đối tƣợng cho các con

của n lại có các con của chúng là các trƣờng... Nhƣ vậy, mô hình hƣớng đối

tƣợng có thể diễn tả mọi cấu trúc của mô hình thực thể-liên kiết, tuy nhiên để

đảm bảo yêu cầu truy xuất hiệu quả các thông tin cần thiết trong các cấu trúc

đối tƣợng cũng không phải là một công việc đơn giản.

1.1.3. Mô hình dữ liệu dạng khối

Mô hình dữ liệu dạng khối là một mở rộng của mô hình quan hệ, khi

đó, mô hình quan hệ có thể đƣợc coi là một trƣờng họp đặc biệt của mô hình

dữ liệu dạng khối. Các nội dung cụ thể sẽ đƣợc trình bày trong phần tiếp theo

của luận văn.

1.2. Khối, lƣợc đồ khối và các đặc trƣng cơ bản

1.2.1. Khái niệm khối và lược đồ khối

Khái niệm toán học làm nền tảng cho mô hình dữ liệu dạng khối là các

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

khối hiểu theo nghĩa của lý thuyết tập hợp. Khối đƣợc định nghĩa nhƣ sau:

Định nghĩa 1.1[4], [7]

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ọ ánh xạ từ tập chỉ số id

đến các miền giá 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ý kiệ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.

Khi đó, khối r(R) đƣợc gọi là có lƣợc đồ khối R. Nhƣ vậy, trên cùng

một lƣợc đồ khối R, ta có thể xây dựng đƣợc nhiều khối khác nhau.

Ví dụ 1.1

Xây dựng khối sản phẩm (ký hiệu SP(R)) để quản lý sản phẩm của một

công ty: cho lƣợc đồ khối R = (id; A1, A2, A3, A4) trong đó:

id = {1/2014, 2/2014, 3/2014, ..., 12/2014} và các thuộc tính A1 = ma

(mã), A2 = ten (tên), A3 = c_luong (chất lƣợng), A4 = gia (giá).

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Hình 1.1 Biểu diễn khối SANPHAM

Với khối SP(R) ở hình trên thì nó gồm 3 phần tử t1, t2, t3.

Chất lƣợng của sản phẩm t1 ở thời điểm tháng 2 năm 2014 là:

t1(2/2014, c_luong) = Tot

Mã số của sản phẩm t2 ở thời điểm tháng 1 năm 2014 là:

t2(1/2014, ma) = A02

Tên của sản phẩm t3 ở thời điểm tháng 3 năm 2014 là:

t3(3/2014, ten) = C

Giá của sản phẩm t2 ở thời điểm tháng 1 năm 2014 là:

t2(1/2014, gia) = 400

Định nghĩa 1.2[4], [7]

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:

với t = {ti: id Dom(Ai)} i=1..n

ở đây .

Khi đó, t(Rx) đƣợc gọi là một lát cắt trên khối r(R) tại điểm x.

Ví dụ 1.2

Với khối SP(R) đã cho ở trên, R = (id; A1, A2, A3, A4) trong đó:

id = {1/2014, 2/2014, 3/2014, ..., 12/2014} và các thuộc tính A1 = ma (mã),

A2 = ten (tên), A3 = c_luong (chất lƣợng), A4 = gia (giá).

Nếu x = 1/2014 id thì lát cắt r(R1/2014) có dạng nhƣ sau:

ma c_luong gia ten r(R1/2014):

A01 TB 300 A

A02 Tot 400 B

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

A03 Cao 550 C

Nhận xét

Cho R = (id; A1, A2,…, An), r(R) là một khối trên R. Với mỗi x id, thì

lát cắt r(Rx) là một quan hệ. Trong trƣờng hợp tập chỉ số id gồm một phần tử

thì r(R) trở thành một quan hệ.

Nhƣ vậy, mỗi quan hệ r(A1, A2,…, An) là một trƣờng hợp đặc biệt của

khối, đó chính là khối r(R) với R = ({x}; A1, A2,…, An).

Mệnh đề 1.1[4], [7]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), r(R) là một khối trên R, khi

đó tồn tại một họ quan hệ (hiểu theo nghĩa tập hợp) duy nhất biểu diễn họ

{r(Rx)}x id các lát cắt của khối r(R). Ngƣợc lại không đúng, nghĩa là với một

họ quan hệ cho trƣớc biểu diễn họ các lát cắt của một khối nào đó thì khối tìm

đƣợc không duy nhất.

1.2.2. Các phép tính cơ bản trên khối

Các phép tính cơ bản thƣờng đƣợc áp dụng cho một cơ sở dữ liệu là:

- Phép chèn (insert)

- Phép loại bỏ (delete)

- Phép sửa đổi (change)

Trong mô hình dữ liệu dạng khối, các phép tính này cũng đƣợc áp dụng

cho từng phần tử của các khối lƣu trữ trong máy. Cụ thể

- Phép chèn (insert)[4], [7]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), r(R) là một khối trên R.

0, t2

0,…, tn

Khi chèn thêm một phần tử t0 vào khối r, ta có:

r = r INSERT(r, t1 {t0}, ở đó t0 = (t1 0,…, tn 0, t2

- Phép loại bỏ (delete) [4], [7]

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Cho lƣợc đồ khối R = (id; A1, A2,…, An), r(R) là một khối trên R.

Phép loại bỏ là phép xóa một phần tử ra khỏi một khối cho trƣớc.

0,…, tn 0) 0,…, tn = tn

r = r - {t0}, t0 = (t1 DEL(r, t1 = t1 Chẳng hạn, loại phần tử t0 vào khối r(R), có dạng: 0, t2 0, t2 = t2

Ở đây, để xác định phần tử cần loại bỏ, ta phải dùng bộ ánh xạ (t1, t2,…,

0, t2=t2

0,…, tn = tn

0 để

tn). Nghĩa là, ta phải thực hiện các phép so sánh: t1 = t1

xác định phần tử t0 nhƣ ở trên.

- Phép sửa đổi (change)[4], [7]

0,…, tn

0,…, t’n

0),

Phép sửa đổi phần tử t0 thành phần tử t’0 có dạng. 0), t’0 = (t’1

0, t2 0; t1 = t’1

0, t2 = t’2

0, t’2 0,…, t’n = tn

r = r - {t0} CH(r, t1 = t1 {t’0}, với t0 = (t1 0,…, tn = tn 0, t2 = t2

Đối với các phép chèn, loại bỏ và sửa đổi nêu trên, khi khối r suy biến

thành một quan hệ, nghĩa là khi tập chỉ số id chỉ gồm một phần tử (id ={x})

thì chúng lại trở thành các phép chèn, loại bỏ và sửa đổi trên một quan hệ

trong mô hình dữ liệu quan hệ.

* Đại số trên khối [4], [7]

Cho r là một khối trên R = (id; A1, A2,…, An). Tƣơng tự nhƣ đại số

quan hệ trong mô hình dữ liệu quan hệ, ở đây, các phép toán của đại số quan

hệ đƣợc áp dụng cho các khối nhƣ: phép hợp, phép giao,phép trừ, phép chiếu,

phép chọn, phép kết nối, phép chia. Ngoài ra, phép nối dài là phép toán mới

đƣợc xây dựng.

Hai khối r và s đƣợc gọi là khả hợp nếu chúng có cùng một lƣợc đồ khối.

- Phép hợp

Cho hai khối r và s khả hợp, khi đó hợp của r và s, ký hiệu r s là một

khối gồm các phần tử thuộc khối r hoặc thuộc khối s đã cho.

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Ta có: r s = {t | t r hoặc t s}

ten

A01

A02

A01

A02

2/2014

A02

2/2014

A03

A02

Ví dụ 1.3

1/2014

A03

1/2014

A03

2/2014

1/2014

A03

A02

s r s r

Hình 1.2.Ví dụ về phép hợp

- Phép giao

Cho hai khối r và s khả hợp, khi đó giao của r và s, ký hiệu r s là một

khối gồm các phần tử của nó thuộc đồng thời cả hai khối r và s đã cho.

Ta có: r s = {t | t r và t s}

ten

A01

ten

A01

A02

A01

A02

Ví dụ 1.4

2/2014

A01

A02

1/2014

A02

2/2014

A03

A02

1/2014

A03

r r s s

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Hình 1.3Ví dụ về phép giao

- Phép trừ

Cho hai khối r và s khả hợp, khi đó hiệu của r và s, ký hiệu r - s là một

khối mà các phần tử của nó thuộc r nhƣng không thuộc s.

Ta có: r - s = {t | t r và t s}

Ta thấy: r s = r – (r – s)

ten

A01

A02

A01

A01 A01

A02

ten

A02

2/2014

A02

A03

A02

1/2014

A02

A03

1/2014

A03

t3 2/2014

1/2014

A03

Ví dụ 1.5

r r - s

Hình 1.4Ví dụ về phép trừ

- Tích Đề-các

Cho lƣợc đồ khối R = (id; A1, A2,…, An), S = (id; B1, B2,…, Bm),

. và {A1, A2,…, An} {B1, B2,…, Bm} =

Khi đó, tích Đề-các của hai khối r(R) và s(S) là một khối, ký hiệu r s,

khối này có khung R S = (id; A1, A2,…, An, B1, B2,…, Bm), mỗi phần tử

thuộc khối này là một bộ gồm n + m ánh xạ, trong đó n ánh xạ đầu có dạng

một phần tử thuộc r, còn m ánh xạ sau có dạng một phần tử thuộc s.

r s = {t | t(R) r và t(S) s},

trong đó:

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

t = (t1, t2,…, tn, tn+1,…, tn+m), t(R) = (t1, t2,…, tn), t(S) = (tn+1,…, tn+m).

- Tích Đề-các theo tập chỉ số

Cho lƣợc đồ khối R = (id; A1, A2,…, An), S =(id’; A1, A2,…, An). Khi

đó, tích Đề-các của hai khối r(R) và s(S) theo tập chỉ số là một khối, ký hiệu

id s, khối này có khung R

id S=(id ∐ id’; A1, A2,…, An), với id ∐ id’ là

ký hiệu tích rời rạc của hai tập chỉ số id và id’. Mỗi phần tử thuộc khối này là một bộ gồm n ánh xạ(t1, t2,…, tn) với ti: id ∐ id’ → Ai, với i = 1..n, mỗi ánh

xạ này đƣợc cảm sinh từhai ánh xạ thứ i tƣơng ứng của r và s.

s: r và ts

r), ts = (t1

r,…, tn

s, t2

r, t2

s),

Cụ thể hơn, giả sử có 2 phần tử là tr s,…, tn tr = (t1

khi đó, ta có ánh xạ cảm sinh của tr và ts, phần tử cảm sinh của tr và ts,

ký hiệu là trs.

Gọi j1: id → id ∐ id’; j2: id → id ∐ id’ là các phép nhúng, thì ta

id s = {t | tj1

s và r s} đƣợc:trsj1 r và trsj2 r và tj2

- Phép chiếu

Cho lƣợc đồ khối R = (id; A1, A2,…, An), r là một khối trên R. Khi đó,

ta gọi P = (id’; Ai1, Ai2,…, Aih) là lƣợc đồ con của lƣợc đồ R nếu:

id' id, Aij {A1, A2,…, An}, j = 1..h

p(r), là một khối có

Một phép chiếu của r trên lƣợc đồ con P, ký hiệu

lƣợc đồ P và mỗi phần tử thuộc khối này có dạng:

Trong đó: tij {t1, t2,…, tn} với j = 1..h và (t1, t2,…, tn) r

Biểu diễn theo hình thức của phép chiếu có dạng:

- Phép chọn

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Cho lƣợc đồ khối R = (id; A1, A2,…, An), và khối r(R).

Cho một phép chọn, nghĩa là ta xây dựng một tập con các phần tử của

khối đã cho thỏa mãn biểu thức F cho trƣớc. Biểu thức F đƣợc diễn tả bằng một

tổ hợp Boole của các toán hạng, mỗi toán hạng là một phép so sánh đơn giản

giữa hai biến là hai giá trị điểm của hai ánh xạ thành phần nào đó hoặc giữa

một biến là giá trị điểm của một ánh xạ thành phần và một hằng. Các phép so

sánh trong F là: <, >, =, , , , còn các phép toán logic trong F là: , , .

Biểu diễn hình thức của phép chọn có dạng:

F(r) = {t

r | F(t)},

Trong đó F(t) là giá trị của biểu thức Boole F tại phần tử t r.

- Phép kết nối

Cho lƣợc đồ khối R = (id; A1, A2,…, An), S = (id; B1, B2,…, Bm), cùng

với hai khối tƣơng ứng r(R), s(S).

Gọi T = (id; C1, C2,…, Cp), trong đó:

{C1, C2,…, Cp} = {A1, A2,…, An} {B1, B2,…, Bm}.

Phép kết nối của hai khối r và s, ký hiệu r ⨝ s là khối t(T) định nghĩa

nhƣ sau:

t(T) = {t | tr r và ts s sao cho t(R) =tr, t(S) = ts}

Phép kết nối này cũng gọi là phép kết nối tự nhiên của hai khối r(R) và

s(S), đôi khi sử dụng ký hiệu r*s.

Đặc biệt, khi các khối r(R) và s(S) có tập chỉ số id trong lƣợc đồ khối

của chúng chỉ gồm một phần tử thì các khối này trở thành các quan hệ và

phép kết nối tự nhiên của hai khối lại trở thành phép kết nối tự nhiên của hai

quan hệ trong mô hình CSDL quan hệ.

Nếu hai tập {A1, A2,…, An}và {B1, B2,…, Bm} không giao nhau thì r* s

trở thành tích Đề-các của hai khối đã cho.

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Ta có thể mở rộng khái niệm kết nối nhƣ sau:

Giả sử Aik {A1, A2,…, An}, Bik {B1, B2,…, Bm} và Dom(Aik) =

k Dom(Bik), 1 h (ở đây Aik và Bik không nhất thiết phải phân biệt).

Khi đó, phép kết nối của r và s theo Ai1, Ai2,…, Aih và Bi1, Bi2,…, Bih là

ik, 1 k h},

khối t(T), khối này đƣợc định nghĩa là:

ik = ts

r và ts s sao cho t(R) =tr, t(S) = ts, tr

r), ts = (t1

s, t2

s,…, tm

s).

t(T) = {t | r, t2 trong đó tr = (t1 tr r,…, tn

ik, 1

Thay cho ký hiệu r ⨝ s, ở đây ta ký hiệu rõ hơn:

ik = ts

k h] s. t(T) = r [tr

- Phép chia

Cho hai khối r(id; A1, A2,…, An) và s(id; Ai1, Ai2,…, Aih), trong đó,

Aik {A1, A2,…, An}, k =1..h. Khi đó, phép chia của khối r cho khối s, ký

hiệu r s, là một khối gồm các phần tử t = (t1, t2, …, tn-h) sao cho:

u = (u1, u2, …, uh), u s thì phần tử tu r,

ở đây phần tử tu có dạng:tu = (t1, t2, …, tn-h, u1, u2, …, uh).

Biểu diễn hình thức của phép chia: r s = {t | u s, tu r}.

- Phép nối dài

Cho hai khối r(id; A1, A2,…, An), s (id’; A1, A2,…, An), ở đó, nếu id

id’ = r và k s:

mà ta có với t t = (t1, t2, …, tn), k = (k1, k2, …, kn)

thì khi đó, ta xây dựng đƣợc một phần tử mới có dạng:

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

u = (u1, u2, …, un) vớiuh: id id’ Dom(Ah)sao cho:

, và ký hiệu uh = th *id kh, h = 1..n

Những phần tử u = (u1, u2, …, un) này tạo thành một khối mới, đƣợc ký

hiệu r *id s, gọi là khối nối dài của hai khối r và s.

Phép toán đƣợc xây dựng ở trên gọi là phép nối dài của hai khối r và s

đã cho.

Biểu diễn hình thức của phép nối dài có dạng:

1.2.3. Khái niệm phụ thuộc hàm

id)

Để đơn giản, ta sử dụng các ký hiệu: x(i) = (x; Ai); id(i) = (x(i)| x 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).

Định nghĩa 1.3[4], [7]

, Cho R = (id; A1, A2,…, An), r(R) là một khối trên R, X, Y

X Y là ký hiệu mộtphụ thuộc hàm (PTH). Một khối r thỏa X Y nếu với

mọi t1, t2 R sao cho t1(X)= t2(X) thì t1(Y)= t2(Y).

Định nghĩa 1.4[4], [7]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), F là tập cácPTH 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ệuPTHX Y đơn

giản làx(m) y(k).

Khối r thỏa x(m) y(k) nếu với mọi mọi t1, t2 r sao cho t1(x(m))= t2(x(m))

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

thì t1(y(k))= t2(y(k)).

Trong đó:

t1(x(m))= t1(x; Am), t2(x(m))= t2(x; Am), t1(y(k))= t1(x; Ak), t2(y(k))= t2(x; Ak),

Mệnh đề1.2[4], [7]

, X Cho R = (id; A1, A2,…, An), r(R) là một khối trên R, X, Y

Y là ký hiệu mộtPTH. Giả sử r(R) thỏaPTHX Y. Khi đó, nếu id = {x} thì: r(R)

) trở trở thành quan hệ r(A1, A2,…, An) vàPTH X Y, (X, Y

thànhPTH trong mô hình dữ liệu quan hệ.

Mệnh đề 1.3[4], [7]

là một khối trên R,

Cho R = (id; A1, A2,…, An), r(R) id(m),x(k) id(k). Khi đó, nếu r thỏaPTHx(m) x(m) x(k) thì đối với mọi y

id, r thỏa y(m) y(k)

Mệnh đề 1.4[4], [7]

r(R) là một khối trên R, Cho R=(id; A1, A2,…, An),

x(m),y(m) id(m),x(k),y(k) id(k). Khi đó, nếu r thỏa cácPTHx(m) y(m) và x(m)

y(k) thì r thỏa x(m) y(k).

1.2.4. Bao đóng của tập thuộc tính chỉ số

Định nghĩa 1.5[4], [7]

Cho R = (id; A1, A2,…, An), F là tập cácPTH trên R.

Với mỗi X , ta định nghĩa bao đóng của X đối với F, ký hiệu

X+ nhƣ sau:

X+ = {x(i), x id, i = 1..n | X x(i) F}

Cho lƣợc đồ khối R = (id; A1, A2,…, An), ta ký hiệu tập cácPTH trên R:

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

, Y = , A, B {1, 2,… n}, x id}, Fh = {X Y|X =

Y }, với x ∈ id và kí hiệu Fhx= Fhx = {X Fh | X, Y

Thuật toán 1.1(Tìm bao đóng của tập thuộc tính X của lƣợc đồ

khối)[4], [7]

Algorithm BAODONG1

Format: BAODONG1(X, F, R)

Input: Tập thuộc tính X, tập phụ thuộc hàm F và

lược đồ khối R

Output: X+, bao đóng của X đối với F trên R

Method

Tepcu := ; tepmoi := X;

While tepmoi tepcu do

Begin

Tepcu := tepmoi;

For each W Z in F do

If tepmoi W then tepmoi:=tepmoi Z;

End;

Return (tepmoi);

End BAODONG1;

Cho lƣợc đồ khối R = (id; A1, A2,…, An), Fh, Fhx là tập cácPTH trên R,

, M = , x A id. Rx tƣơng ứng, M , Mx , Mx

Khi đó, dựa vào thuật toán tính bao đóng ở trên, ta có thể tính bao đóng M+ của M đối với Fh. Từ quá trình tính bao đóng của M đối với Fh, ta thấy đó

A) chính là các quá trình tính bao đóng của các tập thuộc tính chỉ số Mx (x

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

A). đối với các tậpPTH tƣơng ứng Fhx (x

Mệnh đề 1.5[4], [7]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), Fh, Fhx là tập cácPTH trên R,

, M = , x A id. Rx tƣơng ứng, M , Mx , Mx

x A d, Khi đó, nếu M+ là bao đóng của M đối với Fh thì

M+ là bao đóng của Mx = M đối với Fhx.

Mệnh đề 1.6[4], [7]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), Fh, Fhx là tập cácPTH trên R,

, M = , x A id. Rx tƣơng ứng, M , Mx , Mx

+ là bao đóng của Mx đối với Fhx thì

là bao đóng Khi đó nếu Mx

của M = đối với Fh.

Từ hai mệnh đề trên, ta rút ra điều kiện cần và đủ sau:

Mệnh đề 1.7[4], [7]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), Fh, Fhx là tập cácPTH trên R,

, M = , x A id. Rx tƣơng ứng, M , Mx , Mx

+ =M+

Khi đó, M+ là bao đóng của M đối với Fh khi và chỉ khi:

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Mx là bao đóng của Mx đối với Fhx.

Thuật toán 1.2(Tìm bao đóngcủa tập thuộc tính X của lƣợc đồ khối)[4],

[7]

Algorithm BAODONG2

Format: BAODONG2(X, Fh, R)

Input: - tập thuộc tính X,

- tậpPTH Fh

- lược đồ khối R.

Output: X+, bao đóng của X đối với Fh trên R.

Method

X+ := ;

For each x id do

begin

Y := X ;

; Fhx :=

if Y then X+ := X+ BAODONG(Y,Fhx,R);

end; return(X+)

End BAODONG2;

1.2.5. Khóa của lược đồ khối R đối với tập F trên R

Định nghĩa 1.6[4], [7]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), F là tập cácPTH trên R, K

. K gọi là khóa của lƣợc đồ R đối với F nếu F thỏa 2 điều kiện:

a. K x(i) F+, x id, i = 1..n.

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

b. K’ K thì K’ không có tính chất a.

Nếu K là khóa và K K’’ thì K’’ gọi là siêu khóa của lƣợc đồ R đối

với F.

Từ định nghĩa của khóa, ta có thuật toán tìm khóa của lƣợc đồ khối R

đối với tập cácPTH F trên R nhƣ sau:

Thuật toán 1.3(Tìm một khóa của lƣợc đồ khối)[4], [7]

Algorithm KHOA

Format: KHOA (R, F)

Input: - Lược đồ R = (id; A1, A2,…, An),

- tập cácPTHF trên R.

Output: K là khóa của R đối với F.

Method

K := {x(i) | x id, i {1, 2, …, n}};

For each x in id do

For each i in {1, 2, …, n} do

ifK - {x(i)} K then K:=K–{x(i)};

return(K);

End KHOA;

Mệnh đề 1.8[4], [7]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), Fh, Fhx là tập cácPTH trên R,

, x Rx tƣơng ứng, K id. Khi đó, nếu K là khóa của R đối với Fh thì

x id, Kx = K là khóa của Rx đối vớiFhx.

Chứng minh

Giả sử K là khóa của R đối với Fh, khi đó, theo định nghĩa khóa thì bao

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

đóng K+ của K thỏa mãn K+ = và mọiK’ K không có tính chất này.

+ =

Khi đó, K+ là bao đóng của Kx = K đối với Fhx.

Nhƣ vậy Kx

+ =

Để có Kx là khóa của Rx đối với Fhx, ta còn phải chứng minh rằng:

+ là bao đóng của Nx

Nx Kx thì không xảy ra Nx (ở đây Nx

+ =

đối với Fhx).

, khi đó có bao đóng là Thật vậy, giả sử Nx

mà , mâu thuẫn với tính chất khóa của K.

Mệnh đề 1.9[4], [7]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), Fh, Fhx là tập cácPTH trên R,

, x Rx tƣơng ứng, Kx id. Khi đó, nếu Kx là khóa của Rx đối với Fhx

thì K = là khóa của R đối vớiFh.

Chứng minh

Theo giả thiết, ta có: x x id, id, Kx là khóa của Rx đối với Fhx

. Do đó, = . Mặt khác, theo điều kiện cần và đủ về Kx

bao đóng ở trên, ta lại có: K+ = K+ = .

Giả sử có K’ K, mà K’+ = .

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Khi đó, (K’ ) (K ), x id.

id sao cho = (K’ ) (K ). Mà Nhƣ vậy, x0

theo giả thiết thì = , còn = K’+ = Mâu

thuẫn với giả thiết là khóa của đối với .

Từ các mệnh đề 1.13 và 1.14, ta rút ra điều kiện cần và đủ sau:

Mệnh đề 1.10[4], [7]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), Fh, Fhx là tập cácPTH trên R,

, x Rx tƣơng ứng, K id. Khi đó, nếu K là khóa của R đối với Fh khi

và chỉ khi Kx = K là khóa của Rx đối với Fhx.

Hệ quả 1.1

Cho lƣợc đồ khối R = (id; A1, A2,…, An), Fh, Fhx là tập cácPTH trên R,

, x id. Khi đó, nếu với A {1, 2, …, n}là Rx tƣơng ứng, K

khóa của Rx đối với Fhx thì là khóa của lƣợc đồ R đối vớiFh.

1.2.6.1. Các dạng chuẩn

1.2.6. Các dạng chuẩn, tựa chuẩn và tựa chuẩn hóa trên lược đồ khối

Định nghĩa 1.7[3], [5]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), F là tập các PTH trên R. Ta

gọi lƣợc đồ khối R thuộc dạng chuẩn 1 nếu và chỉ nếu toàn bộ các miền giá trị của các thuộc tính x(i), x {1, 2, …,n} đều chỉ chứa các giá trị id, i

nguyên tố.

Mệnh đề 1.11[3], [5]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), F là tập các PTH trên R. R

thuộc dạng chuẩn 1. Khi đó, nếu id = {x} thì lƣợc đồ khối R suy biến thành

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

LĐQH ở dạng chuẩn 1 trong mô hình dữ liệu quan hệ.

Định nghĩa 1.8[3], [5]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), F là tập các PTH trên R; X, Y

. Ta nói Y phụ thuộc hàm đầy đủ vào X nếu Y là phụ thuộc hàm vào

X nhƣng không phụ thuộc hàm vào bất kỳ một tập con thực sự nào của X.

Định nghĩa 1.9[3], [5]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), F là tập các PTH trên R. Ta

gọi lƣợc đồ khối R thuộc dạng chuẩn 2 nếu nó ở dạng chuẩn 1 và mọi thuộc

tính không khóa của R đều là PTH đầy đủ vào khóa.

Mệnh đề 1.12[3], [5]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), F là tập các PTH trên R. R

thuộc dạng chuẩn 2. Khi đó, nếu id = {x} thì lƣợc đồ khối R suy biến thành

LĐQH ở dạng chuẩn 2 trong mô hình dữ liệu quan hệ.

Mệnh đề 1.13[3], [5]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), và Fh là tập các PTH trên R.

R thuộc dạng chuẩn 2. Khi đó, R thuộc dạng chuẩn 2 thì với mọi x id, Rx

cũng ở dạng chuẩn 2.

Định nghĩa 1.10[3], [5]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), F là tập các PTH trên R. Ta gọi lƣợc đồ khối R thuộc dạng chuẩn 3 nếu nó ở dạng chuẩn 2 và mọi thuộc

tính không khóa của R đều là không PTH bắc cầu vào khóa.

Mệnh đề 1.14[3], [5]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), F là tập các PTH trên R. R

thuộc dạng chuẩn 3. Khi đó, nếu id = {x} thì lƣợc đồ khối R suy biến thành

LĐQH ở dạng chuẩn 3 trong mô hình dữ liệu quan hệ.

Mệnh đề 1.15[3], [5]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), và Fh là tập các PTH trên R.

R thuộc dạng chuẩn 3. Khi đó, R thuộc dạng chuẩn 3 thì với mọi x id, Rx

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

cũng ở dạng chuẩn 3.

Định nghĩa 1.11[3], [5]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), F là tập các PTH trên R; X

. Ta gọi lƣợc đồ khối R thuộc dạng Boye-Codd nếu X x(i) thỏa trên

R, x(i) X, x id, i {1, 2, …, n} thì X là một khóa của R.

Mệnh đề 1.16[3], [5]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), F là tập các PTH trên R. R

thuộc dạng chuẩn Boye-Codd. Khi đó, nếu id = {x} thì lƣợc đồ khối R suy

biến thành LĐQH ở dạng chuẩn Boye-Codd trong mô hình dữ liệu quan hệ.

Mệnh đề 1.17[3], [5]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), F là tập các PTH trên R. Khi

đó, R thuộc dạng chuẩn Boye-Codd thì R ở dạng chuẩn 3.

Mệnh đề 1.18[3], [5]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), Fh là tập các PTH trên R.

Khi đó, R thuộc dạng chuẩn Boye-Codd thì x id, Rx cũng ở dạng chuẩn

1.2.6.2. Các dạng tựa chuẩn

Boye-Codd.

Định nghĩa 1.12[3], [5]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), F là tập các PTH trên R. Ta

gọi lƣợc đồ khối R thuộc dạng tựa chuẩn 2 (tựa chuẩn 3) nếu và chỉ nếu x

id, lát cắt Rx thuộc dạng chuẩn 2 (chuẩn 3).

Định nghĩa 1.13[3], [5]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), F là tập các PTH trên R. Ta

gọi lƣợc đồ khối R thuộc dạng tựa chuẩn Boye-Codd nếu và chỉ nếu x id,

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

lát cắt Rx thuộc dạng chuẩn Boye-Codd.

Mệnh đề 1.19[3], [5]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), F là tập các PTH trên R. Khi

đó, nếu x id sao cho Rx thuộc dạng chuẩn 2 (dạng chuẩn 3, dạng chuẩn

Boye-Codd) thì y id, ta có Ry thuộc dạng chuẩn 2 (dạng chuẩn 3, dạng

chuẩn Boye-Codd).

Mệnh đề 1.20[3], [5]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), F là tập các PTH trên R. Khi

đó, nếu x id sao cho Rx thuộc dạng tựa chuẩn 2 (dạng tựa chuẩn 3, dạng

tựa chuẩn Boye-Codd) thì y id, ta có Ry thuộc dạng tựa chuẩn 2 (dạng tựa

chuẩn 3, dạng tựa chuẩn Boye-Codd).

Mệnh đề 1.21[3], [5]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), F là tập các PTH trên R. Khi

đó, nếu R thuộc dạng tựa chuẩn 2 thì R thuộc dạng tựa chuẩn 1.

Mệnh đề 1.22[3], [5]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), F là tập các PTH trên R. Khi

đó, nếu R thuộc dạng tựa chuẩn 3 thì R thuộc dạng chuẩn 2.

Mệnh đề 1.23[3], [5]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), F là tập các PTH trên R. Khi

đó, nếu R thuộc dạng tựa chuẩn Boye-Codd thì R thuộc dạng chuẩn 3.

Mệnh đề 1.24[3], [5]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), F là tập các PTH trên R. Khi

đó, nếu x id sao cho Rx thuộc dạng chuẩn 2 (chuẩn 3, chuẩn Boye-Codd)

thì R thuộc dạng tựa chuẩn 2 (dạng tựa chuẩn 3, dạng tựa chuẩn Boye-Codd).

Mệnh đề 1.25[3], [5]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), Fh là tập các PTH trên R. Khi

đó, nếu x id sao cho mọi thuộc tính Rx đều là thuộc tính khóa thì R thuộc

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

dạng chuẩn 3.

1.2.6.3. Tựa chuẩn hóa lược đồ khối

Định nghĩa 1.14[3]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), F là tập các PTH trên R.

Phép tách lƣợc đồ khối R là thay thế nó bởi một tập các lƣợc đồ khối =

{R1, R2,…, Rk}, ở đây Ri, i = 1..k là các lƣợc đồ khối con của R có dạng Ri =

(id; Ai1, Ai2, …, Aij) với {Ai1, Ai2, …, Aij} {A1, A2,…, An}

a. Phép tách không mất mát thông tin

= Cho lƣợc đồ khối R = (id; A1, A2,…, An), F là tập các PTH trên R,

{R1, R2,…, Rk} là một phép tách của R. Khi đó, ta nói phép tách này là không

mất thông tin đối với F nếu với mọi khối r trên R thỏa F thì:

(1) r = R1(r)* R2(r)*…* Rk(r)

Nói cách khác, khối r là kết nối tự nhiên của các khối là phép chiếu của

nó trên mỗi Ri.

Ta ký hiệu m (r) là vế phải của (1), khi đó điều kiện để một phép tách

không mất thông tin là r = m (r).

Mệnh đề 1.26[3]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), r là một khối trên R, ri = Ri(r).

Khi đó ta có:

a) r m (r).

b) Nếu s = m (r) thì Ri(r) = ri.

c) m ( m (r) ) = m (r).

b. Kiểm tra phép không mất mát thông tin

Định nghĩa 1.15[3]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), Fh là tập các PTH trên R. Fh

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

là nhƣ nhau x id. đƣợc gọi là tập đầy đủ các PTH nếu Fhx =

Mệnh đề 1.27[3]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), Fh là tập các PTH trên R,

khi đó luôn tồn tại một tập đầy đủ các PTH F*h thỏa mãn: Fh F*h Fh

Chứng minh

, x id, khi đó: Ta có Fhx =

Nếu Fhx là nhƣ nhau x id thì ta chỉ việc chọn F*h = Fh.

id) không giống nhau thì ta tiến hành nhƣ sau: Nếu các Fhx (x

Y , + Lần lƣợt duyệt từng Fhx, với mỗi phụ thuộc X Fhx, X =

Y = , A, B Y’ {1, 2, …, n} ta bổ sung vào các Fhy PTH X’ Fhy,

X’ = , Y’ =

. + Sau cùng, ta đặt F*h =

Khi đó F*h chính là tập đầy đủ các PTH thỏa mãn:

Fh F*h Fh

Thuật toán 1.4(Khẳng định phép tách có mất thông tin hay không)

Để kiểm tra tính bảo toàn thông tin của phép tách trên lƣợc đồ khối, ta

chuyển về kiểm tra tính bảo toàn thông tin trên một lát cắt tùy ý.

Input: Lƣợc đồ khối R = (id; A1, A2,…, An), tập đầy đủ các PTH Fh trên

R, phép tách = {R1, R2,…, Rk}, Ri = (id; Xi), Xi {A1, A2,…, An}, i = 1..k.

Output: Khẳng định phép tách có mất thông tin hay không?

Phương pháp

Xây dựng bảng gồm n cột, k hàng: hàng i tƣơng ứng với lƣợc đồ Ri, cột

j tƣơng ứng với thuộc tính Aj. Tại vị trí có tọa độ (i, j), nếu Aj thuộc Xj thì ta

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

ghi aj, ngƣợc lại ta ghi bj.

Y Ta xét Fhx với một x nào đó, với mỗi PTH X Fhx, nếu tồn tại hai

hàng mà tất cả các cột tƣơng ứng với các thuộc tính của X có giá trị nhƣ nhau

thì ta làm cho các cột ứng với các thuộc tính của Y cũng có giá trị nhƣ nhau

trong hai hàng này theo nguyên tắc: Nếu có một ký hiệu aj trong các cột ứng

với các thuộc tính của Y thì đồng nhất các ký hiệu là aj, ngƣợc lại đồng nhất

bằng một trong các ký hiệu bij. Tiếp tục áp dụng các PTH cho bảng (kể cả

việc lặp lại các PTH đã áp dụng) cho tới khi không thể thay đổi đƣợc giá trị

nào trong bảng nữa.

Nếu trong bảng có một hàng gồm các ký hiệu a1, a2, ..., an thì phép tách

không bảo toàn thông tin.

x = {R1x, R2x, ..., Rkx}, Rix = (x; Xi), Xi

id có phép tách bảo toàn thông tin Theo thuật toán trên, ta có Rx, x

{A1, A2, ..., An}, i = 1..k.

Mặt khác, Fh là tập đầy đủ các PTH nên Fhx là nhƣ nhau đối với mọi lát

cắt Rx. Nhƣ vậy, các phép tách x = {R1x, R2x, ..., Rkx} cũng là nhƣ nhau đối

với mọi lát cắt Rx.

Khi đó, phép tách = là phép tách bảo toàn thông tin trên lƣợc đồ

khối R = (id; A1, A2,…, An).

Mệnh đề 1.28[3]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), Fh là tập đầy đủ các PTH trên R,

= {R1, R2} là một phép tách trên R, R1 = (id; A11, A12,…, A1i), R2 = (id; A21,

A22,…, A2j), trong đó {A11, A12,…, A1i}, {A21, A22,…, A2j} {A1, A2,…, An}.

Phép tách là không mất mát thông tin nếu và chỉ nếu:

{A11, A12,…, A1i} {A21, A22,…, A2j} {A11, A12,…, A1i} \ {A21, A22,…, A2j}

hoặc

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

{A11, A12,…, A1i} {A21, A22,…, A2j} {A11, A12,…, A1j} \ {A21, A22,…, A2i}

Chứng minh

Bằng cách chuyển về xét trên lát cắt Rx, thì khi đó Rx là một quan hệ và

điều kiện cần và đủ nêu trong mệnh đề này chính là nội dung của định lý

Risanen (1977) đã biết trong mô hình quan hệ. Từ tổ hợp của các phép tách

trên các lát cắt (các phép tách này giống nhau) tạo thành phép tách trên khối.

Ta suy ra điều cần chứng minh.

Hệ quả 1.2

Cho lƣợc đồ khối R = (id; A1, A2,…, An), Fh là tập đầy đủ các PTH trên

+ thì phép tách

R, và X, Y {A1, A2,…, An}, nếu X Y thuộc Fh = {R1,

R2} với R1 = {id; XY}, R2 = {id; XZ} trong đó Z = {A1, A2,…, An} \ XY là

1.2.6.4. Phép tách bảo toàn PTH

phép tách không mất thông tin.

Cho lƣợc đồ khối R = (id; A1, A2,…, An), Fh là tập đầy đủ các PTH trên

R, = {R1, R2,...,Rk} là một phép tách của R. Fhi là hình chiếu của Fh lên Ri, ký

Y hiệu Ri(Fh), là tập tất cả các PTH X Fh sao cho XY là tập thuộc tính

của Ri. Khi đó, ta nói phép tách này bảo toàn tập PTH Fh nếu hợp của tất cả các

PTH trong Ri(Fh) với i = 1..k suy diễn logic ra tất cả các PTH trong Fh.

Mệnh đề 1.29[3]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), Fh là tập đầy đủ các PTH trên

R, = {R1, R2,..., Rk} là một phép tách không mất thông tin của R đối với Fh.

Với mỗi i = 1, 2, ..., k, ta gọi Fhi là hình chiếu của Fh lên Ri và đặt = (S1, S2,

..., Sm) là một phép tách không mất thông tin của Ri đối với Fhi. Khi đó, phép

tách R thành (R1, R2,..., Ri-1, S1, S2, ..., Sm, Ri+1, ..., Rk) là không mất thông tin

đối với Fh.

Giả sử có R, Fh, nhƣ đã nói ở trên, = (R1, R2,..., Rk, Rk+1,..., Rn) là

một phép tách của R chứa các lƣợc đồ của thì là một phép tách không mất

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

thông tin.

Thuật toán 1.5(Tách không mất thông tin về dạng tựa chuẩn Boye-

Codd)[3]

Ta sẽ chuyển thành phép tách không mất thông tin về dạng chuẩn

Boye-Codd trên các lát cắt.

Input: Lƣợc đồ khối R = (id; A1, A2,…, An), Fh là tập đầy đủ các PTH

trên R.

Output: Phép tách = {R1, R2,..., Rk} không mất thông tin, Ri với mọi i

= 1, 2, ..., k đều ở dạng tựa chuẩn Boye-Codd với các PTH là hình chiếu của

Fh lên các Ri.

Phương pháp

x sẽ đƣợc tách tiếp với một phép tách không mất mát thông tin đối với Fhx.

Xây dựng phép tách x đối với Rx theo phƣơng pháp lặp, sau mỗi lần lặp,

Ban đầu, phép tách x chỉ gồm Rx. Tiếp theo, nếu S là một LĐQH trong

x không ở dạng chuẩn Boye-Codd, ta xét một PTH X

A của S, với điều

kiện X không chứa khóa của S và A X. Khi đó, thay thế S bởi S1, S2 với

S1= (x, AX), S2 = (x, Y), trong đó Y là các thuộc tính còn lại của S sau khi

loại bỏ A.

Tiếp tục quá trình cho đến khi mọi lƣợc đồ con đều ở dạng chuẩn Boye-

Codd. Nhƣ vậy, ta xây dựng đƣợc phép tách không mất mát thông tin chuẩn

hóa Rx về dạng chuẩn Boye-Codd. Với phép tách x = {R1x, R2x,..., Rkx}.

Khi đó, phép tách , i=1..k chính là = {R1, R2,..., Rk} với Ri =

phép tách cần tìm, các khối Ri đều ở dạng tựa chuẩn Boye-Codd.

Thuật toán 1.6(Tách bảo toàn tập PTH và chuyển về dạng tựa chuẩn 3)

Input: Lƣợc đồ khối R = (id; A1, A2,…, An), Fh là tập đầy đủ các PTH

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

trên R, không mất tính tổng quát, ta giả sử Fh là phủ tối thiểu.

Output: Phép tách = {R1, R2,..., Rk} bảo toàn tập PTH, Ri với mọi i =

1, 2, ..., k đều ở dạng tựa chuẩn 3 với các PTH là hình chiếu của Fh lên các Ri.

Phương pháp

Xây dựng phép tách x đối với Rx theo cách sau:

Nếu có những thuộc tính nào đó của Rx nhƣng không xuất hiện trong

bất kỳ vế trái hoặc phải của một PTH nào trong Fhx thì có thể tạo một lƣợc đồ

riêng xác định trên những thuộc tính này và loại nó ra khỏi R.

Nếu có PTH liên quan tới tất cả các thuộc tính của Rx thì kết quả chính

là Rx.

Ngoài ra, kết quả bao gồm các lƣợc đồ (x, XA) đối với một PTH (x, X)

(x, A) trong Fhx. Trong trƣờng hợp có các PTH X A1, X A2, ..., X

An thì ta sử dụng lƣợc đồ (x,XA1A2 ...An) thay cho (x, Ai) với i=1..n.

Phép tách = {R1x, R2x,..., Rkx} vừa xây dựng đã chuẩn hóa Rx về dạng

chuẩn 3.

Khi đó, phép tách , i=1..k chính là = {R1, R2,..., Rk}, với Ri =

phép tách cần tìm, các khối Ri đều ở dạng tựa chuẩn 3.

1.2.7. Khái niệm về phủ và phủ tối thiểu của tập phụ thuộc hàm

Định nghĩa 1.16[3], [5]

Lƣợc đồ khối R = (id; A1, A2,…, An), F và G là các tập PTH trên R. Ta

nói F tƣơng đƣơng với G và ký hiệu F G nếu F+ = G+.

Nếu F và G là tƣơng đƣơng thì ta nói F phủ G hay G phủ F.

Định nghĩa 1.17[3], [5]

Lƣợc đồ khối R = (id; A1, A2,…, An), tập F các PTH đƣợc gọi là không dƣ

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

thừa nếu không có tập con thực sự F’ của F mà F’ F. Ngƣợc lại F là dƣ thừa.

Định nghĩa 1.18[3], [5]

Y F, X Lƣợc đồ khối R = (id; A1, A2,…, An), F là các PTH, X

Y là một PTH đầy đủ trong F nếu X’ X sao cho F (F-{X Y} {X’

Y}). Khi đó, Y đƣợc gọi là phụ thuộc đầy đủ vào X.

Định nghĩa 1.19[3], [5]

Lƣợc đồ khối R = (id; A1, A2,…, An), tập F là các PTH là tối thiểu nếu:

 Vế phải của các PTH trong F chỉ có một thuộc tính (không có thuộc

tính nào ở vế phải là dƣ thừa).

 Không tồn tại X Y F và X’ X sao cho: F (F-{X Y} {X’

Y}) (không có thuộc tính nào ở vế trái dƣ thừa)

 Không tồn tại X Y F sao cho: F (F-{X Y}) (không có PTH

nào dƣ thừa).

Mệnh đề 1.30[3], [5]

là các tập Cho lƣợc đồ khối R = (id; A1, A2,…, An), Fh và Fhx =

PTH trên R, Rx tƣơng ứng, Fh’ là phủ tối thiểu của Fh. Khi đó, Fhx’ =

là phủ tối thiểu của Fhx.

Mệnh đề 1.31[3], [5]

Cho lƣợc đồ khối R = (id; A1, A2,…, An), Fh và Fhx là các tập PTH trên

, A R, Rx tƣơng ứng, Fh = id, Fhx’ là phủ tối thiểu của Fhx. Khi đó, Fh’

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

= là phủ tối thiểu của Fh.

Định lý[3], [5]

là các tập Cho lƣợc đồ khối R = (id; A1, A2,…, An), Fh và Fhx =

PTH trên R, Rx tƣơng ứng, Fh’ là phủ tối thiểu của Fh khi và chỉ khi Fhx’ =

là phủ tối thiểu của tập Fhx.

Kết luận chƣơng 1

Các nội dung chính đã trình bày trong chƣơng này bao gồm: Các khái

niệm cơ bản về mô hình dữ liệu dạng khối nhƣ: Định nghĩa khối, lát cắt, lƣợc

đồ khối... và các đặc trƣng cơ bản khối và lƣợc đồ khối.

Tác giả cũng đã trình bày các khái niệm về bao đóng, khóa,PTH...

trong mô hình dữ liệu dạng khối. Tìm hiểu một số thuật toán tìm bao đóng và

khóa của lƣợc đồ khối.

Một số vấn đề về các dạng chuẩn, các dạng tựa chuẩn, tựa chuẩn hóa

trên lƣợc đồ khối; các khái niệm về phủ và phủ tối thiểu của tập PTH cũng

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

đƣợc tác giả trình bày trong chƣơng này.

CHƢƠNG 2. PHÉP DỊCH CHUYỂN LƢỢC ĐỒ KHỐI

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ệ. Mô hình mở rộng này đƣợc xây dựng trên cơ sở kế thừa cơ sở toán học

chặt chẽ từ mô hình quan hệ và mở rộng và bổ sung các đặc trƣng cần thiết.

Lý thuyết về phép dịch chuyển LĐQH nhằm nâng cao hiệu quả của các

thuật toán tìm bao đóng và tìm khóa phục vụ cho các quá trình chuẩn hóa

LĐQH. Qua đó cũng giúp tìm hiểu sâu hơn về các đối tƣợng khác trong quản

lý về cơ sở dữ liệu .

Phép dịch chuyển lƣợc đồ khối đƣợc đề xuất với mục đích tƣơng tự với

phép dịch chuyển LĐQH trong mô hình quan hệ. Trƣớc khi tìm hiểu phép

dịch chuyển lƣợc đồ khối, chúng ta cùng tìm hiểu phép dịch chuyển LĐQH và

một số vấn đề liên quan.

2.1. Phép dịch chuyển lƣợc đồ quan hệ

2.1.1. Định nghĩa

Định nghĩa 2.1 [2]

Cho hai LĐQH a = , b = và tập thuộc tính M U. Ta nói

LĐQH b nhận đƣợc từ LĐQH a qua phép dịch chuyển theo tập thuộc tính M,

nếu sau khi loại bỏ mọi xuất hiện của các thuộc tính của M trong sơ đồ a thì

thu đƣợc sơ đồ b.

Nếu sau khi thực hiện phép dịch chuyển theo M cho LĐQH a ta thu

đƣợc LĐQH b thì ta viết b = a\M.

Thao tác loại bỏ M đƣợc thực hiện trên sơ đồ a = để thu đƣợc sơ

đồ b= nhƣ sau:

1. Tính V = U\M có độ phức tạp O(n) với n là số lƣợng thuộc tính

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

trong U.

2. Mỗi PTH X Y trong F ta tạo ra PTH X\M Y\M cho G. Thủ

tục này ký hiệu là G=F\M. Tính F\M đòi hỏi độ phức tạp O(mn) với m

là số lƣợng PTH trong F.

Nhƣ vậy, b=a\M = đƣợc thực hiện với độ phức tạp O(mn),

tức là tuyến tính theo chiều dài dữ liệu vào (của LĐQHa).

Sau khi thực hiện thủ tục G = F\M nếu:

+ G chứa các PTH tầm thƣờng (dạng X Y, X Y) thì ta loại các PTH

này khỏi G.

+ G chứa các PTH trùng lặp thì ta bớt các PTH này.

Nhận xét: Phép dịch chuyển thoả tính hợp thành và giao hoán, cụ thể

nếu a là LĐQH trên tập thuộc tính U và X, Y là hai tập con rời nhau của U thì

a\XY = (a\X)\Y = (a\Y)\X

2.1.2. Thuật toán dịch chuyển lược đồ quan hệ

Thuật toán dƣới đây mô tả phép dịch chuyển một LĐQH với độ phức

tạpO(mn)

Thuật toán 2.1[2](Thuật toán dịch chuyển LĐQH)

Algorithm Translation

Format: Translation(a,M)

Input:

- LĐQH a=

- Tập thuộc tính M U

Output:

- LĐQH b= = a\M, V=U\M, G = F\M.

Method

V:=U\M;

G:=

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

For each FD L R in F do

G:=G {L\M R\M};

Endfor;

G:=Natural_Reduced(G);

Return ;

End Translation;

Phủ thu gọn tự nhiên (Natural_Reduced) [2]

Định nghĩa: Cho hai PTH F và G trên cùng một tập thuộctínhU. G

làphủ thu gọn tự nhiên của F nếu:

1. G là một phủ của F

2. G có dạng thu gọn tự nhiên theo nghĩa sau:

2a. Hai vế trái và phải của mọi PTH trong G rời nhau (không

giao nhau) f G: LS(f) LS(f) =

2b. Các vế trái của mọi PTH trong G khác nhau đôi một.

f, g G: f g LS(f) LS(g)

Thuật toán 2.2 (Tìm phủ thu gọn tự nhiên) Format: Natural_Reduced(F) Input: - Tập PTH F Output - Một phủ thu gọn tự nhiên G của F

(i). G F

(ii). L→R G: L R =

(iii). Li→Ri, Lj→Rj G: i j Li→Lj

Method

G:= ; for each FD L→R in F do Z:= R\L

then

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

ifZ if there is an FD L→Y in G then Replace L→Y in G by L→YZ

else add L→Z to G; end if;

end if;

endfor; Return G;

End Natural_Reduced;

Thủ tục Natural_Reduced(G) đƣa tập phụ thuộc hàm G về dạng thu gọn

tự nhiên bằng cách loại khỏi G những phụ thuộc hàm tầm thƣờng (có vế trái

chứa vế phải), chuyển đổi mỗi phụ thuộc hàm có hai vế trái phải rời nhau và

gộp các phụ thuộc hàm có cùng vế trái.

Định lý sau đây thiết lập công thức biểu diễn bao đóng của tập thuộc

tính theo phép dịch chuyển LĐQH.

Định lý 2.1[2] (Định lý công thức biểu diễn bao đóng theo phép dịch

chuyển LĐQH).

F = XY+

F\X

Cho LĐQH a= và hai tập con rời nhau X và Y trong U. Khi đó (XY)+

Chứng minh

Đặt V=U\X và G=F\X và để ý rằng do X Y= và X không xuất hiện

trong V và G nên theo định nghĩa bao đóng của tập thuộc tính ta có

G= . Ta chứng minh bằng quy nạp theo số bƣớc xây dựng các dãy (XY)(h) và Y(h), h =0,1,... theo thuật toán bao đóng của các tập thuộc tính XY và Y tƣơng

X Y+

ứng với các tập PTH F và G cụ thể ta chứng minh bất biến.

(XY)(h) = XY(h), h = 0,1,... Cơ sở: h = 0. Ta có (XY)(0) = XY và Y(0) = Y, do đó (XY)(0) = XY(0) =

Quy nạp: Giả sử với h 0 ta có (XY)(h) = XY(h). Ta cần chứng minh:

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

(XY)(h+1) = XY(h+1)

Ta sẽ chỉ ra rằng khi chuyển từ bƣớc h sang bƣớc h+1 hai tập (XY)(h) và XY(h) sẽ đƣợc bổ sung thêm cùng một số thuộc tính. Trƣớc hết ta để ý rằng

do X Y= và X không có mặt trong LĐQH b=a\X = nên với mọi

h=0,1,2,... ta luôn có X Y(h) = . Ngoài ra do dãy (XY)(h) đơn điệu không

X nên với mọi h = 0,1,2,... ta luôn có (XY)h X. Từ

giảm và (XY)(0) = XY các nhận xét này và từ giả thiết quy nạp (XY)(h) = XY(h) ta suy ra

L U: L (XY)(h) = XY(h) L\X Y(h) và

Z U\X: Z Y(h) XZ XY(h) = (XY)(h)

Giả sử PTH L R F thoả tính chất L (XY)(h). Khi đó L\X R\X G

và L\X Y(h). Từ (XY)(h) = XY(h) ta suy ra R(XY)(h) = RXY(h) = (R\X)XY(h).

Ngƣợc lại, giả sử Z P G và Z Y(h). Theo định nghĩa của phép dịch

chuyển theo X, trong F tồn tại một PTH L R để Z = L\X và P = R\X. Khi đó

XZ XY(h) = (XY)(h) và do đó R(XY)(h) = RXY(h) = (R\X)XY(h) =

ta có L PXY(h).

Để ý rằng mọi tập X, ta có X = X và X = . Từ nhận xét này ta

suy ra hệ quả sau:

Hệ quả 2.1[2](Hệ quả công thức tính bao đóng cho một tập thuộc tính)

F = X(

F/X.

Cho LĐQH a = và tập X U. Khi đó X+ )+

Cho LĐQH a = ta nhắc lại các ký hiệu sau:

- Uo là các tập thuộc tính không khoá, hay phi nguyên thuỷ, tức là thuộc

tính không xuất hiện trong bất kỳ khoá nào của a.

- UK là tập thuộc tính khóa, hay nguyên thuỷ, tức là thuộc tính có trong

một khoá nào đó của a (hợp của các khoá).

- UI là tập các thuộc tính có trong mọi khoá tức là giao của các khoá

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

của a.

Rõ ràng UI UK

Ta cũng biết phân hoạch U=Uo|UK và K Key(a), X Uo

). (K UK) (K X = K Uo =

Ngoài ra theo tính chất của tập hợp X,Y U:X Y= X\Y = X

Để ý rằng nếu M là siêu khoá của LĐQH a = thì:

Z Uo ta có M\Z cũng là siêu khoá của a. Nói cách khác từ một siêu

khoá bất kỳ bỏ đi một số thuộc tính không khoá ta vẫn thu đƣợc siêu khoá.

2.1.3. Bổ đề về siêu khoá trong phép dịch chuyển lược đồ quan hệ

Bổ đề 2.1[2](Bổ đề về siêu khóa trong phép dịch chuyển LĐQH).

Cho hai LĐQHa = , b = và X U. Biết b=a\X. Khi đó:

i) Nếu M là siêu khóa của a thì M\X là siêu khoá của b.

ii) Nếu Z là siêu khoá của b thì ZX là siêu khoá của a. Nói riêng nếu

X Uo và Z là siêu khoá của b thì Z là siêu khoá của a.

Chứng minh

F\X. Từ đẳng thức

F = XP+

F (XP)+ ta suy ra P+

i) Giả sử M là siêu khoá của a. Đặt P=M\X, ta có X P= và M XP.

F\X = V. Vậy P = M\X là

F\X =

Vì M là siêu khoá của a, vận dụng tính đồng biến của bao đóng và công thức biểu diễn bao đóng ta có, U = XV = M+ F\X, X V= và X P+ XV= XP+

siêu khoá của b.

ii) Đảo lại, giả sử Z là siêu khóa của b = a\X. Khi đó Z X = và

G=V. Đặt M = XZ, ta có M+

F = (XZ)+

F = XZ+

F\X = XZ+

G = XV = U. Vậy XZ

Z+

là siêu khoá của a.

Nếu X Uo thì ta có thể loại bỏ trong XZ bộ phận thuộc tính không

khoá X để thu đƣợc Z là siêu khoá của a.

Hệ quả 2.2[2](Hệ quả về siêu khoá trong phép dịch chuyển LĐQH)

Cho LĐQH a = và tập thuộc tính X U. Khi đó nếu Z là siêu

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

khoá của sơ đồ a\X+ thì XZ là siêu khoá của sơ đồ a.

Chứng minh Đặt b = a\X+. Theo bổ đề về siêu khoá trong phép dịch chuyển LĐQH, nếu Z là siêu khoá của b thì X+Z là siêu khoá của a, ta có (X+Z)+ = U. Theo tính chất 5 của bao đóng của tập thuộc tính, (X+Z)+ = (XZ)+ = U. Từ đây suy

ra XZ là siêu khoá của a.

Để ý rằng hệ quả trên không hoàn toàn tƣơng tự nhƣ bổ đề về siêu khoá

trong phép dịch chuyển LĐQH. Điểm khác nhau chính là lƣợng dịch chuyển

trong bổ đề về siêu khoá là X, trong hệ quả này là bao đóng của X, X+ X.

Bổ đề 2.2[2](Bổ đề về khoá trong phép dịch chuyển LĐQH)

Cho hai LĐQH a = , b = và tập thuộc tính X Uo. Biết

b= a\X. Khi đó Key(a) = Key(b)

Chứng minh

Giả sử K Key(a). Khi đó nói riêng K là siêu khoá của a. Do K UK,

nên theo bổ đề về siêu khóa trong phép dịch chuyển X Uo, UK Uo =

LĐQH, K=K\X là siêu khoá của b. Giả sử K chứa siêu khoá M của b. Khi đó

lại theo bổ đề về siêu khoá trong phép dịch chuyển LĐQH ta có M là siêu

khoá của a. Do K là khoá của a, M là siêu khoá của a chứa trong K, nên theo

tính chất tối thiểu của khoá ta phải có M = K. Vậy K là khoá của b.

Đảo lại, nếu K là khóa của b thì K X= và theo bổ đề về siêu khoá

trong phép dịch chuyển LĐQH ta có M\X là siêu khoá của b. Do K là khoá

của b và K chứa M nên M = K. Vậy K là khoá của a.

2.1.4. Dịch chuyển lược đồ quan hệ về dạng cân bằng

2.1.4.1. Sơ đồ cân bằng[2]

LĐQH a = đƣợc gọi là cân bằng nếu tập PTH F trong a thoả 4

tính chất sau:

1. Hợp các vế trái, các vế phải của các PTH trong F đúng bằng tập

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

thuộc tính U: LS(F) = RS(F) = U

2. F không chứa các PTH tầm thƣờng, tức là các PTH có vế trái chứa

vế phải: X,Y U: X Y (X Y F)

3. Cả hai vế trái và phải của mọi PTH trong F rời nhau (không giao

nhau): f F: LS(f) RS(f) =

4. Các vế trái của mọi PTH trong F khác nhau đôi một:

f, g F: LS(f) = LS(g) f = g

Trong đó:

LS(F): Tập các thuộc tính xuất hiện trong vế trái.

và

RS(F): Tập các thuộc tính xuất hiện trong vế phải.

Cụ thể là:

Nhóm tính chất 2-4 cho biết F có dạng thu gọn tự nhiên. Nhƣ vậy

LĐQH là cân bằng khi và chỉ khi tập PTH có dạng thu gọn tự nhiên và mọi

thuộc tính đều xuất hiện ít nhất một lần ở vế trái, một lần ở vế phải.

2.1.4.2. Một số tính chất của sơ đồ cân bằng

Ngoài 4 tính chất trên sơ đồ cân bằng (SĐCB)có những tính chất sau

đây[2]:

5. Nếu tập PTH F trong LĐQH a = ở dạng thu gọn tự nhiên và

chỉ có một PTH thì a không thể là SĐCB. Thật vậy, nếu F ={X Y} và F ở

dạng thu gọn tự nhiên thì LS(F) = X Y = RS(F), vi phạm tính chất 1.

6. Từ tính chất 5 ta suy ra LĐQH chỉ có một thuộc tính thì không thể là

SĐCB. Thật vậy, gọi thuộc tính duy nhất là A, ta chỉ thấy có 4 khả năng tạo

các PTH sau đây:

a. A A (Tầm thƣờng)

b. A (Tầm thƣờng)

c. (Tầm thƣờng)

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

d. A

Nhƣ vậy chỉ có thể chọn U=A và F= hoặc F={ A}.

Trƣờng hợp thứ nhất U=A, F= cho ta LS(F) = RS(F) = U.

Trƣờng hợp thứ hai U=A, F={ A} cho ta LS(F)=

U=RS(F). Cả hai trƣờng hợp đều không cho SĐCB.

Để ý rằng trƣờng hợp U= và F= ta có SĐCB ( , ).

7. Trong SĐCB a = , tập giao các khoá UI= . Thật vậy theo

công thức tính giao các khoá và theo tính chất 3 f F:RS(f) LS(f)= ta

suy ra:

f F: RS(f)\LS(f) = RS(f) do đó

theo tính 1 ta có RS(F)=U,

. do đó UI = U\M = U\U =

2.1.4.3. Thuật toán dịch chuyển lược đồ quan hệ về dạng cân bằng

Thuật toán 2.3[2](Thuật toán dịch chuyển LĐQH về dạng cân bằng)

Thuật toán BS dƣới đây thực hiện phép dịch chuyển một LĐQH về

dạng cân bằng.

Algorithm BS

//Dịch chuyển LĐQH về dạng cân bằng

Format: BS(a)

Input: - LĐQH a =

Output: - SĐCB b =

Method

1. Đưa F về dạng thu gọn tự nhiên

G:=Natural_Reduced(F);

2. Tính giao các khoá UI:= U\RS(G);

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

3. Tính lượng dịch chuyển M

3.1. P:= RS(G)\LS(G)

3.2. M:= (PUI)G

3.3. Tạo LĐQH b = ; V:=U; G:=F;

4. while M do

4.1. Dịch chuyển b theo M b:=b\M; //b=

; V:=V\M; G:=G\M

4.2. Loại khỏi G các PTH dạng X

4.3. Nhóm các PTH có cùng vế trái trong G

X Y1, X Y2,....,X Yk thành X Y1Y2...YK;

4.4. M:=V\LS(G);

Endwhile;

5. return(b);

End BS.

Lý thuyết về phép dịch chuyển LĐQH nhằm nâng cao hiệu quả của các

thuật toán tìm bao đóng và tìm khoá phục vụ cho các quá trình chuẩn hoá

LĐQH. Qua đó cũng giúp tìm hiểu sâu hơn về các đối tƣợng khác trong quản

lý về cơ sở dữ liệu.

2.2. Phép dịch chuyển lƣợc đồ khối

2.2.1. Định nghĩa

Nhƣ chúng ta đã biết, trong mô hình quan hệ, để giảm tính phức tạp của

việc xác định bao đóng, khóa trong các cơ sở dữ liệu lớn, phức tạp thì phép

dịch chuyển LĐQH đã đƣợc đề xuất. Trong mô hình cơ sở dữ liệu dạng khối,

việc xác định khóa và bao đóng càng khó khăn hơn. Chính vì vậy mà phép

dịch chuyển lƣợc đồ khối cũng đƣợc đề xuất ở đây. Nhờ việc dịch chuyển

lƣợc đồ khối mà trong nhiều trƣờng hợp việc tính bao đóng và khóa của khối

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

trở nên đơn giản hơn.

Định nghĩa 2.2[4]

Cho hai lƣợc đồ khối =(R,F), = (S,G), X , X = {x(i), x id, i

A}, A {1, 2, ..., n}. Ta nói lƣợc đồ 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:

- Tính S = R\X, R = (id; A1, A2,…, An), ở đây, ta loại bỏ các thuộc tính

A) trong R, thủ tục này có độ phức tạp là O(nk), với k là số phần tử Ai (i

của A.

- Với mỗiPTH từ M N trong F, với M, N , ta tạo mộtPTH

mới M\X N\X trong G. 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 PTH 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 F = 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 bỏ

chúng khỏi G.

+ Nếu G chứa các PTH trùng nhau thì ta loại bỏ bớt các PTH này (G

không chứa các PTH trùng nhau).

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Nhận xét:

1. Cho hai lƣợc đồ khối =(R,F), = (S,G), X , 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ĐQH và phép dịch chuyển theo tập thuộc tính X trong lƣợc

đồ khối này trở thành phép dịch chuyển theo tập thuộc tính X từ LĐQH về

LĐQH trong mô hình dữ liệu quan hệ.

2. Cho hai lƣợc đồ khối =(R,F), = (S,G), X , 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: = \ X thì:

\X. S = R\X, Gh = Fh \ X =

), x id. Từ đó, ta có: Ghx = Fhx \ (X

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

lại chính là việc dịch chuyển LĐQH trong mô hình dữ liệu quan hệ.

2.2.2. Sự khác biệt giữa phép chuyển dịch lược đồ khối so với phép dịch

chuyển lược đồ quan hệ

Phép dịch chuyển lƣợc đồ khối thực chất là một mở rộng của phép dịch

chuyển LĐQH nên hầu hết các nghiên cứu liên quan đến phép dịch chuyển

lƣợc đồ khối đều cần kế thừa kết quả từ các nghiên cứu phép dịch chuyển

LĐQH.

Xét lƣợc đồ khối =(R, F), X , X = {x(i), x id, i A}, A

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

{1, 2, ..., n}. Lƣợc đồ = (S,G) là lƣợc đồ kết quả phép dịch chuyển của từ

lƣợc đồ qua 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ĐQH và phép dịch chuyển theo tập thuộc tính X

trong lƣợc đồ khối này trở thành phép dịch chuyển theo tập thuộc tính X từ

LĐQH về LĐQH trong mô hình dữ liệu quan hệ.

Việc dịch chuyển trên khối có thể đƣợ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 lại chính là việc dịch chuyển

LĐQH trong mô hình dữ liệu quan hệ.

Phép dịch chuyển LĐQH a = theo tập thuộc tính M đƣợc thực

hiện với độ phức tạp tuyến tính theo chiều dài dữ liệu vào: O(mn) (với n là số

lƣợng thuộc tính trong U; m là số lƣợng PTH trong F).

Phép dịch chuyển lƣợc đồ khối α = (R, F) theo tập thuộc tính X có độ

phức tạp O(mnk) (với n là số lƣợng thuộc tính trong R; m là số lƣợng các

PTH trong F; k là số phần tử của A).

Phép dịch chuyển lƣợc đồ khối có thể đƣợc thực hiện thông qua tập

PTH Fh hoặc thông qua tập PTH Fhx nghĩa là có thể đƣợc thực hiện trên khối

hoặc thông qua các lát cắt.

2.2.3 Một số thuật toán dịch chuyển lược đồ khối

Thuật toán 2.4(Phép dịch chuyển 1)[4]

Algorithm Dich_chuyen_1

Format: Dich_chuyen_1( , X)

Input:

- Lược đồ khối = (R,F),

- X , X = {x(i), x id, i A}, A

{1, 2, ..., n}.

Output: = \ X = (V,G), V = R\X, G = F\X.

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Method

V:=R\X;

G := ;

For each L R in F do

G := G (L\X R\X);

Endfor;

G:= Rutgon(G);

Return(V,G);

End Dich_chuyen_1;

Thủ tục Rutgon(G) sẽ đƣa G về dạng rút gọn tự nhiên, nghĩa là loại bỏ

các PTH tầm thƣờng, đƣa các PTH về dạng có vế phải và trái rời nhau, gộp

các PTH có cùng vế trái.

Trong trƣờng hợp tập PTH F có dạng Fh thì việc dịch chuyển lƣợc đồ

khối lại chính là dịch chuyển lƣợc đồ của các lát cắt trong khối. Từ đó, ta có

thuật toán sau:

Thuật toán 2.5(Phép dịch chuyển 2)[4]

Algorithm Dich_chuyen_2

Format: Dich_chuyen_2( , X)

Input:

- Lược đồ khối = (R, Fh),

- X , X = {x(i), x id, i A}, A

{1, 2, ..., n}.

Output: = \ X = (V,G), V = R\X, G = F\X.

Method

V:=R\X;

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

G := ;

For each x in id do

For each L R in Fhx do

G := G (L\X R\X);

Endfor;

G:= Rutgon(G);

Return(V,G);

End Dich_chuyen_2;

Bản chất của phép dịch chuyển lƣợc đồ khối là loại bỏ khỏi lƣợc đồ

ban đầu một số thuộc tính không quan trọng theo nghĩa chúng không làm

ảnh hƣởng đến kết quả tính toán các đối tƣợng đang quan tâm nhƣ bao đóng,

khóa, phản khóa... Mặc dù lƣợc đồ khối thu đƣợc qua phép dịch chuyển

không tƣơng đƣơng với lƣợc đồ ban đầu, nhƣng ta có thể thu đƣợc các đối

tƣợng cần tìm bằng những phép toán đơn giản nhƣ loại bỏ hoặc thêm một số

thuộc tính. Sau khi loại bỏ một số thuộc tính thì một số PTH sẽ đƣợc loại bỏ

theo, vì chúng trở thành các PTH tầm thƣờng (có vế trái chứa về phải) hoặc

mang thông tin tiền định.

Nhƣ vậy, sau khi thực hiện phép dịch chuyển, ta thu đƣợc lƣợc đồ với

kích thƣớc nhỏ hơn và có thể có số FTH ít hơn lƣợc đồ ban đầu.

Một nhận xét tự nhiên là nếu kích thƣớc của lƣợc đồ càng nhỏ thì các

thao tác tìm khóa, tìm bao đóng càng đơn giản. Sau đây chúng ta cùng tìm

hiểu các kỹ thuật biểu diễn bao đóng và khóa của lƣợc đồ khối ban đầu thông

qua lƣợc đồ dịch chuyển.

2.2.4. Biểu diễn bao đóng qua phép dịch chuyển

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Mệnh đề 2.1[4]

, X = Cho lƣợc đồ khối =(R,Fh), R = (id; A1, A2,…, An), X, Y

{x(i), x id, i A}, Y = {x(i), x id, i B}, A,B {1, 2, ..., n}, A B= .

Khi đó:

Fh = X(Y)+

Fh\X

a) (XY)+

Fh = X(

+ Fhx\X).

b) (XY)+

Fh =

+ Fhx\X].

c) (XY)+

Chứng minh

- Trƣớc hết, ta chứng minh c)

Dựa vào điều kiện cần và đủ của bao đóng trên lƣợc đồ khối, ta có:

Fh =

+ Fhx.

(XY)+

Mặt khác, theo giả thiết, ta có: A B =

Suy ra: = , x id.

Tiếp theo, ta chứng minh:

+ Fhx =

+ Fhx.

(1)

, Khi đó, Để ngắn gọn, ta ký hiệu: Xx = , Yx =

Fhx =Xx (Yx)+

Fhx\X

(2) đẳng thức (1) trở thành: (XxYx)+

Mặt khác, theo công thức tính bao đóng của tập XxYx dựa vào phép

dịch chuyển LĐQH theo tập Xx trong lát cắt Rx đã đƣợc chứng minh, ta có:

Fhx = Xx(Yx)+

Fhx\Xx

(3) (XxYx)+

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Tuy nhiên: Fhx\X = Fhx\Xx

Fhx\Xx = Xx(Yx)+

Fhx\X

(4) Do đó (XxYx)+

Fhx\X nghĩa là (1) đã đƣợc chứng minh.

Từ (3) và (4) ta có: Fhx = Xx(Yx)+ (XxYx)+

+ Fhx=

+ Fhx\X].

Từ(1) ta có:

Fh =

+ Fhx\X]

Suy ra (XY)+

- Ta chứng minh b)

Theo chứng minh c) ở trên, ta có

+ Fhx\X].

Fh =

(XY)+

Mà X =

Fh = X(

+ Fhx\X).

Suy ra: (XY)+

- Ta chứng minh a)

Fh = X(

Fhx\X).

Theo kết quả ở phần b), ta có: (XY)+ )+

Đựa vào điều kiện cần và đủ của bao đóng trên lƣợc đồ khối, ta có:

Fh\X =

+ Fhx\X).

(Y)+

Fh = X(Y)+

Fh\X

Vậy: (XY)+ a) đƣợc chứng minh.

Từ các kết quả trên, ta có hệ quả sau:

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Hệ quả2.3[4] (Biểu diễn bao đóng thông qua phép dịch chuyển)

, X = Cho lƣợc đồ khối =(R, Fh), R = (id; A1, A2,…, An), X

{x(i), x id, i A}, A {1, 2, ..., n}. Khi đó:

Fh = X(

Fh\X.

a) (X)+ )+

Fh = X(

Fhx\X).

b) (X)+ ( )+

Chứng minh

Sử dụng kết quả a) và b) ở trên với trƣờng hợp đặc biệt Y = ta có

ngay điều phải chứng minh.

2.2.5. Biểu diễn khóa qua phép dịch chuyển

Cho lƣợc đồ khối = (R, Fh), R = (id; A1, A2,…, An) và X, U0, UK, UI,

là các tập thuộc tính chỉ số ; đối với lƣợc đồkhối , ta ký hiệu:

- U0 là tập hợp các thuộc tính không khóa.

- UK là tập hợp các thuộc tính khóa

- UI là tập hợp các thuộc tính nằm trong mọi khóa.

Cho các lƣợc đồ khối = (S,G), = (R, Fh), R = (id; A1, A2,…, An),

x = (Rx, Fhx) là lƣợc đồ lát cắt của

= \X. Khi đó, ta ký hiệu:

= (R, Fh) tại điểm x,

x = (Sx, Gx) là lƣợc đồ lát cắt của

= (S, G) tại điểm x,

Mệnh đề 2.2[4]

Cho lƣợc đồ khối = (R, Fh), R = (id; A1, A2,…, An) và X, Y, Q

, X = {x(i), x id, i A}, Y = {x(i), x id, i B}, Q = {x(i), x id, i

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

C}; A, B, C {1, 2, .., n}, = (S, G), = \X. Khi đó:

a) Nếu Y là siêu khóa của thì Y\X là siêu khóa của .

x =(Sx,Gx),

b) Nếu Y là siêu khóa của thì Yx\ Xx là siêu khóa của

B}. x id, ở đây Xx = {x(i), i A}, Yx = {x(i), i

x, x id, ở đây

c) Nếu Q là siêu khóa của thì XxQx là siêu khóa của

C}. Trƣờng hợp X chỉ gồm các thuộc tính không khóa của và Qx = {x(i), i

Q là siêu khóa của thì Qx chính là siêu khóa của x, x id.

Chứng minh

a) Giả sử Y là siêu khóa của , đặt P = Y\X P Q = và Y XP.

Theo giả thiết Y là siêu khóa của , do đó:

Fh = X(P)+

Fh\X.

X( \X)= =Y+ (XP)+

Fh\X =

Mà: X ( \X) = , X P+ P+ \X(1)

Từ (1), ta thấy P = Y\X chính là siêu khóa của = \X.

b) Giả sử Y là siêu khóa của , theo kết quả của a) ta có Y\X là siêu

khóa của = id. \X. Từ đó, ta có: Yx\Xx là siêu khóa của x = (Sx, Gx), x

Fh\X=

c) Giả sử Q là siêu khóa của thì: Q X= , Q+ \X

Fh = X(Q)+

Fh\X =X(

Suy ra: (XQ)+ \X) =

Vậy, XQ là siêu khóa của .

Nếu X chỉ gồm các thuộc tính không khóa của thì việc loại bỏ từ siêu

khóa XQ các thuộc tính không khóa X vẫn cho ta siêu khóa Q của .

d) Giả sử Q là siêu khóa của , thì theo c) ta có XQ là siêu khóa của .

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Từ đó, ta có XxQx là siêu khóa của x, x id.

Trƣờng hợp X chỉ gồm các thuộc tính không khóa của , thì suy ra Xx là

x, do đó Qx = XxQx\Xx chính là siêu khóa

tập các thuộc tính không khóa của

của x, x id.

Mệnh đề 2.3[4]

Cho lƣợc đồ khối , = (R, Fh), R = (id; A1, A2,…, An) và X, Q

X = {x(i), x id, i A}, Q = {x(i), x id, i C}; A, C {1, 2, .., n}, = (S,

G), = \X+. Khi đó, nếu Q là siêu khóa của thì:

a) XQ là siêu khóa của .

b) XxQx là siêu khóa của x, x id.

Chứng minh

a) Giả sử Q là siêu khóa của , theo mệnh đề 2.2, ta có X+Q là siêu

khóa của , khi đó (X+Q)+ = .

Mà ta có: (XQ)+ = (X+Q)+ = XQ là siêu khá của .

b) Giả sử Q là siêu khóa của thì theo a) ta có XQ là siêu khóa của .

Từ đó, ta có: XxQx là siêu khóa của x, x id.

Mệnh đề 2.4[4]

Cho lƣợc đồ khối , = (R, Fh), R = (id; A1, A2,…, An) và X, K

X = {x(i), x id, i A}, K={x(i), x id, i B}; A, B {1, 2, .., n}, = (S, G),

= \X.

Khi đó,

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

a) Nếu K là khóa của thì K\X là khóa của .

b) Nếu K là khóa của id. Ở thì Kx\Xx là khóa của x = (Sx, Gx), x

A}. đây, Kx = {x(i), i B}, Xx = {x(i), i

Chứng minh

a) Giả sử, K là khóa của K là siêu khóa của , theo mệnh đề 2.2, ta

có K\X là siêu khóa của . Nếu K\X không phải là khóa của thì M K\X

là siêu khóa của , theo mệnh đề 5.2 ta lại có XM là siêu khóa của .

Mà XM X(K\X)=K, điều này mâu thuẫn với giả thiết K là khóa của

. Do đó, K\X là khóa của .

b) Giả sử K là khóa của , khi đó, theo a) ta có K\X là khóa của . Vậy

ta có Kx\Xx là khóa của x, x id.

Mệnh đề 2.5[4]

Cho lƣợc đồ khối , = (R, Fh), R = (id; A1, A2,…, An) và X, K

X = {x(i), x id, i A}, K = {x(i), x id, i B}; A, B {1, 2, .., n}, X U0,

= (S, G), = \X. Khi đó,

thì K là khóa của

B}, x id thì K là a) Nếu K là khóa của b) Nếu Kx là khóa của x = (Sx, Gx), Kx = {x(i), i

khóa của .

Chứng minh

a) Giả sử K là khóa của K là siêu khóa của theo mệnh đề 2.2,

ta có K là siêu khóa của (vì giả thiết X U0). Ta chứng minh K là khóa của

Giả sử K không là khóa của , khi đó K’ K mà K’ là siêu khóa của

, . Theo mệnh đề 2.2, ta có K’ =K’\X (vì giả thiết X U0) là siêu khóa của

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

điều này mâu thuẫn với giả thiết K là siêu khóa của . Vậy K là khóa của .

B}, x id, khi đó, b) Giả sử Kx là khóa của x= (Sx, Gx), Kx = {x(i), i

ta có K là khóa của , từ đó, dựa vào kết quả của a) ta có K là khóa của .

Mệnh đề 2.6 (điều kiện cần và đủ)[4]

Cho lƣợc đồ khối , = (R, Fh), R = (id; A1, A2,…, An) và X, K

X = {x(i), x id, i A}, K = {x(i), x id, i B}; A, B {1, 2, .., n}, X U0,

= (S, G), = \X. Khi đó,

a) K là khóa của khi và chỉ khi thì K là khóa của

x = (Sx, Gx), Kx =

b) K là khóa của khi và chỉ khi Kx là khóa của

{x(i), i B}, x id.

Chứng minh

a) K là khóa của K là khóa của

Thật vậy, từ giả thiết K là khóa của , X U0 và mệnh đề 2.4 ta suy ra

K =K\X là khóa của

K là khóa của K là khóa của

Giả sử K là khóa của theo mệnh đề 2.5 ta suy ra K là , vì X U0

khóa của

b) Giả sử K là khóa của theo kết quả của câu a) ta suy ra K là khóa

của B}, x id. ta có Kx là khóa của x = (Sx, Gx), Kx = {x(i), i

B}, x id. Ngƣợc lại, nếu Kx là khóa của x = (Sx, Gx), Kx = {x(i), i

ta có K là khóa của

Từ đó, áp dụng kết quả của câu a) K là khóa của .

2.2.6. Ví dụ

Cho lƣợc đồ khối = (R, F), với R = (id; A1A2A3A4A5A6); id = {1, 2}

F={ {1(1), 2(1), 1(5), 2(5) } {1(4) , 2(4)},

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

{1(2), 2(2), 1(3), 2(3) } {1(5) , 2(5)},

{1(5) , 2(5)} {1(2), 2(2), 1(3), 2(3) } }

Fh, (X2)+

X1 = {1(1), 2(1), 1(5), 2(5), 1(6), 2(6)}; X2 = {1(6), 2(6)} Tính (X1)+

Bài giải

Fh = X1(

Fh\X1

)+ Theo hệ quả 2.3 về công thức tính bao đóng cho mọi tập thuộc tính (X1)+

Ta tính 1 = (S1, G1) =

\X1 {1(4) , 2(4)}, {1(2), 2(2), 1(3), 2(3) } (loại), G1 = F\X1={

{ {1(2), 2(2), 1(3), 2(3) } }

{ {1(2), 2(2), 1(3), 2(3), 1(4) , 2(4) }

Fh/X1= {1(2), 2(2), 1(3), 2(3), 1(4) , 2(4) }

Từ đây ta tính đƣợc ( )+

Fh = X1(

Fh\X1 = {1(1), 2(1), 1(5), 2(5), 1(6), 2(6), 1(2), 2(2), 1(3), 2(3),

)+ (X1)+

Fh = X2(

Fh\X2

)+ 1(4), 2(4) } = R (X2)+

\X2

{1(4) , 2(4)}, {1(2), 2(2), 1(3), 2(3) } (loại), Ta tính 2 = (S2, G2) = G2={ {1(1), 2(1)}

{1(2), 2(2), 1(3), 2(3) } }

= { {1(1), 2(1)} {1(4) , 2(4)}, {1(2), 2(2), 1(3), 2(3) }}

Fh = X2(

Fh/X2= {1(2), 2(2), 1(3), 2(3)} Fh\X2 = {1(2), 2(2), 1(3), 2(3), 1(6), 2(6)}

Từ đây ta tính đƣợc ( )+ (X2)+

Kết luận chƣơng 2

Trong chƣơng này, luận văn đã trình bày một số vấn đề về phép dịch

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

chuyển trong LĐQH và lƣợc đồ khối và giới thiệu cácthuật toán dịch chuyển

lƣợc đồ khối trong mô hình dữ liệu dạng khối. Đƣa ra phƣơng pháp biểu diễn

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

bao đóng và khóa của lƣợc đồ khối thông qua phép dịch chuyển.

CHƢƠNG 3. CHƢƠNG TRÌNH THỬ NGHIỆM

Luận văn tập trung nghiên cứu tìm hiểu mô hình cơ sở dữ liệu dạng

khối và phép dịch chuyển lƣợc đồ khối. Việc cài đặt chƣơng trình thử nghiệm

nhằm mục đích mô phỏng các kết quả nghiên cứu đƣợc của học viên. Chƣơng

trình có giao diện đơn giản, dễ sử dụng, dễ hiểu và đƣợc viết bởi ngôn ngữ lập

trình C#, một ngôn ngữ có hƣớng đối tƣợng, khá phổ biến... và cho phép tạo

giao diện nhanh, dễ dàng.

3.1. Bài toán thử nghiệm

Trên thực tế, có rất nhiều bài toán phân tích thiết kế, xây dựng chƣơng

trình cần phải chuẩn hóa cơ sở dữ liệu. Vì dữ liệu dùng để xây dựng chƣơng

trình nếu không đƣợc chuẩn hóa sẽ dẫn đến dƣ thừa, gây khó khăn cho việc

quản lý, sử dụng, xử lý dữ liệu của ứng dụng. Trong quá trình đó, ngƣời thiết

kế thƣờng gặp một số vấn đề sau:

Khi xác định một số đặc điểm của đối tƣợng đƣợc lƣu trữ, ngƣời thiết kế

sẽ liệt kê tất cả các thuộc tính cần quản lý của đối tƣợng mà không quan tâm

đến vấn đề liệu khi thêm thuộc tính đó thì có bị trùng lặp thông tin không, dữ

liệu có nhất quán không. Chẳng hạn, trong hệ thống bán hàng, chúng ta lƣu trữ

thông tin của nhà cung cấp để đặt hàng thì một số thông tin ta cần là: mã nhà

cung cấp, tên nhà cung cấp, địa chỉ, số điện thoại, mã hàng, tên hàng... Với đối

tƣợng nhà cung cấp nếu ta quản lý rằng mỗi nhà cung cấp chỉ cung cấp một

mặt hàng thì ta biết đƣợc nhà cung cấp nào cung cấp mặt hàng tên gì nhƣng dữ

liệu về tên mặt hàng không nhất quán. Khi nhập liệu ta có thể nhập nhƣ sau:

Mã nhà cung cấp … Mã hàng Tên hàng

01 01 Abc

02 02 Abc

Bảng 1. Quan hệ nhà cung cấp

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Điều đó sẽ gây khó khăn cho ta trong quá trình truy xuất thông tin.

Để khắc phục đƣợc vấn đề trên, đầu tiên ngƣời thiết kế phải dựa vào

các qui tắc quản lý (phụ thuộc hàm), áp dụng hệ luật dẫn Amstrong trên các

phụ thuộc hàm để xác định mối liên hệ giữa các thuộc tính trong một đối

tƣợng hoặc giữa các đối tƣợng trong một CSDL. Sau đó, sử dụng thuật toán

tìm khóa của đối tƣợng. Dựa vào khóa và các phụ thuộc hàm, ngƣời thiết kế

sẽ đi xác định dạng chuẩn để đánh giá tính chất của LĐQH hay là đối tƣợng

cần quản lý. Trong thực tế, ngƣời ta chỉ đánh giá cao các LĐQH đạt từ dạng

chuẩn 3 trở lên vì ở dạng chuẩn này CSDL sẽ tránh trùng lắp thông tin. Do

đó, khi LĐQH không đạt đƣợc dạng chuẩn 3, ngƣời thiết kế phân rã LĐQH

đó thành những lƣợc đồ con đảm bảo dạng chuẩn cao hơn, dữ liệu không bị

trùng lắp mà vẫn giữ đƣợc tính bảo toàn, tính chính xác của dữ liệu, không

gây mất thông tin.

Trong mô hình cơ sở dữ liệu dạng khối, khi thiết kế các CSDL, ngƣời

ta cũng gặp phải vấn đề tƣơng tự nhƣng độ phức tạp lớn hơn nhiều, đặc biệt là

đối với những CSDL lớn.

Trong chƣơng 3,tác giả xây dựng một chƣơng trìnhsử dụng các thuật

toán dịch chuyển nhằm thu gọnlƣợc đồ và phƣơng pháp biểu diễn khóa của

lƣợc đồ khối thông qua phép dịch chuyển nhằm mô phỏng các kết quả nghiên

cứu của luận văn.

3.2. Phân tích và thiết kế chƣơng trình thử nghiệm

3.2.1. Thủ tục dịch chuyển

Trong chƣơng 2 của luận văn, tác giả đã giới thiệu 2 thuật toán dịch

chuyển lƣợc đồ khối. Cả 2 thủ tục này đều có thông tin vào là lƣợc đồ khối

= (R, Fh) và tập thuộc tính chỉ số X, thông tin ra là lƣợc đồ dịch chuyển theo

tập thuộc tính chỉ số X của : = \ X = (V,G) với V = R\X, G = F\X.

Xác định V: Ở cả 2 thủ tục dịch chuyển, việc xác định tập V:=R\X đều

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

giống nhau, nghĩa là V thu đƣợc từ việc loại bỏ khỏi R các thuộc tính trong X

Việc xác định tập FTH G: Đối với thủ tục dịch chuyển sử dụng thuật

toán 2.1, ta sẽ tiến hành thực hiện trực tiếp trên các FTH của khối ban đầu.

Còn thủ tục dịch chuyển sử dụng thuật toán 2.2, ta sẽ tiến hành thực hiện trên

các lát cắt.

Việc thực hiện thao tác G:= Rutgon(G) ta thực hiện 2 việc:

+ Loại bỏ các PTH tầm thƣờng (dạng X Y, X Y)

+ Loại bỏ bớt các PTH trùng nhau.

3.2.2. Biểu diễn khóa qua phép dịch chuyển

Theo mệnh đề 2.26, việc xác định khóa của lƣợc đồ khối α có thể đƣợc

thực hiện thông qua việc tìm khóa của lƣợc đồ β = α\X với X U0; Việc xác

định khóa của lƣợc đồ khối β có thể đƣợc thực hiện thông qua việc tìm khóa

id, mỗi lát cắt lại có thể coi là một LĐQH. Vậy, việc tìm Kxcủa lát cắt βx, x

khóa của lƣợc đồ khối lại trở thành việc tìm khóa của LĐQH.

3.2.3. Thiết kế chương trình

Chƣơng trình cần có một số chức năng chính sau:

+ Nhập dữ liệu: cho phép ngƣời sử dụng nhập các lƣợc đồ khối, các

phụ thuộc hàm và các thuộc tính chỉ số. Việc nhập dữ liệu có thể đƣợc thực

hiện thông qua tệp hoặc nhập trực tiếp.

+ Thực hiện thủ tục dịch chuyển lƣợc đồ khối: Cho phép ngƣời sử dụng

lựa chọn áp dụng một trong 2 thuật toán dịch chuyển lƣợc đồ khối đầu vào,

hiển thị kết quả ra màn hình.

+ Biểu diễn khóa qua phép dịch chuyển

3.3. Cài đặt và thực hiện chƣơng trình thử nghiệm

3.3.1. Yêu cầu hệ thống

Chƣơng trình thử nghiệm đƣợc viết bằng ngôn ngữ lập trình Visual C#

trên nền tảng .Net của bộ công cụ lập trình Visual Studio 2013. Để có thể sử

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

dụng chƣơng trình, trên máy tính cần cài đặt Dotnet Framework 4.5

3.3.2. Hệ thống dữ liệu vào/ra

Với mục tiêu của bài toán là thực hiện phép dịch chuyển lƣợc đồ khối

theo tập thuộc tính chỉ số, dữ liệu đầu vào của hệ thống bao gồm:

+ Lƣợc đồ khối = (R,F), với:

R = (id; A1, A2,…, An);

F: tập phụ thuộc hàm có dạng L R, trong đó:

L, R , id(i) = (x(i)| x id); x(i) = (x; Ai);

+ Tập thuộc tính chỉ số X , X = {x(i), x id, i A}, A {1, 2,

..., n}.

Thông tin thu đƣợc từ bài toán là:

+ Lƣợc đồ khối = \ X = (V,G), V = R\X, G = F\X.

+ Biểu diễn khóa của lƣợc đồ khối .

3.3.3. Hệ thống giao diện

Giao diện chính:

Hình 3.1 Giao diện chính của chương trình

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Giao diện nhập khối ban đầu, các phụ thuộc hàm, tập thuộc tính:

Hình 3.2 Giao diện nhập dữ liệu

3.3.4. Kết quả thử nghiệm chương trình và đánh giá

Ví dụ 3.1

Cho lƣợc đồ khối = (R,F), với

R = (id; A1A2A3A4A5A6); id = {1} F={ {1(1), 1(5) } {1(4)}, {1(1)} {1(4), 1(6)},

{1(2), 1(3) } {1(5)}, {1(5)} {1(2), 1(3)} }

X = {1(1), 1(4), 1(6)}

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Xác định = \ X = (V,G), V = R\X, G = F\X

V=R\X = {1(2), 1(3), 1(5)}

G = { {1(5) } (loại), (loại),

{1(2), 1(3)} {1(5)}, {1(5)} {1(2), 1(3)} }

= { {1(2), 1(3)} {1(5)}, {1(5)} {1(2), 1(3)} }

Lƣợc đồ khối = \ X thu đƣợc có dạng:

= (V,G) với

V = (id; A2A3A5); id = {1} G = { {1(2), 1(3)} {1(5)}, {1(5)} {1(2), 1(3)} }

Kết quả thực hiện trong chƣơng trình:

Trong ví dụ này, id ={1}, lƣợc đồ khối suy biến thành LĐQH, phép

dịch chuyển lƣợc đồ khối trở thành phép dịch chuyển trong mô hình quan hệ.

Ví dụ3.2

Cho lƣợc đồ khối = (R,F), với

R = (id; ABCDEHKI); id ={1}

F = { {(1; A), (1; B)} {(1; C)},

{(1; C)} {(1; D), (1; E) (1; H)},

{(1; H)} {(1;K)}}

X = {(1; B), (1; I)}

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Hãy xác định = \ X

Kết quả thực hiện trên phần mềm:

Ta dịch chuyển α theo X, ta đƣợc sơ đồ β =

V = ({1}; ACDEHK)

G = { {(1; A)} {(1; C)},

{(1; C)} {(1; D), (1; E) (1; H)},

{(1; H)} {(1; K)} }

Ví dụ 3.3

Cho lƣợc đồ khối = (R,F), với

R = (id; A1A2A3A4A5A6); id = {1, 2} F={ {1(1), 2(1), 1(5), 2(5)} {1(4), 2(4)}, {1(1), 2(1)} {1(3), 2(3)},

{1(5), 2(5)} {1(2), 2(2), 1(3), 2(3)}, {1(5), 2(5), 1(6), 2(6)} {1(1), 2(1)},

{1(1), 2(1), 1(3), 2(3)} {1(5), 2(5), 1(6), 2(6)},{1(2), 2(2), 1(4),2(4)} {1(3), 2(3)}

X = {1(2), 2(2), 1(3), 2(3), 1(5), 2(5)}

+ Xác định = \ X = (V,G), V = R\X, G = F\X

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

+ Tìm một khóa của lƣợc đồ khối

Kết quả thực hiện trên phần mềm:

Áp dụng thuật toán 2.4 V=R\X = {1(1), 1(4), 1(6), 2(1), 2(4), 2(6)}

G = F\X ={ {1(1),2(1)} {1(4), 2(4)}, {1(1), 2(1)} (loại),

(loại), {1(6), 2(6)} {1(1), 2(1)},

{1(1),2(1)} {1(6),2(6)}, {1(4), 2(4)} (loại) }

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Thu gọn G, ta đƣợc:

G ={ {1(1), 2(1)} {1(4), 2(4), 1(6), 2(6)}, {1(6), 2(6)} {1(1), 2(1)} }

Vậy = \ X thu đƣợc có dạng:

= (V,G) với

V = (id; A1A4A6); id = {1,2} G ={ {1(1), 2(1)} {1(4), 2(4), 1(6), 2(6)}, {1(6), 2(6)} {1(1), 2(1)} }

Áp dụng thuật toán 2.5

id = {1, 2} nên R có 2 lát cắt

{1(4)}, {1(1)} {1(3)},

R1 = ({1}; A1A2A3A4A5A6); với tập FTH Fh1={ {1(1), 1(5) } {1(5)} {1(2), 1(3)} , {1(5), 1(6) } {1(1)},

{1(1), 1(3) } {1(5), 1(6) }, {1(2), 1(4) } {1(3)}}

{2(4)}, {2(1)} {2(3)},

R2 = ({2}; A1A2A3A4A5A6); với tập FTH Fh1={ {2(1), 2(5) } {2(5)} {2(2), 2(3)} , {2(5), 2(6) } {2(1)}, {2(1), 2(3) }

{2(5), 2(6) }, {2(2), 2(4) } {2(3)} }

1 = (R1,Fh1) trên tập thuộc tính X1 = {1(2), 1(3), 1(5)}, 2 = (R2,Fh2) trên tập thuộc tính X2 = { 2(2), 2(3), 2(5)}

Ta cần thực hiện phép dịch chuyển trên 2 lát cắt với các lƣợc đồ tƣơng ứng

Ta có:

1 = 1\ X1 = (V1,G1) V1=R1\X1 = {1(1), 1(4), 1(6)} G1 = Fh1\X1 = { {1(1)} {1(6)}

{1(4)}, {1(1)} (loại), (loại),

{1(1)}, {1(1)} {1(6) }, {1(4)} (loại) }

Thu gọn G1, ta đƣợc

{1(1)} {1(4),1(6) }, {1(6)} {1(1)} } G1 = {

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Tƣơng tự, ta có

2 = 2\ X2 = (V2,G2) V2=R2\X2 = {2(1), 2(4), 2(6)}

{2(1)} {2(4),2(6) }, {2(6)} {2(1)} } G2 = {

Vậy = \ X thu đƣợc có dạng:

= (V,G) với

V = (id; A1A4A6); id = {1,2} {1(1)} G = { {1(4),1(6) }, {1(6)} {1(1)},

{2(1)} {2(4),2(6) }, {2(6)} {2(1)} }

={ {1(1), 2(1)} {1(4), 2(4), 1(6), 2(6)}, {1(6), 2(6)} {1(1), 2(1)} }

Nhƣ vậy, qua một số ví dụ, các kết quả thử nghiệm trên phần mềm hoàn toàn trùng khớp với việc thực hiện thuật toán trên giấy. Việc áp dụng 2 thuật toán dịch chuyển lƣợc đồ khối có kết quả tƣơng tự nhau.

Kết luận chƣơng 3

Trong chƣơng này,tác giả đã tiến hành xây dựng một chƣơng trình trên

ngôn ngữ lập trình C# trên nền tảng Visual Studio 2013,sử dụng các thuật

toán dịch chuyển nhằm thu gọnlƣợc đồ và áp dụng phƣơng pháp biểu diễn

khóa của lƣợc đồ khối trong ứng dụng trên.

Tác giả cũng đã đƣa ra một số ví dụ đơn giản để thử nghiệm kết quả

thực hiện chƣơng trình với việc thực hiện thuật toán trên giấy với kết quả

trùng khớp. Tuy nhiên, đây mới chỉ là ứng dụng hết sức đơn giản, chỉ dừng lại

ở mức độ mô phỏng kết quả nghiên cứu của tác giả. Việc xây dựng chƣơng

trình có tính ứng dụng trong thực tế cần phải đầu tƣ nhiều hơn nữa thời gian

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

và công sức.

KẾT LUẬN

Qua tìm hiểu và nghiên cứu về phép dịch chuyển lƣợc đồ khối trong

mô hình dữ liệu dạng khối, luận văn đã thực hiện đƣợc một số kết quả chính

sau đây:

- Tìm hiểu về 1 mô hình dữ liệu mới, đó là mô hình dữ liệu dạng khối.

Mô hình này là một mở rộng của mô hình dữ liệu quan hệ do E.Codd đề xuất

năm 1970.

- Trình bày một số kết quả nghiên cứu về bao đóng, khóa và phụ thuộc

hàm trong mô hình này đồng thời cũng giới thiệu các tính chất về khóa, thuật

toán tìm khóa, các dạng chuẩn và tựa chuẩn... Mối liên quan giữa mô hình dữ

liệu dạng khối với mô hình quan hệ.

- Tìm hiểu và giới thiệu phép dịch chuyển lƣợc đồ khối trên mô hình dữ

liệu dạng khối và một số thuật toán liên quan; ứng dụng các thuật toán trên

vào việc xây dựng chƣơng trình demo cho phép thực hiện một số thao tác trên

mô hình dữ liệu dạng khối.

Trên đây là một số kết quả mà luận văn đã tìm đƣợc đối với phép dịch

chuyển lƣợc đồ khối trong mô hình dữ liệu dạng khối. Tuy nhiên, đó chỉ là

những kết quả bƣớc đầu, việc nghiên cứu tiếp về mô hình dữ liệu này vẫn còn

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

là những vấn đề mở cần đƣợc nghiên cứu tiếp.

TÀI LIỆU THAM KHẢO

A. Tiếng Việt

[1] Nguyễn Kim Anh (2002), “Đại số khối trên các cơ sở dữ liệu đa

chiều”, Tạp chí Tin học và Điều khiển học, 18(2), tr. 149-154.

[2] Nguyễn Xuân Huy (2006), Các phụ thuộc logic trong cơ sở dữ liệu,

Nhà xuất bản Thống kê, Hà Nội.

[3] Lê Văn Phùng (2010), Cơ sở dữ liệu quan hệ và Công nghệ phân

tích-Thiết kế, Nhà xuất bản Thông tin và Truyền thông, Hà Nội.

[4] Trịnh Đình Thắng (2011), Mô hình dữ liệu dạng khối, Nhà xuất bản

Lao Động, Hà Nội.

[5]Vũ Đức Thi (1997), Cơ sở dữ liệu: Kiến thức và thực hành, NXB

Thống Kê, Hà Nội.

[6] Vũ Đức Thi (2010), Giáo trình Cơ sở dữ liệu nâng cao, Nhà xuất

bản Đại học Thái Nguyên, Thái Nguyên.

[7] Trịnh Đình Vinh (2011), Một số phụ thuộc dữ liệu trong cơ sở dữ

liệu dạng khối, Luận án tiến sĩ toán học, Hà Nội.

B. Tiếng Anh

[8] C. Stolte, D. Tang, and P. Hanrahan. Polaris (2002): “A System for

Query, Analysis, and Visualization of Multi-dimensional Relational

Databases”. In IEEE Trans. On Visualization and Computer Graphics, 8(1),

pp. 52-65.

[9] Demetrovics J, Ho Thuan, Nguyen Xuan Huy, Le Van Bao (1986),

Translations of relation schemes, balanced relation scheme and the problem

of key representation, EIK, Berlin.

[10] E. Rundensteiner, M. Ward, J. Yang, and P. Doshi. XmdvTool

(2002): “VisualInteractive Data Exploration and Trend Discovery of High-

dimensional Data Sets”. In Proc. ACM SIGMOD 2002.

[11] Harinarayan V., Rajaraman A., and Ullman J. D. (1996),

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

“Implementing data cubes efficiently”, SIGMOD.

Luận văn Thạc sĩ Khoa học máy tính: Phép dịch chuyển lược đồ khối trong mô hình dữ liệu dạng khối

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

NGÔ VĂN ĐỊNH

PHÉP DỊCH CHUYỂN LƢỢC ĐỒ KHỐI TRONG MÔ HÌNH DỮ LIỆU DẠNG KHỐI

ĐẠI HỌC THÁI NGUYÊN

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

NGÔ VĂN ĐỊNH

PHÉP DỊCH CHUYỂN LƢỢC ĐỒ KHỐI TRONG MÔ HÌNH DỮ LIỆU DẠNG KHỐI

LỜI CẢM ƠN

LỜI CAM ĐOAN

Ngô Văn Định

Định nghĩa 2.1 [2]

Hình 3.1 Giao diện chính của chương trình

Hình 3.2 Giao diện nhập dữ liệu

Có thể bạn quan tâm

Luận văn Thạc sĩ: Quản lý hoạt động phát triển nhận thức cho trẻ mẫu giáo ở các trường mầm non, huyện Hoàng Su Phì, tỉnh Hà Giang

Luận văn Thạc sĩ tóm tắt: Pháp luật về điều kiện đầu tư kinh doanh trong lĩnh vực giáo dục, đào tạo ở Việt Nam

Luận văn Thạc sĩ: Sự nghiệp nghiên cứu phê bình văn học của Hoài Thanh

Luận văn Thạc sĩ: Tiểu thuyết của Đỗ Phấn từ góc nhìn sinh thái

Luận văn Thạc sĩ: Giải pháp ứng phó với nhập cư ở Liên minh Châu Âu

Luận văn Thạc sĩ: Diễn ngôn về giới nữ trong văn xuôi nữ Việt Nam đương đại (khảo sát sáng tác của Dạ Ngân, Y Ban, Lý Lan, Nguyễn Thị Thu Huệ)

Luận văn Thạc sĩ: Xây dựng mức phát thải tham chiếu rừng khu vực huyện Bảo Lâm tỉnh Lâm Đồng

Luận văn Thạc sĩ: Đặc điểm nhân vật chính trong ba tác phẩm của Franz Kafka: Lâu đài, Vụ án, Hóa thân

Kháo luận tốt nghiệp: Vận dụng lí thuyết học tập trải nghiệm vào dạy học Thống kê - Xác suất ở lớp Hai

Luận văn Thạc sĩ: Xây dựng hệ thống điều khiển và thu nhận dữ liệu cho Robot dịch vụ

Luận văn Thạc sĩ: Thế giới nhân vật trong truyện ngắn Lê Minh Khuê sau năm 1975

Luận văn Thạc sĩ: Tác động của cấu trúc vốn đến hiệu quả hoạt động của các ngân hàng thương mại cổ phần niêm yết trên thị trường chứng khoán Việt Nam

Luận văn Thạc sĩ: Kiểm soát rủi ro tín dụng bán lẻ tại Ngân hàng Thương mại Cổ phần Đầu tư và Phát triển Việt Nam chi nhánh Thủ Thiêm

Luận văn Thạc sĩ: Các yếu tố ảnh hưởng đến hiệu quả kinh doanh của ngân hàng thương mại cổ phần niêm yết trên thị trường chứng khoán Việt Nam

Luận văn Thạc sĩ: Các nhân tố ảnh hưởng đến hành vi sử dụng dịch vụ ngân hàng điện tử tại Ngân hàng Thương mại Cổ phần Ngoại thương Việt Nam – Chi nhánh Thủ Đức

Luận văn Thạc sĩ: Các yếu tố tác đồng đến nợ xấu tại Ngân hàng Nông nghiệp và Phát triển Nông thôn - Chi nhánh Tiền Giang

Luận văn Thạc sĩ: Yếu tố ảnh hưởng đến quyết định sử dụng dịch vụ thanh toán không dùng tiền mặt tại Ngân hàng TMCP Công thương Việt Nam (Vietinbank)

Luận văn Thạc sĩ tóm tắt: Pháp luật về du lịch biển, thực tiễn tại tỉnh Bình Định

Luận văn Thạc sĩ: Ảnh hưởng của các yếu tố thương hiệu với vai trò trung gian của Marketing truyền miệng đến quyết định chọn việc làm của nhân viên GenZ tại chuỗi nhà hàng gà rán Popeyes khu vực Thành Phố Hồ Chí Minh

Luận văn Thạc sĩ: Ảnh hưởng của Marketing mix đến ý định học cao học của sinh viên khối ngành kinh tế thuộc Trường Đại học Công nghệ Thành phố Hồ Chí Minh

Tài liêu mới

Luận án Tiến sĩ: Nghiên cứu xây dựng thuật toán thích nghi và học tăng cường cấu trúc Actor - Critic điều khiển bám quỹ đạo cho robot di động đa hướng mecanum

Luận án Tiến sĩ: Cơ cấu bệnh tim mạch và chất lượng cuộc sống của người cao tuổi mắc suy tim, rung nhĩ điều trị tại Bệnh viện Thống Nhất, thành phố Hồ Chí Minh

Tóm tắt Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

Tóm tắt Luận án Tiến sĩ: Nghiên cứu xây dựng giải pháp đảm bảo an toàn thông tin cho quá trình học liên kết dựa trên mật mã

Tóm tắt Luận án Tiến sĩ: Phát triển năng lực đánh giá công nghệ cho học sinh trong dạy học môn Công nghệ 11 ở trường trung học phổ thông

Tóm tắt Luận án Tiến sĩ: Nghiên cứu phân loại chi cầu diệp – Bulbophyllum Thouars (Orchidaceae) ở vùng Tây Nguyên bằng phương pháp hình thái và phân tử

Tóm tắt Luận án Tiến sĩ: Nghiên cứu đặc điểm phân bố và dinh dưỡng của các loài lưỡng cư ở Vườn Quốc gia Bến En và Khu bảo tồn thiên nhiên Pù Luông, tỉnh Thanh Hóa

Luận án Tiến sĩ: Tổng hợp luật dẫn và điều khiển cho một lớp tên lửa đối hải trên cơ sở ứng dụng mạng nơ ron và hệ mờ

Luận án Tiến sĩ: Nghiên cứu tổng hợp hệ điều khiển góc Pitch tua bin gió trong điều kiện có nhiễu tác động

Luận án Tiến sĩ: Nghiên cứu hóa học lipid của hai loài san hô thủy tức Millepora dichotoma và Millepora platyphylla ở Việt Nam

Luận án Tiến sĩ: Nghiên cứu kiểm soát phân phối công suất kéo trên cầu chủ động của ô tô con bằng ABS

Luận án Tiến sĩ: Ứng dụng phản ứng Domino vào tổng hợp các dẫn xuất Podophyllotoxin, Pyrimidine và đánh giá hoạt tính sinh học của các chất tổng hợp được

Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và một số hoạt tính sinh học của cây chùm ngây (Moringa oleifera)

Tóm tắt Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và ứng dụng ức chế ăn mòn cho thép của cao chiết xuất từ cây Lộc vừng thuộc họ Lecythidaceae

Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA

Hỗ trợ

Hướng dẫn sử dụng

Đăng ký tài khoản VIP

093 303 0098

support@tailieu.vn

Phương thức thanh toán

Theo dõi chúng tôi

Facebook

Youtube

TikTok