ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

CAO THỊ NHÂM

LOẠI BỎ MẨU TIN NHÂN BẢN THỪA
TRONG CƠ SỞ DỮ LIỆU QUAN HỆ

LUẬN VĂN THẠC SĨ

Hà Nội - 2009


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

Cao Thị Nhâm

LOẠI BỎ MẨU TIN NHÂN BẢN THỪA
TRONG CƠ SỞ DỮ LIỆU QUAN HỆ

Ngành: Công nghệ thông tin
Chuyên ngành: Công nghệ phần mềm
Mã số: 60 48 10

LUẬN VĂN THẠC SĨ

NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Lê Huy Thập

Hà Nội - 2009


1.2.1

Khái quát về cơ sở dữ liệu phân tán ........................................................23

1.2.2

Các kiểu phân mảnh cơ sở dữ liệu ..........................................................25

1.3

LÝ THUYẾT CHẮC CHẮN.........................................................................29

1.3.1

Hệ số chắc chắn dành cho dữ kiện ..........................................................29

1.3.2

Hệ số chắc chắc chắn dành cho luật........................................................30

1.3.3

Các quy tắc tính toán trên CF..................................................................30

1.4

TỔNG KẾT CHƯƠNG 1 ...............................................................................32

Chương 2
THUẬT TOÁN LOẠI BỎ MẨU TIN NHÂN BẢN THỪA TRONG

TỔNG KẾT CHƯƠNG 2 ...............................................................................39

Chương 3

ỨNG DỤNG THUẬT TOÁN .................................................................40

3.1 HỆ THỐNG LOẠI BỎ MẨU TIN NHÂN BẢN THỪA TRONG CSDL
QUAN HỆ .................................................................................................................40
3.1.1

Mô tả bài toán..........................................................................................40

3.1.2

Yêu cầu đặt ra đối với hệ thống ..............................................................40

3.1.3

Khả năng giải quyết bài toán...................................................................41

3.1.4

Sơ đồ hệ thống.........................................................................................42

3.2 THIẾT KẾ HỆ THỐNG LOẠI BỎ MẨU TIN NHÂN BẢN THỪA TRONG
CSDL QUAN HỆ ......................................................................................................49
3.2.1

Xây dựng các lớp đối tượng ....................................................................49


Hướng phát triển......................................................................................69

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


5

DANH MỤC HÌNH VẼ
Hình 1-1 Kiến trúc cơ sở dữ liệu phân tán .................................................................23
Hình 1-2 Phân mảnh hỗn hợp của quan hệ EMP ........................................................27
Hình 3-1 Các tầng xử lý của hệ thống........................................................................42
Hình 3-2 Luồng xử lý của hệ thống EDRS ................................................................44
Hình 3-3 Sơ đồ tương tác giữa các lớp trong hệ thống ..............................................51
Hình 3-4 Biểu đồ tuần tự của quá trình loại bỏ bản ghi nhân bản..............................59
Hình 3-5 Biểu đồ tuần tự của quá tình xử lý bản ghi nghi ngờ nhân bản .....................60
Hình 3-6 Biểu đồ tuần tự của quá trình thiết lập luật cho hệ thống ..............................60


6

DANH MỤC BẢNG
Bảng 1-1 Quan hệ EMP.................................................................................................13
Bảng 1-2

Quan hệ EMP1 ............................................................................................14

Bảng 1-3 Quan hệ NHÂNVIÊN....................................................................................17
Bảng 1-4 Kết quả phép chọn .........................................................................................17
Bảng 1-5 Kết quả phép chọn .........................................................................................18
Bảng 1-6 Kết quả của các phép toán tập hợp ................................................................19

Kí hiệu viết tắt
EDRS

Tên tiếng Anh
Eliminate
system

duplicate

CSDL

Ý nghĩa
record Hệ thống loại bỏ mẩu tin nhân
bản thừa
Cơ sở dữ liệu

CF

Certainty factor

