intTypePromotion=1

Một số cải tiến đối với phép biến đổi ma tập để tối ưu hóa câu truy vấn trên chương trình datalog

Chia sẻ: Kinh Kha | Ngày: | Loại File: DOC | Số trang:8

0
21
lượt xem
0
download

Một số cải tiến đối với phép biến đổi ma tập để tối ưu hóa câu truy vấn trên chương trình datalog

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài báo tập trung thảo luận một số vấn đề liên quan đến phép biến đổi ma tập và đề xuất một số cải tiến nhằm nâng cao hiệu quả của nó trong việc tối ưu câu truy vấn trên chương trình Datalog. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:
Lưu

Nội dung Text: Một số cải tiến đối với phép biến đổi ma tập để tối ưu hóa câu truy vấn trên chương trình datalog

TẠP CHÍ KHOA HỌC, Đại học Huế, Số 14, 2002<br /> <br /> <br /> <br /> <br /> MỘT SỐ CẢI TIẾN ĐỐI VỚI PHÉP BIẾN ĐỔI MA TẬP <br /> ĐỂ TỐI ƯU HÓA CÂU TRUY VẤN TRÊN CHƯƠNG TRÌNH DATALOG <br /> <br /> Lê Mạnh Thạnh, Trương Công Tuấn<br /> Trường Đại học Khoa học, Đại học Huế<br /> <br /> <br /> <br /> 1. MỞ ĐẦU<br /> Phép biến đổi ma tập được đánh giá là một trong những kỹ  thuật tối  ưu câu <br /> truy vấn rất có hiệu quả  trong cơ sở dữ liệu suy diễn. Lý do quan trọng đối với sự <br /> thành công của kỹ  thuật này là sự  kết hợp được các  ưu điểm của kỹ  thuật  ước  <br /> lượng trên xuống (top­down) và dưới lên (bottom­up), từ đó giảm thiểu được số  các <br /> sự  kiện cần tính và tìm kiếm trên cơ  sở dữ liệu. Tính lôi cuốn của kỹ thuật ma tập  <br /> được thể  hiện  ở  tính hiệu quả  của nó ([3, 4, 5]). Tuy nhiên, phép biến đổi ma tập  <br /> chưa hẳn là một chiến lược định giá câu truy vấn tốt nhất. Bài báo tập trung thảo <br /> luận một số vấn đề liên quan đến phép biến đổi ma tập và đề  xuất một số cải tiến <br /> nhằm nâng cao hiệu quả  của nó trong việc tối  ưu câu truy vấn trên chương trình <br /> Datalog.<br /> <br />  2. MỘT SỐ KHÁI NIỆM CƠ SỞ<br /> Trong khuôn khổ một bài báo, chúng tôi chỉ trình bày tóm tắt một số khái niệm <br /> cơ sở của phép biến đổi ma tập. Để có các chi tiết đầy đủ hơn cũng như một số khái <br /> niệm khác của cơ sở dữ liệu suy diễn có thể xem trong [1, 5].<br /> 2.1 Tô điểm (Adornment): <br /> Tô điểm là cách chú thích trên các vị  từ  để  cung cấp thông tin về  các vị  từ  sẽ <br /> được sử  dụng như thế  nào trong quá trình định giá câu truy vấn. Ta có một số  định <br /> nghĩa:<br /> (i) Một đối của một đích con trong quy tắc r được gọi là buộc nếu trong suốt <br /> quá trình định giá câu truy vấn, mọi đích được tạo ra từ đích con này có giá trị hằng ở <br /> vị trí của đối này. Ngược lại, đối được gọi là tự do.<br /> <br /> 5<br /> (ii) Một tô điểm của vị từ  p(t1,t2,...,tk) là một dãy các ký tự  b và f  có chiều dài <br /> k. Nếu ký hiệu thứ  i của tô điểm là b thì đối thứ  i của p là buộc, nếu ký hiệu thứ  i <br /> của tô điểm là  f  thì đối thứ  i  của p là tự do. Chỉ có các vị từ IDB là được tô điểm.<br /> (iii) Cho quy tắc p   q1 q2 ... qn và w là tô điểm của vị từ p, tô điểm  i của các <br /> đích con  qi (t i ,1 ,..., ti ,ni ) được xác định như sau: Nếu ti,j là hằng hoặc biến đã xuất hiện <br /> trong đích con qk trước đó (k 
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2