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

PHẠM THỊ CHI LÊ

TỐI ƢU HÓA TRUY VẤN
CƠ SỞ DỮ LIỆU SUY DIỄN

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

Thái Nguyên - 2013

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

/


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

PHẠM THỊ CHI LÊ

TỐI ƢU HÓA TRUY VẤN CƠ SỞ DỮ LIỆU
SUY DIỄN

Chuyên ngành : Khoa học máy tính
Mã số : 60.48.01
LUẬN VĂN THẠC SĨ KHOA HỌC

NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS ĐOÀN VĂN BAN


Trƣớc tiên tôi bầy tỏ lời cảm ơn chân thành đến các Thầy, Cô giáo đã
giảng dạy, hƣớng dẫn và giúp đỡ tôi trong thời gian học tập và nghiên cứu
hoàn thành luận văn này.
Xin đƣợc bầy tỏ lòng biết ơn sâu sắc tới Thầy giáo PGS.TS Đoàn Văn
Ban đã tận tình hƣớng dẫn, giúp đỡ và đóng góp cho tôi nhiều ý kiến quí báu
để hoàn thành luận văn này.
Xin chân thành cảm ơn các Thầy, Cô giáo Trƣờng Đại học Công nghệ
thông tin & truyền thông Thái Nguyên và Viện Công nghệ thông tin đã giảng
dạy, giúp đỡ và tạo điều kiện thuận lợi cho tôi trong thời gian học tập tại
Trƣờng.
Tôi xin gửi lời cảm ơn đến các bạn đồng nghiệp và các bạn học viên lớp
Cao học K10A khóa 2011 – 2013 đã giúp đỡ và tạo điều kiện thuận lợi cho tôi
trong quá trình học tập và làm luận văn.
Cuối cùng, xin chân thành cảm ơn gia đình và bạn bè đã động viên, quan
tâm, giúp đỡ tôi hoàn thành khóa học và luận văn.

PHẦN MỞ ĐẦU
Cơ sở dữ liệu (CSDL) là một trong những lĩnh vực đƣợc tập trung nghiên
cứu và phát triển của công nghệ thông tin, nhằm giải quyết các bài toán quản
lý, tìm kiếm thông tin trong những hệ thống lớn, đa dạng, phức tạp cho nhiều
ngƣời sử dụng trên máy tính điện tử. Cùng với sự ứng dụng mạnh mẽ công
nghệ thông tin vào đời sống xã hội, kinh tế, quốc phòng ... Việc nghiên cứu
CSDL đã và đang phát triển ngày càng phong phú và hoàn thiện.
Tuy nhiên CSDL kinh điển không có khả năng suy dẫn ra sự kiện mới, khả
năng tiềm ẩn không đƣợc khai thác hết nên từ những năm 1970-1980 có một

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

/


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

/


3

hợp với câu truy vấn. Tuy nhiên quá trình tính toán có thể kéo dài vô hạn. Các
phƣơng pháp dƣới lên đảm bảo tính kết thúc trong quá trình tìm lời giải của
câu truy vấn, nhƣng điều này không có nghĩa là nó hiệu quả. Chúng thƣờng
không định hƣớng đích, nhiều sự kiện không thích hợp với câu truy vấn cũng
đƣợc tính. Các chiến lƣợc dƣới lên không xem xét câu truy vấn trong suốt quá
trình định giá, tức là việc tính toán không đƣợc gắn liền với câu truy vấn nhƣ
thƣờng xảy ra trong các phƣơng pháp trên xuống.
Trong thời gian gần đây, một số phƣơng pháp mở rộng để trả lời câu truy
vấn đƣợc đề xuất nhằm mục đích tạo ra một chiến lƣợc tìm kiếm hƣớng đích,
đồng thời có tính hiệu quả là đảm bảo kết thúc quá trình tính toán câu trả lời
truy vấn. Điển hình đó là phép biến đổi ma tập (magic set transformation) và
định giá bảng. Các phƣơng pháp này đƣợc đánh giá là một trong những kỹ
thuật tối ƣu câu truy vấn có hiệu quả trong CSDL suy diễn. Nó đã kết hợp
đƣợc các ƣu điểm của kỹ thuật định giá theo kiểu trên xuống và dƣới lên, do
đó giảm thiểu đƣợc số các sự kiện cần tính và tìm kiếm trên CSDL.
Ý tƣởng chính của phép biến đổi ma tập là mô phỏng sự lan truyền các trị
ràng buộc đƣợc tạo ra trong phƣơng pháp định giá câu truy vấn theo kiểu trên
xuống. Sự lan truyền này nhận đƣợc bằng cách viết lại chƣơng trình gốc ban
đầu. Trong mỗi quy tắc gốc một điều kiện mới đƣợc thêm vào để hạn chế việc
tính toán trên quy tắc. Các điều kiện này đƣợc xem là các quan hệ lọc. Một
quy tắc mới đƣợc tạo ra để mô phỏng sự lan truyền các trị ràng buộc.
Luận văn gồm phần mở đầu, ba chƣơng nội dung, phần kết luận, tài liệu
tham khảo và phần phụ lục.

