Tối ưu hóa truy vấn cơ sở dữ liệu suy diễn

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

ĐẠ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 http://www.lrc-tnu.edu.vn/

ĐẠ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

Thái Nguyên - 2013

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

LỜI CAM ĐOAN

Tôi cam đoan luận văn này là do bản thân tự nghiên cứu và thực hiện theo sự

hƣớng dẫn khoa học của PGS.TS Đoàn Văn Ban.

Tôi hoàn toàn chịu trách nhiệm về tính pháp lý quá trình nghiên cứu khoa học

của luận văn này.

Thái Nguyên, ngày tháng năm 2013

Ngƣời Cam Đoan

Phạm Thị Chi Lê

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

1

LỜI CẢM ƠN

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 http://www.lrc-tnu.edu.vn/

2

trào lƣu sôi nổi muốn đƣa vào CSDL quan hệ những cơ chế suy diễn, những

tri thức tổng quát. CSDL suy diễn là một lĩnh vực khá mới mẻ, trong thời gian

qua ngƣời ta đã tập trung nghiên cứu và cho nhiều kết quả thú vị cả lĩnh vực

lý thuyết và ứng dụng. CSDL suy diễn có khả năng sử dụng các tính năng của

lập trình logic để thực hiện các suy diễn nhằm tạo ra thông tin mới dựa trên

các luật suy diễn và dữ liệu đƣợc lƣu trữ trong cơ sở dữ liệu.

CSDL suy diễn, một sự mở rộng CSDL quan hệ, không những chỉ có các

nguyên tố nền tƣơng ứng với các bộ của các quan hệ trong CSDL quan hệ mà

còn có các quy tắc tổng quát (gồm các quy tắc suy diễn và các ràng buộc toàn

vẹn). Những quy tắc này tạo thành phần mở rộng. So với các hệ CSDL quan

hệ, các hệ CSDL suy diễn thừa nhận một kiểu lý thuyết chứng minh, nghĩa là

nó đƣợc xem xét nhƣ một lý thuyết bao gồm một tập các công thức cấp một,

còn việc thực hiện một câu truy vấn hoặc làm thoả mãn một ràng buộc toàn

vẹn có thể xem nhƣ chứng minh một công thức cấp một là hệ quả logic của lý

thuyết đã cho.

Sức mạnh biểu diễn của CSDL suy diễn là thật sự quan trọng trong nhiều

lĩnh vực khác nhau. Các ứng dụng tiêu biểu của CSDL bao gồm hệ chuyên

gia, hệ hỗ trợ quyết định, phân tích tài chính, phân tích ngôn ngữ, cú pháp ...

Tuy vậy, trong lĩnh vực CSDL suy diễn, mặc dù đã có nhiều kết quả có giá trị

nhƣng cũng có nhiều vấn đề cần nghiên cứu tiếp, đặc biệt là các vấn đề về

ngữ nghĩa của phủ định và tối ƣu hoá câu hỏi (truy vấn).

Luận văn nghiên cứu các kỹ thuật tối ƣu câu truy vấn trên CSDL suy diễn.

Có ba kiểu tiếp cận khác nhau trong việc định giá câu truy vấn: Các phƣơng

pháp trên xuống, các phƣơng pháp dƣới lên và các phƣơng pháp có sự kết hợp

các đặc trƣng của phƣơng pháp trên xuống và dƣới lên. Các phƣơng pháp trên

xuống (còn gọi là suy luận đích hoặc kết xâu lùi) có điểm khởi đầu của việc

tính toán là từ đích truy vấn và chúng sẽ không tính các sự kiện không thích

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

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.

Chƣơng 1: Trình bày khái quát về Cơ sở dữ liệu suy diễn và ngữ nghĩa

chƣơng trình logic.

Chƣơng 2: Trình bày các phƣơng pháp tối ƣu câu truy vấn trong cơ sở dữ

liệu suy diễn.

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

4

Chƣơng 3: Cài đặt chƣơng tr .

Phần phụ lục giới thiệu về Swi-Prolog và hƣớng dẫn cách thức làm việc với

Swi-Prolog.

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

5

CHƢƠNG 1. CƠ SỞ DỮ LIỆU SUY DIỄN VÀ NGỮ NGHĨA

CHƢƠNG TRÌNH LOGIC

Chương 1 trình bày kiến thức cơ bản về cơ sở dữ liệu suy diễn với các khái

niệm, cấu trúc, mô hình, mục đích, chức năng cơ bản của cơ sở dữ liệu suy

diễn và giới thiệu một số hệ quản trị cơ sở dữ liệu suy diễn như hệ LDL, hệ

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