Hệ số chắc chắn

FPE

False Positive Error

Tỉ lệ phán đoán sai

SK
Cardr

phát triển và đóng vai trò quan trọng trong mọi lĩnh vực ứng dụng và nghiên cứu. Đi đôi
với sự lớn mạnh của các hệ thống này là sự xuất hiện những dữ liệu “bẩn” và dữ liệu dị
thường. Dữ liệu dị thường và dữ liệu “bẩn” làm ảnh hưởng rất nhiều tới hiệu quả xử lý
và độ chính xác của kết quả xử lý cũng như ảnh hưởng tới việc biểu diễn và phân tích
dữ liệu. Tệ hại hơn có thể làm hệ thống phần mềm trở nên vô giá trị.
Dữ liệu dị thường và dữ liệu “bẩn” xuất hiện trong dữ liệu thực là chuyện không
thể tránh khỏi, người ta ước tính dữ liệu dị thường và dữ liệu “bẩn” chiếm khoảng 5%.
Thực tế này dẫn tới xu hướng phát triển các phương pháp làm sạch dữ liệu. Không có
mô tả chung nào cho mục đích và cũng không có mô tả bao quát cho quá trình làm sạch
dữ liệu. Làm sạch dữ liệu đòi hỏi rất nhiều loại tri thức cũng như đòi hỏi có nhiều kiến
thức về việc xử lý và bảo trì dữ liệu. Mục đích trước hết của làm sạch dữ liệu là loại bỏ
những nhân bản thừa trong tập hợp dữ liệu có sẵn.
Quá trình làm sạch dữ liệu khó có thể thực hiện được nếu không có sự tham gia
của các chuyên gia hay các kiến thức chuyên gia, vì việc loại bỏ dữ liệu dị thường và dữ
liệu “bẩn” cần phải có kiến thức chuyên gia về lĩnh vực đó. Quá trình làm sạch dữ liệu
là quá trình bán tự động. Nhưng nên xử lý tự động nhiều nhất có thể. Hiệu quả và sự
thành công của quá trình làm sạch dữ liệu phụ thuộc rất nhiều vào kiến thức chuyên gia
hiện có và những thông tin cần thiết để xác định và chỉnh sửa những dữ liệu dị thường.
Làm sạch dữ liệu là một thuật ngữ không rõ ràng và không có định nghĩa chính
xác. Nguyên nhân chính là vì mục đích chính của làm sạch dữ liệu là tìm ra “lỗi” trong
dữ liệu có sẵn, tuy nhiên thế nào là dữ liệu lỗi và thế nào là không lỗi thì phụ thuộc rất
nhiều vào từng lĩnh vực, khó có thể đưa ra một định nghĩa chung. Chính vì điều này,
nhiều phương pháp chỉ tập trung vào một phần nhỏ của kiến thức về lĩnh vực đang xét
bằng cách sử dụng một số thuật toán cũng như áp dụng kinh nghiệm sẵn có.
Có nhiều phương pháp được áp dụng để làm sạch dữ liệu như phân tích cú pháp


10

(parsing), biến đổi dữ liệu (data transformation), tạo các ràng buộc về mặt dữ liệu

cũng đưa ra những kết quả kiểm thử trên dữ liệu thật để đi đến những đánh giá về hiệu
quả của thuật toán.
Chương 4. Kết luận và hướng phát triển. Kết luận, đánh giá những gì đã đạt được và
chưa làm được trong luận văn tốt nghiệp và nêu ra hướng phát triển của đề tài là nội
dung trình bày của chương này.


12

Chương 1

CƠ SỞ LÝ THUYẾT