Anditi, hệ Coral; giới thiệu về chương trình logic với các khái niệm cơ bản
như logic vị từ, hạng thức, công thức đóng, bộ kí tự ...và ngữ nghĩa của
chương trình logic; cuối chương giới thiêu về cơ sở dữ liệu Horn với các khái
niệm, định lý, hệ quả, ngữ nghĩa của cơ sở dữ liệu Horn và các ví dụ để minh
chứng cho phần lý thuyết.
1.1 Giới thiệu về cơ sở dữ liệu suy diễn
Tính từ thời điểm xuất hiện các hệ quản trị cơ sở dữ liệu đầu tiên (khoảng
những năm 1960) đến nay, công nghệ CSDL đã tiến triển nhanh chóng, và đã
thu đƣợc rất nhiều thành tựu trong các lĩnh vực ứng dụng khác nhau của công
nghệ thông tin. Một đặc điểm chung của các hệ CSDL là khả năng quản lí
những khối lƣợng lớn dữ liệu, tuy nhiên thƣờng chỉ thực hiện các thao tác đơn
giản để xử lí dữ liệu. Vì vậy, việc nghiên cứu cơ sở dữ liệu suy diễn đƣợc đặt
ra nhƣ một yêu cầu thiết thực.
Mặt khác, song song với sự phát triển của các hệ quản trị CSDL, các hệ
chuyên gia đã đƣợc phát triển để trợ giúp quá trình ra quyết định trong các
lĩnh vực chuyên ngành hẹp. Đặc điểm chính của các hệ chuyên gia là cung
cấp khả năng suy luận nhằm hỗ trợ việc ra quyết định, nhƣng chúng thƣờng
không có khả năng quản lí các khối lƣợng lớn thông tin.
Từ các yếu tố trên, các hệ CSDL suy diễn đã đƣợc đề xuất, xem nhƣ một
giải pháp khắc phục những hạn chế của các hệ CSDL truyền thống bằng cách

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

/


6

phối hợp, theo một cách nào đó, các đặc trƣng nổi trội đƣợc cung cấp bởi các
hệ chuyên gia.

Cơ sở dữ liệu suy
diễn
Hình 1.1. Sự tiến triển song song của các hệ CSDL và các hệ chuyên
gia
Hình trên đây minh hoạ sự tiến triển song song của các hệ CSDL và các hệ
chuyên gia.
Khái niệm về CSDL suy diễn cũng đƣợc nhiều nhà nghiên cứu đề cập theo
hƣớng phát triển các kết quả mà Green đã đạt đƣợc vào năm 1969 về các hệ
thống hỏi – đáp. Xuất phát từ quan điểm lý thuyết, các CSDL suy diễn có thể
Số hóa bởi Trung tâm Học liệu

/


7

đƣợc coi nhƣ các chƣơng trình logic với sự khái quát hoá khái niệm về CSDL
quan hệ. Đó là cách tiếp cận của Brodie và Manola vào năm 1989, của Codd
vào năm 1970, của Date vào năm 1986, của Gardarin và Valdurier vào năm
1989 và của Ullman vào năm 1984 [2].
Nhƣ vậy, CSDL suy diễn có thể đƣợc coi nhƣ các chƣơng trình logic với
sự khái quát hóa khái niệm về CSDL quan hệ bằng cách hỗ trợ các khung
nhìn đệ qui và dữ liệu không nguyên tử. Điều này làm cho viêc lập trình
CSDL dễ hơn nhiều đối với các ứng dụng.
1.1.1 Cơ sở dữ liệu suy diễn (CSDLSD) là gì
CSDL truyền thống không suy diễn các sự kiện mới, ví dụ không thể suy
ra đƣợc là Vân là cha của ai nếu dựa vào quan hệ parent(X, Y).
Cơ sở dữ liệu suy diễn là cơ sở dữ liệu (CSDL) có khả năng suy diễn ra
một số sự kiện mới từ những sự kiện, các luật đƣợc lƣu trữ trong CSDL.
Mô hình cơ sở dữ liệu suy diễn (CSDLSD) là sự tích hợp của mô hình cơ

Bố(Phát, Mai)
- Các luật suy diễn
Cha_mẹ(x, y) ← Bố(x, y)
Cha_mẹ(x, y) ← Mẹ(x, y)
Bà(x, y) ← Mẹ(x, z) ^ Cha_mẹ(z, y)
Tổ_tiên(x, y) ← Cha_mẹ(x, y)
Tổ_tiên(x, y) ← Cha_mẹ(x, z) ^ Tổ_tiên(z, y)
- Các rằng buộc toàn vẹn
IC1(x) ← Cha_mẹ(x, x)
IC2(x) ← Bố(x, y) ^ Mẹ(x,y)

Tóm lại, một CSDL suy diễn là một bộ ba (F, DR, IC), trong đó F là một
tập hữu hạn các sự kiện cơ sở, DR là một tập hữu hạn các luật suy diễn, và IC
là một tập hữu hạn các rằng buộc toàn vẹn. Tập F các sự kiện đƣợc gọi là
phần ngoại diên của CSDL (còn gọi là CSDL ngoại diên – EDB), còn tập DR
và IC làm thành nội hàm của CSDL (còn gọi là CSDL nội hàm – IDB) [10],
[16], [20].
Các tân từ CSDL đƣợc chia thành các tân từ cơ sở (ngoại diên) và các tân
từ dẫn xuất (còn gọi là nội hàm hay khung nhìn).
Số hóa bởi Trung tâm Học liệu

/