Giáo trình Hệ cơ sở dữ liệu phân tán và suy diễn: Phần 2 - Nguyễn Văn Huân, Phạm Việt Bình

Chia sẻ: Na Na | Ngày: | Loại File: PDF | Số trang:80

Thêm vào BST

Báo xấu

259
lượt xem 72
download

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

Giáo trình Hệ cơ sở dữ liệu phân tán và suy diễn: Phần 2 có nội dung trình bày cơ sở dữ liệu suy diễn, cơ sở dữ liệu hướng đối tượng, thực hành một số ứng dụng. Mời bạn đọc tham khảo nội dung phần 2 tài liệu để hiểu về các cơ sở dữ liệu trên.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình Hệ cơ sở dữ liệu phân tán và suy diễn: Phần 2 - Nguyễn Văn Huân, Phạm Việt Bình

C H Ư Ơ N G III C ơ SỞ DỮ LIỆU SUY DIỄN 3 .1. G ỈÓ Ì T H IỆ U C H Ư N G - Khái niệm về CSDL suy diễn được nhiều nhà nghiên cứu đề cập đến 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 câu hòi - trả lời. - Xuất phát từ quan điểm lý thuyết, các CSDL suy diễn có thể đượ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 Ĩ986, của Gardarin và Valdurier vào nàm 1989 và của Ullman vào năm 1984. - Lập trình logic là mảng công việc trước tiên khi chứng minh định lý cơ học. Sự thật thì việc chứng minh định lý đã tạo nên cơ sờ cho hầu hết hệ thống lập trình logic hiện nay. Tư tưỏĩig cơ bản cùa lập trình logic là sử dụng logic toán học như ngôn ngữ lập trình. Điều này được đề cập trong tài liệu của Kowaski năm 1970, và được Colmerauer đưa vào thực hành năm 1975 trong các cài đặt ngôn ngữ lập trinh logic đầu tiên, tức là ngôn ngữ PROLOG (PROgramming LOGic). Nhờ sự hình thức hoá, Kowalski đã xem xét tập con của các logic bậc một, gọi là logic mệnh đề Hom. Một câu hay một mệnh đề theo logic có thể có nhiều điều kiện đúng nhưng chỉ có một hay không có kết luận đúng. - Đối với nhu cầu thực hành CSDL suy diễn xử lý các câu không phức tạp như các câu trong hệ thống lập trình logic, s ố các luật, tức là số các câu với các điều kiện không trống trong CSDL suy diễn nhỏ hon số các sự kiện, tức các câu với điều kiện rỗng. - Một khía cạnh khác nhau nữa giữa CSDL suy diễn và lập trình logic là các hệ thống lập trình logic nhẩn mạnh các chức năng, trong khi CSDL suy dierì rĩhấn mạnh tỉnh hiệu quá. ( 'ơ chế suy dien dùng trong CSDL suy diễn đê tỉnh toán trà lời không đuực tông quát như trong lập trình logic. -•N goài việc dùng logic đế diễn tá các câu CSDL, người ta còn dùng logic đế diễn tá những cáu hói V Ĩ các điều kiện toàn vẹn. C 3 .2 . C ơ S Ở D ữ L IỆ U S U Y D IỄ N 3 .2 .1 . M ô h ìn h c ơ s ở d ữ liệu su y d iễn Mô hinh dữ liệu gồiư: + Kí pháp toán học để mô tả hinh thức dữ liệu và các quan hệ ; + Kỹ thuật để xử lý dữ liệu như trả lời các câu hỏi, kiếm tra điều kiện toàn vẹn. 129
Ngôn ngữ bậc một được dùng như kí pháp toán học để mô tả dữ liệu trong mô hình CSDL suy diễn và dữ liệu được xử lý trong các mô hình như vậy nhờ việc đánh giá công thức logic. Tiếp cận của logic bậc một như nền tảng lý thuyết của các hệ thống CSDL suy diễn. Tuy nhiên, để dễ biểu diễn hình thức các khái niệm về CSDL suy diễn, ta thường dùng phép toán vị tìr, tức logic vị từ bậc nhất. Logic vị tìr bậc nhất là ngôn ngũ hình thức dùng để thể hiện quan hệ giữa các đối tượng và đế suy diễn ra quan hệ mới. Định nghĩa 1: Mỗi một hằng số, một biến số hay một hàm số áp lên các term là một hạng thức (term). Hàm n ngôi f(x l, x2,..., xn); xi I i = 1, 2,..., n là một hạng thức thì f(x l, x 2 ,..., xn) là một term. Định nghĩa 2: Công thức nguyên tổ (công thức nhỏ nhất) là kết quả của việc ứng dụng một vị từ trên các tham số của term dưới dạng P(tl, í2,..., ín). Nếu p là vị từ có n ngôi và ti I i = 1, 2,..., n là một hạng thức (term). Định nghĩa 3: (Literal) Dãy các công thức nguyên tố hay phủ định của công thức nguyên tố đã được phân tách qua các liên kết logic (a, V, -T V 3) thì công thức đó , , được thiết lập đúng đắn. (i): Một công thức nguyên tố là công thức thiết lập đúng đắn. (ỉi): F, G là Công thức thiết lập đúng đắn => F A G, F V G, F -> G, F 4-» G, F , G cũng là các công thức thiết lập đúng đắn. (iii): Nếu F là Công thức thiết lập đúng đắn, mà X là một biến tự do trong F => (Vx)F và (3x)F cũng là các công thức thiết lập đúng đắn (Vx, 3x trong F). Vỉ dụ 3.1: Cho quan hệ R(A1, A 2 ,.. An) với n bậc (tức n thuộc tính) => là một vị tìr n ngôi. Nếu reR (r bộ của R) => (r.A l, r.A 2,..., r.An) => R(A1, A2,..., An) nhận giá trị đúng. Nếu ríSR (r bộ của R) => gán (r.A l, r.A 2,..., r.An) => R(A1, A2,..., An) nhận giá trị sai. Định nghĩa 4: Câu (Clause) Công thức có dạng PlAP2A....APn Q1a Q2a .... a Qìi Trong đó: Pi và Qj (ij=l,2,...,n) là các Literal dương. Trong hệ thống logic, Literal dương có dạng nguyên tố, nhỏ nhất, trái với Literal âm là phủ định của nguyên tố. Định nghĩa 5: Câu Horn (Horn clause) Là câu cỏ dạng PlAP2A....APn -> Q1 Định nghĩa 6: CSDL sụy diễn tổng quát (General deductive database) CSDL suy diễn tồng quát, hay CSDL tổng quát, hay CSDL suy diễn được xác định như cặp (D,L), trong đổ D là íập hữu hạn của các câu CSDL và L là ngôn ngữ bậc một. Giả sử L có ít nhất hai ký hiệu, một là ký hiệu hằng số và một ký kiệu vị từ. + Một CSDL xác định (hay CSDL chuẩn) là CSDL suy diễn (D,L) mà D chỉ chứa các câu xác định (câu chuẩn). + Một CSDL quan hệ là CSDL suy diễn (D,L) mà D chi chứa các sự kiện xác định. 130
Vậy CSDL quan hệ là một dạnu đặc biệt cũa CSDL tồniì quát, hay chuẩn, hay xác định. Còn một CSDL. xác định là dạng đặc biệt của CSDL chiiấn hav tồng quát. 3 .2 .2 . Lý th u y ế t m ô h ìn h đối v ó i cơ sỏ’ d ữ iiệu q u a n hệ 3.2.2. L N h ìn nhận c ơ s ở d ữ liệu theo quan điểm logic Một CSDL có thể được nhìn nhận dưới quan điểm của logic như sau: • LÝ thuyết bậc một; • Diễn giải của lý thuyết bậc một. Theo quan điềm diễn giải, các câu hỏi và các điều kiện toàn vẹn là công thức dùng để đánh giá việc sử dụng định nghĩa ngũ' nghĩa. Còn theo quan điềm lý th u y ế t các câu hỗi đưọc coi như các định lý có thể chứng minh được hay cònn thức hiến nhiên theo lý thuyết này. Hai tiếp cận này được tham chiếu đen như quan điếm lý thuyết mỏ hình, hay quan điểm cấu trúc quan hệ, và quan điểm lý thuyết chứng minh. Hai quan điếm trẻn đà đưọc hình thức lìoá thành khái niệm tưong ứng của CSDL thônỉỉ thưòng vả CSDL suy diễn. Tư tưỏng đằng sau quan điếm lý thuyết chứng minh của CSDL (D, L) là: (i) Xây dựng một lý thuyết T, gọi là lý thuyết chửng minh của (D,L). bàng cách dùng các câu D và ngôn ngữ L; (ii) Trá lời các câu hòi trong CSDL, 3.2.2.2. N hìn lạ i c ơ s ở d ữ liệu quan hệ ở đây ta xét lớp các CSDL quan hệ. tức là các sụ- kiện làm nền dựa trên nền cúa các sự kiện, với các ngôn ngữ không chứa bất kỳ kí hiệu hàm nào. Các giả thiết được đặt ra trên lóp của các CSDL quan hệ đế đánh giá các câii hỏi; 1) G ià thiết về thế giói đó ng (( 'VVA Close World Assumption): Kháng định rằng các ĩhỏiìg tin khỏng đíiiìg trong C'SDL dirọc coi là sai, lức là R (al, an) coi là đúng chì khi sụ- kiện R(aK a2.....an) không xuất hiện trong CSDL. Ví dự. Có CSDL sau; Hoc sinh(Xuân) Sinhvìen(Đ ông) Nghiên cưu(Đông) Thich(Xuân. Toán) Như vậy theo CWA thì bộ “ .Thich(Đỏng, Toán) được giả sử là đúng, tức Đông không thích Toán. 2) Gỉả thiết về tên duy nhất (UNA Unique Name Assumption); Khẳng định các hằng số của các tên khác nhau được coi là khác nhau. Theo ví dụ trẽn có thể nói ràng hai hằng số Xuân vàĐông gán tên duy nhất cho haisinh viên khác nhau. 3) G iả thiết về bao đóng cúa miền (DCA Domain Closure Assumption); Cho ràng không có các hằng số ngoài các hằng số trong ngôn ngữ của CSDL. 131
Theo ví dụ trên có tìiể nói rằng Triết không phải là hằng đủng. Cho CSDL quan hệ (D,L), D có một vài hạn chế L không chứa kí hiệu hàm nào. Vậy CSDL này có thể được coi là diễn giải của lý thuyết bậc môt gồm có ngôn ngữ L và các biến của L, như đã được sẳp đặt trên miền trong diễn giải này. V iệc đánh giá công thức Logic trong diễn giải này dựa trên: R (al, an) đủng chỉ khi R (al, a 2 ,..., an) e D Các tiên đề của ngôn ngữ T: Theo quan điểm lý thuyết chứng minh của CSDL quan hệ thu được bằng cách xây dựng lý thuyết T ưong ngôn ngữ L. T l. Xác nhậìĩ: Đối với mồi sự kiện R (al, a2,...,an) E D - > R (al, an) được xác định. T2. Các tiên đề đầy đù: Với mồi kí hiệu quan hệ R, n ế u R ( a ; ,a ^ ,...,a ‘ ) ,R ( a f ,a ^ ,..„ R(a,", a ỉ ' ,..., ) kí hiệu cho các sự kiện của R thì tiên đề đầy đủ đối với R là: V x l, V x 2 ,..., Vxn R (al, a2,..., a n )-> (x l = aỊ A x2 = a 2 A ...A x n = aỊ, ) v * ’‘S í ' (xl= a f ax2 = d j a . . . A x n = a ^ ) V... v ( x 1 = aỊ " a x 2 = a ... a x n = a ™ ) T3. Các tiên đề về tên duy nhất: Nếu a l, a2,..., ap là tất cả những kí hiệu hằng số của L thì: (al a2), (al * a 3 ( a l ÌẾ 3p), (a2 * a3), (a2 ^ a 4 ),..., (ap.i T4. Các tiên đề về bao đóng của miền: Nếu a l, a2,..., ap là các kí hiệu hằng số của L thì: V x((x= al) V (x=a2) V ...V (x=ap)) T5. Các tiên đề tương đương: 1. Vx(x=x) 2. VxVy((x=y) -> (y=x)) 3. VxVyVz ((x=y) A ( y = z ) ( x = z ) ) 4. V x l,V x l,...,V x n (P (x l, TÚ.,..., xn) A ( x l= y l) A (x2=y2) A ... A (xn=yn) -> (y l, yn)) 3.2.3. Nhìn nhận cơ sở dữ liệu suy diễn ở đây chi nhìn nhận lý thuyết chứng minh áp dụng cho CSDL suy diễn. Ngôn ngữ L cùa CSDL (D, L) được xây dựng chỉ bằng các kí hiệu xuất hiện trong D, và người ta có thể dùng bất kỉ ngữ nghĩa thủ tục nào trong ngữ cảnh của chương trinh logic như công cụ để tìm các câu trả lời bằng cách suy diễn từ lý thuyết chứng minh T, lý thuyết T đảm bảo ngữ nghĩa của D nhất trí với ngữ nghĩa của T. Liên quan đến CSDL suy diễn, người ta đưa ra Comp (D ) như là lý thuyết chứng minh của CSDL (D, L) và đùng cách giải SLDNF để tim câu trả lời cho câu hỏi. Giả sử (D, L) là CSDL chuẩn. Như trong trường hợp của CSDL quan hệ, quan điểm lý thuyết chứng minh của D đạt được bằng cách xây dựng một lý thuyết T frong ngôn ngữ L. 132
C ác tiên đề lý th u y ết của T n h ư sau: 1) C ác tiên đề về đầy đủ: Tiên đề có được do hoàn thiện mỗi kí hiệu vị từ của u tưong ứng vói các câu trong D. 2) Tiên đề về d u y nhất của tên và về tính tươ ng đư ơ n g: các tiên đề về lý thuyết tương đưo'ng là tuỳ theo các kí hiệu hằng số, hàm số và vị từ của L. 3) Tiên đ ề về bao đó ng của miền: Nấu a l, a2...., ap là tất cả những phần tử của L và fq là các kí hiệu hàm số của L, thì tiên đề về bao đóng của miền, theo Lloyd năm 1987, Mancarella năm 1988 như sau; Vx((x="al) V (x=ap) V (3x1, 3x2,..., 3xm(x xm))) V ... V (3 y l, 3y2,..., 3 y n (x = fq (yl, Y 2 ,...,y n )))) 3 .2 .4 . C á c g ia o tác trên c ơ s ở d ữ liệu suy d iễn Đ ịnh nghĩa / ; G iao tác (T ransaction) M ột giao tác trong CSDL suy diễn là một xãu hữu hạn của các phép toán, hay các hành động bỗ sung, loại bỏ hay cập nhật các cãíL Vì một CSDL suy diễn được xem như tập các câu, tức là theo quan điểm lý thuyết mô hinh, không một phép loại bỏ hay cập nhật nào được phép thực hiện trên sự kiện. Các sự kiện là ngầm có trong CSDL. Đ ịnh nghĩa 2: K h ắ n g định (Com m it) M ột g ia o tác đitợc g ọ i là được khẳng đ ịn h tốt n ếu toàn bộ x â u cá c phép toán tạo nên kết quả tốt của giao tác. Lý do chính của việc không đảm bảo hoàn thành tốt một giao tác là sự vi phạm điều kiện toàn vẹn khi thực hiện các phép toán trong giao tác, hay hư hòng hệ thống, tính toán vô hạn. 3.3. C ơ S Ở D ữ L iỆ U D ự A T R Ê N L O G IC Trong phần này ta đi nghiên cứu CSDL dựa trên logic mà cụ thể là chương trình DATALOG. DATALOG là một ngôn ngữ phi thủ tục dựa trên logic vị từ bậc nhất. Người ta sử dụng để mô tả thông tin cần thiết không theo cách lấy thông tin trong các thủ tục bình thường mà dựa trẽn logic (ngôn ngữ DATALOG). 3 .3 .1 . C ú p h áp í' Ký hiệu: + Vị từ so sánh: 0 (Biến) so sánh với (giá trị) + Cách biểu diễn các luật(Clause - Rule) 133
Q < -P 1 ,P 2 , Pn D ấ u “,” 0 A N D ( a ) Dấu o OR (v) Dấu Kéo theo Pi: là các tiên đề, giả thiết, đích con, vị từ Q: là kết luận hay là sự kiện + Nếu n = 0 : Ọ
+ Luật trên có thể viết được dưới dạng biểu thức tính toán tương đương trên miền xác định và kết quả được bổ sung vào quan hệ suy diễn mới “Ca” {< x, Y> I 3 w , z (W, X, Y, Z) GGửitíền A w = “Hà Nội” A z>1200} Từ đó ta đi đến một sổ công thức sau: 1) Các luật được xây dựng frên các Literal có dạng sau: P(A1, A 2 ,..., An), trong đó: p là tên của quan hệ cơ sở hay quan hệ suy diễn. Mỗi Ai (i = 1, 2,..., n) là hằng số hay tên biến. 2) Một luật trong DATALOG có dạng: P(X1, X 2 ,..., Xn) Q 1(X 11, X I 2 ,..., X lm l), Q 2(X 21, X 2 2 ,...,X 2 m 2 ),..., Qr(Xrl, X r2,..., Xrtnr), e trong đó: + p là tên của quan hệ suy diễn; + Mỗi Qi là tên của quan hệ cơ sở hay quan hệ suy diễn; + e là biểu thức vị từ số học đối với các biến xuất hiện ừong p và tất cả các Qi (mỗi biến xuất hiện ữong p cũng xuất hiện trong Qi nào đó). Literal P(X1, X 2 ,..., Xn) gọi là đầu của luật, phần còn lại gọi là thân của luật. Đ ể hiểu chính xác cách thức diễn giải một iuật ừong Datãiog, người ta xác định khái niệm thay thế luật và hiện trạng của luật. Đ ịnh nghĩa 7: T hay thế luật (Rule Substitution) V iệc thay thế luật được áp dụng cho một luật là việc thay mỗi biến trong luật bằng một biến hay một hằng. Tức là, nểu một biển xuất hiện nhiều iần trong một luật thì phải thạy nó bằng cùng một biển hay cùng một hằng sổ. Ví dụ: Thay thể đối với luật nêu trong ví dụ ừên, biến z được thay bằng w và các biến kia được thay bằng hằng số. Ca(“M ỗ”, 123) < - Gưitiên(“Hà N ội”, 123, “Mỗ”, W), w>1200 Tuy nhiên, nếu thay X bằng hằng số 123 và 333 thì không được Ca(“MỖ”, 123) < - Gưitiên(“Hà N ội”, 333, “Mỗ”, W), w> 1200 => sai Đ ịnh nghĩa 8 ; H iện trạng của luật (Rule instantiation) Hiện trạng của luật là việc thay thể hợp lệ các biến bằng các hằng số. M ột thay thế đúng cho người ta một hiện ừạng của luật. Ví dụ: Ca(“M ỗ”, 123) < - Gưitiên(“Hà N ội”, 123, “Mỗ”, 1500), 1500> 1200 Đ ối với luật cụ thể, có thể có nhiều hiện trạng hợp lệ. Đ ể xem Datalog diễn giải luật ra sao, người ta xét một hiện trạng của luật: P(X1, X 2 ,..., Xn) ^ Q 1(X 11, X 1 2 ,..., X lm l) , Q2(X21, X 2 2 ,..., X 2m 2),..., Qr(Xrl, X r2,..., Xrmr), e p đúng nếu các biểu thức: Q1(C11, C12,..., Clml)AQ2(C21, C22,..., C2m2)A...AQr(Crl, Cr2,..., Crmr)Ae 135
C ó giá trị đúng, Literal Qi(Cil, Ci2,..., Cimi) là đúng nếu n_bộ (Ci 1, C i2,..., Cimi) cỏ mặt trong quan hệ Ọi. Vi dụ: Đối với luật: Ca(Y,X) < - Gửìtiền(“Hà N ội”, X, Y, Z), z>1200 Ca(Y, X) là điing khi có hàng số C1 thoa măn diều kiện sau: c l>1200 n_bộ(“ Hà Nộ^”, 123, “ Mỗ”, C 1 ) có trong quan hệ "Gưitiên". Đ ịnh nghĩa 9: Hệ quản trị CSDL suy diễn (Deductive DBM S) Hệ quản trị CSDL cho phép suy diễn các n_bộ của vị từ theo mục đích bằng bằng cách sử dụng các luật logic. Các chức năng của hệ quản trị CSDL suy diễn được mô tả như sau; CSDL suy diễn được xây dựng dựa trên các quan hệ cơ sở và quan hệ suy diễn. Hệ quản trị CSDL này được gọi là suy diễn bới lẽ nó cho phép suy ra các thông tin từ các dữ liệu đã lưu trữ theo cơ chế suy diễn logic. Các thông tin là các vị từ theo mục đích, các thông tin này có được khi người ta tương tác với vị từ theo mục đích hoặc cập nhật vị từ cơ sở. Đ ịnh nghĩa 10: Câu hỏi Datalog (Datalog Query) Một câu hỏi trong CSDL suy diễn gồm có: • Một chương trình Datalog, tức là một tập hữu hạn, có thể rỗng của các luật; • Một Literal đơn có dạng P(xl,x2,..,xn)? Trong đó xi (i=l,2,..,n) là hằng số hoặc tên biển. Việc khai thác câu hỏi trước tiên là tính chương trình Datalog, nếu có. Tiếp theo P(xl, x2,..., xn) được đánh giá. Thù tục này tương tự như lựa chọn trong quan hệ p theo ràng buộc phù hợp. Vi d ụ 3.2: Tìm tất cả các n_bộ cùa quan hệ vay tại chi nhánh Hà Nội. Khi đó ta có: Vay(“ Hà Nội”, X, Y, Z) Câu hỏi này không có chương trình Datalog. Ví dụ 3.3: Tính tập các khách hàng cùa chi nhánh “ Hà Nội” có tài khoản mà số dư trên 1200. Chương trình Datalog chi có một luật đơn. 136
C(Y) Guitien(“ Hà Nội”, X, Y, Z), z > 1200 C(Y)? Câu C(Y)? là thừa; vì nó chỉ nhằm xác định quan hệ cần thể hiện. Để loại trừ hiện tưọng thừa, người ta có thể dùng kí pháp ngắn gọn, nếu không sợ bị lẫn lộn, nhầm lẫn. Nếu bấy giờ cho câu p (x l, x2,..., xn) và yêu cầu chương trình Datalog bao hàm một luật đon phân biệt là: Hỏi (x l, x2,..., xn) ... Trong đó xi (i = 1 ,2 ,..., n) là tên biến. Điều này hiểu rằng ngưòi ta có câu: H ỏi(xl, x2,..., xn)? Câu này là một phần của câu hỏi. Do vậy, câu hỏi sau là tư ơ n g đưoTig với câu hỏi trên là: Hỏi(Y) 1200 3.3.4, Cấu trúc của câu hỏi Để trình bày cấu trúc của câu hỏi người ta sử dụng đồ thị luật. Đ ịn h n g h ĩa 11: Đ ồ th ị lu ậ t (R u le G ra p h ) M ột đồ thị luậí đối với câu hỏi q là đồ thị có hướng mà: • Các nút của đồ thị ứng với tập các k í hiệu Literal có mặt trong các luật của q. • Cung của đồ thị ứng với quan hệ truYrc giữa Literal trong thân của luật và Literal có mặt trong đầu của ỉuậí đó. Do vậy đồ thị sẽ có cung ữì
Đồ thị trên là đồ thị không có chu trình thưò’ng được gọi là câu hỏi không đệ quy. Ví dụ 3.5: Xét câu hỏi: p l(A , B ,C ) < q l(A . B). P2(B. C) p2(X, Y) ^ q2(X). pl(X . Y .Z ) Hỏi(A, B) pl(A , B ,C ), p2(B. C) Đồ thị ứng vói câu hỏi này là: Đồ thị này là đồ thị có chu trình thường đưọc gọi là câu hỏi đệ qiiy. K ết luận:, + Việc xây dựng cấu trúc của câu hỏi cho phép chúng ta dễ dàng trong việc đánh giá câu hỏi. t Giữa câu hỏi đệ quy và câu hói không đệ quy cũng có nhiều khác nhau ở khỉa cạnh loại hinh câu hói trên CSDl.. Thực tế cho thấv việc đánh giá câu hỏi đệ quy phức tạp hơn đánh giá câu hói thường. 3.3.5. So sánh DATALOG với đại số quan hệ v ề mặt cơ bản ngôn ngữ Datalog với các câu hỏi không đệ quy đưọc xem như tương đương với đại số quan hệ về khả năng thề hiện. Vói các câu hỏi đệ quy cho phép ngưòi ta một công cụ niạiili han các ngôn ngữ quan quan hệ. Điều này ngôn ngữ Datalog cho phép hỏi các câu hói không được phép trong đại sổ quan hệ. ( 1) Phép hợp', ià tập các luật có cùng đầu luật : H ỏ i(X l,X 2 ......Xn)< - r l ( X I . X 2 ........Xn) H o i(Y I,Y 2 ......Yn)< r 2 ( Y I ,Y 2 .......Yn) Vi dụ 3.6\ {\-\) Cliamẹ(.\, > ) < B ố(\, y) (r2) Chamẹ(x, y) < mẹ(x, y) Vi dụ J. 7: Tìm tên của các khách hàng tại chi nhánh “ Hà N ội”, làm như sau: Hỏi(Y)
Chú v\ hai luật thê hiện phép hợp là tách biệt (2) Phép chọn : ứng với một luật mà thân luật có một vị từ so sánh -> biểu thức chọn. Phép chọn chọn các n_bộ trong quan hệ r được viết dưới dạng câu hỏi: r(x l, x 2 ,..., xn)? trong đó: xi (i = 1, 2 ,.... n) là tên biến haỵ một hằng số. Ví dụ 3.8: Chamẹ(x, y) < Chamẹ(x, y ) . V ■ Dĩintỉ - điều này ~ ơv - D (Chamẹ(x, y)) ( phép chọn vói điều kiện là y ^ 'D ũng') iiiig Ví dụ 3.9: Chọn (tim kiếm) tên của những khách hàng vay quá 1000? Hỏi(Y) 1000 (3) Phép chiếu: ià phép toán ứng với một sổ luật mà có một số biến ờ thân luật mà không xuất hiện trong đầu luật. Cha(x) = KỌ(x) C h a m ẹ (x ,y ), y = Dũng (4) Phép kết nốỉ: là phép ứng với luật mà có biến chung ở các vị từ của thân luật. Phép kết nối hai quan hệ rl và r2 được viết dưới dạng Datalog như sau: H ỏi(XI, X 2...... Xn, Y l , Y2,..„ Ym) < rl(X K X 2 ,..„ Xn), r2(YU Y2 Ym) Trong đó; Xi, Yj I i = 1, 2,..., n v à j = 1, 2,..., m là các tên biến phân biệt nhau. Vi dụ 3.J0: (r3) Ôngbà(x, y)
Yêu cầu: 1) Tìm tên của những người làm việc trực tiếp dưới quyền của ông Mỗ, tức phụ ứiuộc mức 1, viết như sau: Hỏi(X) < Quản lý(X, '‘Mỗ” ) — 2) Đe tìm tên cùa những ngưòi làm việc trục tiếp diiới quyền cùa người d Mỗ quản lý, tức phục thuộc mức 2 vào ông Mỗ. viết như sau: Hỏi(X) ^ Quản lý(X, Y). Quản lý(Y, “ Mỗ”) Như vậy, người ta không thể thể hiện yêu cầu tìm người phụ thuộc bậc n vào ông Mỗ trong đại số quan hệ đirọc. Dĩ nhiên câu hỏi tìm tên cua nhân công làm việc dưói quyền của ông Mỗ, trực tiếp hay gián tiếp, không thể tạo đưọc bằng đại sổ quan hệ hay bằng Datalog với các câu hỏi không đệ quy. Nguyên nhân là do người ta không biết ỏng Mỗ quản lý đến mức nào. Tuy nhiên người có thể tạo câu hỏi này trong Datalog dưói dạng câu hỏi đệ quy như sau: e(X) < - Ọuản lỷ(X, “ Mỗ” ) e(X)
e' ^ Ị Hoa, Lan, Mai, Chén, Tích Ị e {Hoa, Lan, Mai, Chén, Tích} C ách a2: Ngoài cách làm như trên người ta có tliế có cách làm khác mà vẫn đạt được kết quả như trên: m(X, Y)
L ư u ý: Dù đã có phương pháp đánh giá tốt hon đánh giá thô, người ta vẫn không đạt được liiệu quả như trong câu hỏi clio cùng kết quả trước đó. CCing có nhiều kĩ thuật đảm bảo làm tinh kĩ thuật nửa thô. 3.3.6. Các hệ C ’ sỏ’ dữ liệu chuyên gia O Qua phần trên, ngưòi ta thấy rằng các luật dựa trên logic có thể tích họp đirọc vào CSDL quan hệ. Các luật như vậy bắt đầu từ các sự kiện trong các n bộ của các bang quan hệ. Các hệ chuyên gia dùng ý này để thực hiện hơn nữa các hoạt động có điều khiển. Định nghĩa: H ệ thống CSD L chuyên gia (Expert Database System) Một hệ thong CSDL chvyérì gia bao gồm C ĨC ìuậi có cỉạnịỉ; "nếu cỏ tập các n hộ nùo đó C irong C SD L thì m ột thù tục đặc biệt chrực khai thác Thủ tục này có thể cập nlĩật CSDL; và câu lệnh IF eủa các luật khác cỏ thề đúng và thù tục khác đưọc thực hiện... Như vậy CSDL loại này gọi là C SD L n ăng động. Cấu trúc của hệ thống CSDL chuyên gia tương tự như cấu trúc cúa hệ chuyên gia trong trí tuệ nhân tạo. Khác nhau chính giữa liai loại hình này là việc sử dụng CSDL hoặc sử dụng bộ nhớ trong, hay bộ nhớ ảo. Theo dạng chuẩn, một hệ thống CSDL chuyên gia gồm CSDL chuẩn và hệ chuyên gia chuấn. Hệ chuyên gia hỏi bằng ngôn ngũ' của CSDL, chẳng hạn như ngôn ngữ SQL và đợi trả lời từ phía CSDL. 3 .4 . M Ộ T S Ó V Á N Đ È K H Á C Ngoài cách tiếp cận về CSDL suy diễn như trén, người ta còn quan tâm đến một số vấn đề về CSDL suy diễn sau: - T h ứ nhất là; những đặc trưng của quá trinh xử Iv câu hỏi, cần thiết mô tả chi tiết hơn về lựa chọn các chiến lược đánh giá câu hỏi đối vói CSDL xác định và các đích xác định. Mặt khác việc xử lý câu hoi trong môi trường song song cùng được quan tâm. - T h ứ hai là: các nghiên cứu hệ thống về các khía cạnh của điều kiện toàn vẹn. cần có sự phân loại chi tiết tuỳ theo bản chất cúa ràng buộc, cách thế hiện của ràng buộc trong công thức logic, và các quan điểm khác nhau về thoả mãn và về kiểm tra toàn vẹn trong CSDL suy diễn. Bên cạnh đó cần cỏ các phương pháp quản lý điều kiện toàn vẹn trong CSDL suy diễn. - T hứ ba là: mẫu hình của hệ thống CSDL suy diền. Đó là một so kiến trúc có tliể chấp nhận đưọc đối vói hệ thống CSDL suy diễn. Khi đã chấp nhận một số kiến trúc nào đó, CSDL suy diễn mẫu sẽ được phát triển trước khi dùng bộ diễn giải Prolog. - Thứ tư là: các CSDL suy diễn song song. Việc giới thiệu một vài kiến trúc song song cùa CSDL suy diễn gồm các thuật toán mô tả chi tiết quá trình xử lý câu hởi. Các câu hỏi được coi là xác định và CSDL suy diễn được xác định tách biệt, tự do về chức năng. Việc đánh giá song song đối với các điều kiện toàn vẹn cũng là quan trọng. 142
- T h ứ năm là: việc hình tlìức hoá các chức năíìii gộp lón và các diì liệu toàn vẹn. T"oim các phần trước diều kiện toàn vẹn chí là tĩnh và không gộp lớn, dùng cho CSDL chuẩn. Khi phát tiẻn CSDL, các điều kiện toàn vẹn cũng đưọc làm phù hợp. Ngưòi ta hình thức hoá các clỉửc năng líộp ión, các điều kiện toàn vẹn và các ràng buộc trên giao tác. Các nội dung trình bày trên mói chi là các hướng sẽ phát triển, làm chi tiết thêm. 143
C H Ư Ơ N G IV CO sở DỬ LIỆU HƯỚNG ĐÓI TƯỢNG Các CSDL quan hệ, theo các bảng chiếm tỷ lệ cao, khoảng 70%, trên thị trường phần mềm ứng dụng. Các dữ liệu được xử lý thuộc loại số, ký tự. Còn lại các dữ liệu phức tạp như vãn bản, đồ hoạ, bản đồ, hinh ảnh, dũ' liệu nhiều chiều và các dữ liệu động như chương trinh, mô phỏng quá trinh... trong CAD, ván phòng học, hệ chuyên gia... thì người ta không chi dùng CSDL quan hệ mà giải quyết được. Mô hình đối tưọng hay mô hình hướng đối tượng rất đa dạng. Nó gồm những mạng ngCr nghĩa và các ngôn ngữ lập trinh hướng đối tượng. Chúng cho phép mô hinh hoá những đối tượng phức tạp có được trong các thú tục xử lý. Dù có nhiều ngôn ngCr hướng đối tượng, đa số CSDL đối tượng dựa trên c + + , lựa chọn này do tính hiệu quả và thông dụng của c++. Các CSDL đối tượng kể ra gồm Ontons năm 1990, Versant nãm 1991, Object Store năm 1991 và CSDL Objectivity năm 1990. Thực tế cho thấy CSDL đổi tượng có các ưu điểm: - Cho phép xét các liên kết đối tưọng dưới dạng các phép lưu trữ vói các đối tượng; - Các đối tượng dùng chung giữa nhiều ngưòi sử dụng; - Khả năng phát triển kho tri thức bằng cách thêm các đối tượng mới và các phép xử lý kèm theo; - Phát triển hệ quản trị CSDL dựa trên việc xử lý các đối tượng phức tạp, giao diện chương trinh, đối tượng động và trừu tượng. 4.1. N G U Y Ê N T Ắ C C Ủ A C Á C M Ô H ÌN H H Ư Ớ N G Đ Ó I T Ư Ợ N G 4 .1 .1 . M ô h ìn h h ỏa các đ ố i tư ọ tig + Đối tượng (Object): Là tập hợp các phần tử của các dữ liệu có cấu trúc, tham chiếu duy nhất qua tên. Vi dụ: Có thể lấy ví dụ minh hoạ về đối tưọng như; một con người, ngưởi có các dữ liệu mô tả chi tiết về họ tên và thông tin về con cái, là con người khác. Đối tượng là một máy bay, gồm các thông số bay, tổ lái, kĩ thuật. Để thể hiện các đối tượng, người ta dùng cách viết như trong ngôn ngữ c++, trong đó một nhóm các thuộc tính được xác định sau tên của đối tượng được đặt trong dấu ngoặc nhọn; các thuộc tính tách nhau bằng dấu phẩy. Ví dụ'. Ngưòi 1{Họ: Nguyễn, Tên: Tèo, Tiioi;25, Địa chỉ: Hà Nội} Một đối tượng có thể đơn giản hoặc gộp cùa tên và một giá trị, như số nguyên NI {Giá trị: 25}, tuy vậy chúng có thể phức tạp và chứa cả các đổi tượng khác, như máy bay có 2 môtơ, 4 cách,... 145
Để làm việc được với đối tượng cần phải biết thêm một số khái niệm sau: Tên của đối tượng; Sự tham chiếu chung. + Định tên của đối tưọng Mỗi đối tượng có một tên. Hai đối íưọng tuy cỏ cùng giá trị nhưng có hai ten khác nhau sẽ được xem như hai đối tượng khác nhau. Một đối tượng cỏ thể thay đối giá trị, nhưng không thể đổi tên. Định nghĩa: Định tên đối tượng (O bject Identifier) Tham chiểu m ột cách duy nhất g ắ n với đ ỗ i tư ợ n g từ k h i tạo ra nó, cho p h é p ch ỉ định đối tượng. Trong CSDL HĐT, tẻn đối tượng xác định đối tượng, tên khác nhau chỉ các đối tượng khác nhau. Nhin lại dữ liệu quan hệ, mỗi n_bộ xác định qua giá trị của n bộ, nay dùng tên, cho phép xác định không chỉ giá trị, mà còn tính chất của đối tượng, dùng để phân biệt logic và vật lý với các đối tượng khác. - Hai đối tượng là trùng nhau ( 0 1 ^ 0 2 ) nếu chúng trùng tên. - Hai đối tuựng là bằng nhau ( 0 1 “- 0 2 ) khi chủng có cùng giá trị; Do vậy nếu 01 ^ 0 2 thì 0 1 ^ 0 2 , ngược lại không đúng. + Thâm chiếu chung Tên của đối tượng là phưoTig tiện thuận lợi c h o việc mô hình h o á c á c đối tượng phức tạp. Cụ thể một đối tượng có thể tham ch iếu đen đối tượng khác. Ví dy: Đối tưọng Người tham chiếu đến đối tưọng Xe mà họ sò‘ hữu. Tuy nlìiẽn cỏ thể nhiều người chung chiếc xe đó. Người 1{Tên: Tèo, Xe: X I } Người2{Tên;Tâm , X e :X l} + Thuộc tính(Attribute) Tính chất của đối tưọng được gán tên; cho phép timng ứng vcV một giá trị hay một tham i chiếu đến đối tượng khác. 4 .1 .2 . P h ư ơ n g p h á p Mô hinh đối tượng đà thể hiện cấu trúc tĩnh, cho phép mô hinh hoá các đối tượng và các liên kết giữa các đối tượng. Mặt khác mô hinh đối tượhg còn thế hiện khía cạnh động, cho phép quản lý cấu trúc cúa các đối tưọĩig theo clìửc năng, còn được gọi là phưong pháp. Định nghĩa: Thủ tục đặc tm n g hởi tên đầu thù tục, các tham số gọi và tham số trả về dùng để áp lên một đối tuợng có tên. 4 .1 .3 , L ó p ( C la s s ) Lớp là khuôn mau cho phép xác định tập các ĩinh chai ciia đối tượng, n h ư các thvộc tính và các phư ơng pháp, và tạo nên các đối tượng marìg cúc tính chấí đỏ. 146
Ví dụ: Xác định lớp Người và Xe (cú pháp được chọn để mô tà lớp là cú pháp cúa ngôn ngCr C í“+), người ta dùng ký pháp * để tham chiếu đến loại dCr liệu khác. Có hai phưong pháp gắn vói đối tượng N gưòi là Già - đi,cho phép tăng tuồi hàng năm cho mỗi đối tượng người và cho kết quả là tuổi mới nhận, và Lái cho biểt việc thay đối xe liên quan đến đối tu’ ’ng: Q Class Người { String họ; String tên; Int tuổi; Xe * ôtô; Int Già_đi(); Void Lái (Xe); }; Class Xe{ String số; Chế tạo *Mác; String Loại; Máy *Môtơ; }; 4 .1 .4 . C á c liê n k ế t th ừ a k ế g iữ a cá c ló p + Tống q u át hoá Liêrì kết p h á n cấp giữ a các lớp cho phép xá c địỉih ìĩhững đối tượng cùa lớp ữ ên là tổng quát hơìĩ các đối tưọTìg cua lớp dưới. Lóp thấp gọi là lóp con. Lớp trên gọi là lớp cha. 4- Thừa kế (Inheritance) Việc chuyến tự động các tỉnh chẩt của m ột ỉởp, cho các lớp con. Tất cả các phần tử của lớp con là phần tử CLÌa lớp cha thi chúng kế thừa các tính chất cùa lóp cha. Mặc dù được thừa kế các tính chất từ lóp cha, lớp con còn có các tính chất khác nỉiư các phương pháp và thuộc tính bổ sung. Ví dự. Lớp người có hai lóp con là : Người có việc và ngirời thất việc Class Có việc: Người { Char Nghề [12]; Thành phố Nơi làm; Double Lương; Double Thưòng; Void Làm việcO; }; 147
4.1.5. Lược đồ lớp MÔ tả một CSDL hirỚTỉg đối tượng gom các lớp, các thuộc íhih V Ị các phinrng pháp, C cũng như các ỉiêrì kết tông quát hoá giĩta các ìớp. 4.2. T ÍN H B È N V Ũ ÌV G C Ủ A C Á C Đ Ố I T Ư Ợ N G 4 .2 .1 . C ơ s ở d ữ liệ u h ư ở n g đ ố i t ư ợ n g Những khái niệm trên đây mới cho phép mô hình hoá các đối tưọng. Một khái niệm về CSDL được bổ sung trong phần này là tính bền vCrng. Đe đánh giá một hệ quản trị CSDL đối tượng, trước hết hệ thống phai cỏ các chức năng của một hệ quản trị CSDL. Ngoài ra nó còn đảm bảo một số tính chất như dirói đây. + Tính bền vững của các đối tượng: Các đối tượng cần nằm chắc chắn trên phương tiện nhớ như đĩa từ, khi đưọc một chương trình tạo ra. • Đối tượng bền vững: là đối tượng được lưu gÌLĩ trong CSDL. có thời gian tồn tại dài hơn thời gian của chương trinh tạo ra đối tượng đó. • Đối tượng tạm thòi: là đối tượng được lưu trong bộ nhớ trong; do vậy thòi hạn tồn tại của nó không quá thời hạn của chương trình tạo ra đối tượng đó. + Tính khai thác tương tranh: CSDL đối tượng cho phép các giao tác dùng chung. Việc khoá giao tác, khoá dữ liệu cần hạn chế để đảm báo tính tương hợp về dữ liệu. + Tính tin cậy của đối tưọng Những đối tượng cỏ thể khôi phục lại khi c 6 sai sót xày ra. Các giao tác cần chia nhỏ để đảm bảo hoặc chúng được thực hiện hoàn toàn, hoặc không thực hiện tí gì. + Tính tiện lợi t r a cứu Người ta yêu cầu tìm được các đối tượng theo giá trịcủa thuộc tính đối tượng. Do vậy cần quản lý tận giá trị thuộc tính, các kết quà của phương pháp, các liênhệ giữa các đối tượng. + Chức năng khác • Phân bố các đối tưọng; • Những mô hinh về các giao tác; • Những thế hệ của các đối tượng. 4.2.2. Q u ả n lý tín h bền vŨTig Một mô hình CSDL đối tượng cho phép xác định các loại dữ liệu của đối tượng. Trong mỏi trường lập trình, các đối tượng cần được xây dựng và bị huỷ bò trong bộ nhớ nhờ các chức năng đặc biệt, gọi là bộ tạo dạng và bộ huỷ bỏ. + T ạo d ự n g đối tượng: chức năng gẩn với một lớp cho phép tạo nên và khởi động một đối tượng trong bộ nhớ. 148