1.1 CƠ SỞ DỮ LIỆU QUAN HỆ
Các cơ sở dữ liệu và các hệ quản trị cơ sở dữ liệu đã trở thành một thành phần chủ
yếu trong cuộc sống hàng ngày của xã hội hiện đại. Trong vòng một ngày con người có
thể có nhiều hoạt động cần có sự giao tiếp với cơ sở dữ liệu như: đến ngân hàng để rút
tiền và gửi tiền, đăng ký chỗ trên máy bay hoặc khách sạn, truy cập vào thư viện đã tin
học hoá để tìm sách báo, đặt mua tạp chí ở một nhà xuất bản… Tại các ngân hàng, các
cửa hàng, người ta cũng cập nhật tự động việc quản lý tiền bạc, hàng hoá.
Tất cả các giao tiếp như trên được gọi là các ứng dụng của cơ sở dữ liệu truyền
thống. Trong các cơ sở dữ liệu truyền thống, hầu hết các thông tin được lưu giữ và truy
cập là văn bản hoặc số. Những năm gần đây, những tiến bộ về kỹ thuật đã đưa đến
những ứng dụng mới của cơ sở dữ liệu. Các cơ sở dữ liệu đa phương tiện bây giờ có thể
lưu trữ hình ảnh, phim và tiếng nói. Các hệ thống thông tin địa lý có thể lưu trữ và phân
tích các bản đồ, các dữ liệu về thời tiết và các ảnh vệ tinh. Kho dữ liệu và các hệ thống
phân tích trực tuyến được sử dụng trong nhiều công ty để lấy ra và phân tích những
thông tin có lợi từ các cơ sở dữ liệu rất lớn nhằm đưa ra các quyết định. Các kỹ thuật cơ
sở dữ liệu động và thời gian thực được sử dụng trong việc kiểm tra các tiến trình công
nghiệp và sản xuất. Các kỹ thuật tìm kiếm cơ sở dữ liệu đang được áp dụng cho World

11
15
18

NAME
Jones
Smith
Bob
Jane
Mary

AGE
23
45
18
27
31

DEPTNUM
1
2
1
3
1

Bảng 1-1 Quan hệ EMP

Một lược đồ quan hệ được tạo nên từ tên một quan hệ và danh sách các thuộc tính
của nó, kí hiêu một lược đồ quan hệ như sau: <Tên quan hệ>(). Ví dụ: EMP(EMPNUM, NAME, AGE, DEPTNUM) là lược đồ quan hệ của

EMPNUM
3
7
11
15
18

AGE
23
45
18
27
31
Bảng 1-2

DEPTNUM
1
2
1
3
1
Quan hệ EMP1

NAME
Jones
Smith
Bob
Jane
Mary




16

các khóa dự tuyển làm khóa chính của quan hệ. Khóa chính là một khóa dự tuyển mà
các giá trị của chúng được dùng để xác định các bộ trong quan hệ.
Chú ý rằng, khi một lược đồ quan hệ có nhiều khóa dự tuyển thì việc lựa chọn
khóa chính là tùy ý, tuy nhiên tốt nhất là chọn khóa chính gồm một thuộc tính hoặc có
số thuộc tính ít nhất.

1.1.2

Các phép toán đại số quan hệ
Ngoài việc định nghĩa cấu trúc cơ sở dữ liệu và các ràng buộc, một mô hình dữ

liệu phải chứa một tập hợp các phép toán để thao tác dữ liệu. Tập hợp cơ sở các phép
toán mô hình quan hệ tạo nên đại số quan hệ. Các phép toán này giúp cho người sử
dụng xác định rõ yêu cầu lấy tin cơ bản. Kết quả của phép lấy tin là một quan hệ mới,
có thể được tạo ra từ một hoặc nhiều quan hệ.
Các phép toán quan hệ đại số chia làm hai nhóm. Một nhóm bao gồm các phép
toán tập hợp lấy từ lý thuyết tập hợp toán học. Các phép toán đó là phép hợp, phép giao,
phép trừ tập hợp và phép tích Đề Các. Nhóm kia bao gồm những phép toán được xây
dựng đặc biệt cho các cơ sở dữ liệu quan hệ. Các phép toán đó là phép chiếu, phép chọn,
phép nối và một số phép khác.
1.1.2.1 Phép chọn
Phép chọn được sử dụng để chọn ra một tập hợp các bộ thỏa mãn điều kiện chọn
từ một quan hệ. Ta có thể xem phép chọn như bộ lọc, nó chỉ giữ lại những bộ thỏa mãn
điều kiện đặt ra.
Phép chọn được kí hiệu như sau: σ< điều kiện chọn>( R)
Trong đó

Bảng 1-3 Quan hệ NHÂNVIÊN

Để chọn ra các bộ NHÂNVIÊN có lương lớn hơn 2000 ta viết như sau:

σ< Lương > 2000>( NHÂNVIÊN)
Kết quả trả về như dưới đây:
MãNV
02
05

TênNV
Mary
Cathy

Lương
3500
5600

Bảng 1-4 Kết quả phép chọn

Biểu thức logic chỉ ra trong <điều kiện chọn> được tạo nên từ một số hạng mục có
dạng :
<tên thuộc tính> <giá trị hằng>
hoặc <tên thuộc tính> <tên thuộc tính>
trong đó <tên thuộc tính> là tên của một thuộc tính trong R, là
một trong các phép toán so sánh {<, >, ≤, ≥, ≠, =}, <giá trị hằng> là một giá trị hằng từ
miền giá trị của thuộc tính. Các hạng mục có thể được nối với nhau bằng các phép toán
logic AND, OR, NOT để tạo ra một điều kiện chọn chung.
Phép chọn là phép toán có tính chất giao hoán, nghĩa là :


2000
3500
1200
5600

Bảng 1-5 Kết quả phép chọn

1.1.2.3 Các phép toán lý thuyết tập hợp
Nhóm tiếp theo của các phép toán đại số quan hệ là các phép toán toán học thông


19

thường trên các tập hợp. Đó là các phép giao, hợp và trừ tập hợp. Các phép toán này là
phép toán hai ngôi, nghĩa là mỗi phép toán được áp dụng cho hai tập hợp. Khi áp dụng
phép toán này cho cơ sở dữ liệu quan hệ, hai quan hệ tham gia vào một trong phép toán
trên phải có kiểu của các bộ như nhau, hay nói cách khác, chúng phải có cùng một cấu
trúc. Điều đó có nghĩa là, hai quan hệ có cùng số các thuộc tính và mỗi cặp thuộc tính
tương ứng có cùng miền giá trị.
Các phép toán được định nghĩa như sau :
Phép hợp: Hợp của hai quan hệ R và S, kí hiệu là R ∪ S, cho kết quả là một quan
hệ chứa tất cả các bộ có trong R hoặc trong S hoặc trong cả hai. Các bộ trùng lặp bị loại
bỏ.
Phép giao: Giao của hai quan hệ R và S, kí hiệu là R ∩ S, cho kết quả là một quan
hệ chứa tất cả các bộ có trong cả hai quan hệ R và S.
Phép trừ quan hệ. Phép trừ quan hệ R và S, được kí hiệu là R – S, cho kết quả là
một quan hệ chứa tất cả các bộ có trong R nhưng không có trong S.
Ví dụ:
R


21

GiớiTính
Nữ
Nam
Nữ
Nam

R∪S

HọTên
AA
BB
CC
DD
EE
FF

Tuổi
20
18
21
25
20
21

GiớiTính
Nam
Nữ
Nam

Nam

Bảng 1-6 Kết quả của các phép toán tập hợp


20

Các phép toán hợp và giao có tính chất giao hoán, nghĩa là :
R ∪ S = S ∪ R và

R∩S=S∩R

Các phép toán trên cũng có tính chất kết hợp, nghĩa là :
R ∪ (S ∪ T) = (R ∪ S) ∪ T

R ∩ (S ∩ T) = (R ∩ S) ∩ T

và

Phép trừ tập hợp không có tính chất giao hoán.
Ngoài các phép toán trên, còn một phép toán gọi là tích Đề Các. Tích Đề Các còn
gọi là tích hỗn hợp(cross product), được kí hiệu là ×. Đó cũng là phép toán hai ngôi
nhưng quan hệ mà nó áp dụng trên đó không phải là tương thích đồng nhất. Phép toán
này được sử dụng để nối các bộ của hai quan hệ vào một kiểu kết hợp. Kết quả của
R(A1, A2, ..., An) × S(B1, B2, ..., Bm)
là một quan hệ Q với n + m thuộc tính Q(A1, A2, ..., An, B1, B2, ..., Bm). Quan hệ Q có
các bộ được tạo thành do sự kết hợp một bộ của R và một bộ của S.
Ví dụ, xét hai quan hệ sau :
R


cc
cc
dd
dd

Bảng 1-7 Tích Đề Các của hai quan hệ R và S

1.1.2.4 Phép nối
Phép nối được kí hiệu là

và được dùng để kết hợp các bộ có liên hệ với

nhau từ hai quan hệ thành một bộ. Phép toán này rất quan trọng đối với cơ sở dữ liệu


21

quan hệ có nhiều bảng bởi vì nó cho phép ta xử lý các mối liên kết giữa các quan hệ.
Dạng tổng quát của phép nối trên hai quan hệ R(A1, A2,…,An) và S(B1,B2,…, Bm) là
R

S

< Điều kiện nối>

Kết quả của phép nối là một quan hệ Q(A1,A2,…,An,B1,B2,…,Bm) có n+m thuộc
tính. Mỗi bộ của Q là một sự kết nối giữa một bộ của R và một bộ của S khi chúng thoả
mãn điều kiện nối. Sự khác nhau giữa tích Đề Các và phép nối là ở chỗ trong phép nối,
chỉ có các bộ thoả mãn điều kiện nối mới xuất hiện trong kết quả, trong khi đó trong
tích Đề Các mọi tổ hợp của các bộ đều có trong kết quả. Điều kiện nối được chỉ ra trên

dd
ac

A1
aa
ab

B1

A2
bb
ac

B1
bb
ac

B2
gg
hh
ff

B2
gg
hh

Bảng 1-8 Phép nối tê-ta hai quan hệ

Phần lớn các phép nối chỉ cho phép các điều kiện nối với các so sánh bằng. Những



Chú ý rằng nếu không có một tổ hợp các bộ nào thoả mãn điều kiện nối thì kết
quả của một phép nối là một quan hệ rỗng không chứa bộ nào. Nói chung, nếu R có nR
bộ và S có nS bộ thì kết quả của phép nối R với S sẽ có số các bộ lớn hơn 0 và nhỏ hơn
nR.nS. Cỡ của một kết quả nối chia cho cỡ cực đại nR.nS tạo nên một tỷ lệ gọi là chọn lựa
nối, đó là một tính chất của mỗi điều kiện nối. Nếu không có điều kiện nối, mọi tổ hợp
các bộ sẽ được chọn và phép nối trở thành một tích Đề Các.
Phép nối được sử dụng để kết hợp các dữ liệu từ nhiều quan hệ sao cho các thông
tin có liên hệ với nhau có thể được biểu diễn trong một bảng. Đôi khi phép nối được áp
dụng nối một bảng với chính nó. Chúng ta có thể áp dụng phép nối tự nhiên và nối bằng
để nối nhiều bảng với nhau. Nếu ta nối n bảng với nhau thì phải chỉ ra n-1 điều kiện nối.


23

1.2 PHÂN MẢNH CƠ SỞ DỮ LIỆU QUAN HỆ
1.2.1

Khái quát về cơ sở dữ liệu phân tán
Hình dưới đây thể hiện kiến trúc một cơ sở dữ liệu quan hệ. Kiến trúc này không

phải lúc nào cũng được triển khai trong mọi cơ sở dữ liệu nhưng các cấp độ của nó là
các khái niệm cơ bản để chúng ta hiểu được kiến trúc của cơ sở dữ liệu phân tán.
Global schema
Fragement schema

Site
independent
schemas


bộ dữ liệu có trong cơ sở dữ liệu phân tán. Vì vậy, lược đồ toàn cục định nghĩa một cách
chính xác nhất một cơ sở dữ liệu lúc chưa phân tán. Trong tài liệu này chúng ta sử dụng
mô hình quan hệ để mô tả cơ sở dữ liệu phân tán. Khi đó, lược đồ toàn cục bao gồm tập
hợp các quan hệ toàn cục.
Mỗi quan hệ toàn cục có thể được chia thành nhiều phần không giao nhau, người


24

ta gọi là phân mảnh. Có nhiều cách để thực hiện phân mảnh một quan hệ toàn cục, ví
dụ: phân mảnh ngang, phân mảnh dọc, phân mảnh hỗn hợp… Sự khớp nhau giữa lược
đồ toàn cục và các phân mảnh gọi là lược đồ phân mảnh. Quan hệ này là một-nhiều một quan hệ toàn cục có nhiều phân mảnh nhưng một phân mảnh chỉ thuộc về một quan
hệ toàn cục mà thôi. Các phân mảnh được gọi tên bằng tên quan hệ toàn cục cộng thêm
chỉ số kèm sau, ví dụ Ri chỉ các phân mảnh của quan hệ toàn cục R.
Phân mảnh là thành phần logic của quan hệ toàn cục, chúng được lưu trữ vật lý tại
một hoặc nhiều nơi khác nhau. Lược đồ phân bố(allocation schema) định nghĩa vị trí
lưu trữ phân mảnh. Kiểu phân bố phân mảnh quy định cơ sở dữ liệu có dư thừa hay
không bị dư thừa. Tất cả phân mảnh thuộc về cùng một một quan hệ toàn cục R và lưu
trữ tại vị trí j tạo thành hình ảnh vật lý của quan hệ toàn cục R tại vị trí j. Vì vậy chúng
ta có quan hệ một-một giữa hình ảnh vật lý và cặp đôi quan hệ toàn cục-vị trí, hình ảnh
vật lý được kí hiệu bằng tên quan hệ toàn cục cộng với số thứ tự của vị trí. Để phân biệt
các phân mảnh với nhau ta sử dụng số mũ, ví dụ: Rj là hình ảnh vật lý của quan hệ toàn
cục R tại vị trí j.
Quay trở lại kiến trúc cơ sở dữ liệu phân tán ở trên, ta thấy ba cấp độ trên cùng
mối quan hệ giữa các đối tượng không phụ thuộc vào mô hình dữ liệu của hệ quản trị cơ
sở dữ liệu. Tại mức thấp hơn, cần phải ghép giữa hình ảnh vật lý với đối tượng tương
ứng trong hệ quản trị cơ sở dữ liệu địa phương.
Mô hình ở trên mô tả rất cơ bản kiến trúc của một cơ sở dữ liệu phân tán. Mục
đích chính của mô hình này là: phân mảnh dữ liệu, lưu trữ, kiểm soát dư thừa dữ liệu và
độc lập với các hệ quản trị cơ sở dữ liệu địa phương.

2. Tính tái thiết được. Bao giờ cũng phải xây dựng được quan hệ toàn cục từ những
phân mảnh của nó.
3. Tính tách biệt. Các phân mảnh không được giao nhau, vì thế dữ liệu nhân bản có thể
được kiểm soát ở cấp độ lưu trữ. Quy tắc này có tác dụng chủ yếu đối với phân
mảnh ngang, phân mảnh dọc có thể không nhất thiết tuân theo quy tắc này.
Sau đây chúng ta xem xét các loại phân mảnh.
1.2.2.1 Phân mảnh ngang
Phân mảnh ngang là cách chia các bản ghi của một quan hệ toàn cục thành các tập
con, các tập con này có cùng tính chất. Có thể biểu diễn phân mảng ngang bằng phép