Phương pháp ước lượng các truy vấn lồng trong cơ sở dữ liệu hướng đối tượng bằng siêu đồ thị kết nối

Abstract: The basic various of the relational databases for data types, the presentation of complex objetcs, class hierarchy, methods in object-oriented databases which query processing and the optimizing query become more difficult. However, one of the methods query processing for the relational databases can be inheritance and advanced for the optimizing query in object-oriented databases. In this paper, we propose a method for estimating the object- oriented query that extended from the algorithms of Ullman [7] and Han [3] by connection hypergraphs for the nested queries. I. GIỚI THIỆU Một trong lĩnh vực quan trọng được đề cập trong CSDL hướng đối tượng là tối ưu hoá truy vấn hướng đối tượng. Khi thực thi một truy vấn, có thể có nhiều phương án mà hệ thống CSDL cho phép xử lý và sản sinh câu trả lời. Các phương án có kết quả cuối cùng là tương đương về kết quả tính toán nhưng khác nhau trong chi phí thực hiện, tức là tổng thời gian cần để thực hiện một truy vấn. Lựa chọn phương án nào để có tổng thời gian thực hiện là nhỏ nhất? Như vậy, vấn đề tối ưu hoá truy vấn là cấp thiết trong các hệ thống quản trị CSDL. Trong những năm gần đây vấn đề tối ưu hoá truy vấn hướng đối tượng được nhiều nhà nghiên cứu quan tâm, các kỹ thuật tối ưu hoá truy vấn được phát triển có tính kế thừa từ mô hình CSDL quan hệ như tối ưu hoá trên các biểu thức đại số [4] và các giải thuật chuyển đổi truy vấn hướng đối tượng sang truy vấn quan hệ để áp dụng các kỹ thuật tối ưu hoá truy vấn đã có trên mô hình quan hệ [8]. Tuy nhiên, vấn đề tối ưu hoá truy vấn trên CSDL hướng đối tượng có những điểm khác biệt so với các phương pháp tối ưu hoá truy vấn trên CSDL quan hệ – điều này xuất phát từ ngữ nghĩa của mô hình dữ liệu hướng đối tượng và các ngôn ngữ truy vấn trên mô hình này, vì vậy cần phải nghiên cứu các phương pháp, đề xuất các kỹ thuật tối ưu hoá truy vấn phù hợp cho các truy vấn hướng đối tượng. Tối ưu hóa các truy vấn lồng trong CSDL hướng đối tượng đã được Cluet, S. [2] đề xuất theo cách tiếp cận 2 giai đoạn trong ngữ cảnh hướng đối tượng. Giai đoạn đầu tiên được gọi là tối ưu hóa trên cơ sở phụ thuộc: biến đổi các truy vấn ở mức ngôn ngữ nhằm thực hiện các biểu thức con chung và các truy vấn con độc lập một cách hiệu quả hơn. Các truy vấn đã biến đổi được biên dịch thành các biểu thức đại số lồng nhau. Sự định giá các vòng lặp lồng nhau có thể không hiệu quả. Vì vậy, ở giai đoạn 2 là giai đoạn “làm phẳng” các biểu thức đại số lồng nhau giúp cho phép định giá hiệu quả hơn. Trong bài báo này, chúng tôi đề xuất cách tiếp cận bằng phương pháp biểu diễn các truy vấn lồng bằng siêu đồ thị kết nối, sau đó thực hiện tiến trình ước lượng các siêu cạnh trên siêu đồ thị kết nối của truy vấn lồng. Xuất phát từ ý tưởng biểu diễn và tối ưu hóa các truy vấn (ngôn ngữ Phương pháp ước lượng các truy vấn lồng trong cơ sở dữ liệu hướng đối tượng bằng siêu đồ thị kết nối The Method for Estimating the Nested Queries in Object-Oriented Databases by Connection Hypergraphs Lê Mạnh Thạnh, Đoàn Văn Ban, Hoàng Bảo Hùng QUEL/SQL) bằng siêu đồ thị của J.D Ullman [7] và Han [3], chúng tôi mở rộng phương pháp biểu diễn này trong ngôn ngữ truy vấn OQL trên CSDL hướng đối tượng. II. BIỂU DIỄN TRUY VẤN OQL BẰNG SIÊU ĐỒ THỊ KẾT NỐI Các truy vấn được viết bằng ngôn ngữ truy vấn OQL (ODMG-93) [5, 6] rất phong phú và đa dạng, trong bài báo này chúng tôi chỉ biểu diễn cho một tập con của các truy vấn viết bằng ngôn ngữ OQL: các truy vấn lồng. Ví dụ 1: Để thống nhất trong trình bày một số ví dụ, chúng ta sử dụng CSDL nhân sự minh hoạ như sau [4, 9]: class NHAN_SU type tuple (maso: integer, hoten: string, pho: string[20], tpho: string[10], matinh: integer, ngaysinh: tuple (ngay: integer, thang: integer, nam:integer)) class SINH_VIEN inherits NHAN_SU type tuple (gvhd: string, dtb: float, hocbong: float, tenkhoa: KHOA) class GIANG_VIEN inherits NHAN_SU type tuple ( bomon: string[20], mabomon: integer, chucvu: string[20], tenkhoa: KHOA, luong: integer, con: set(NHAN_SU)) class KHOA type tuple (makhoa: integer, tenkh: string, diadiem: string, ngansach: float, GIANG_VIEN: set(GIANG_VIEN)) 1. Siêu đồ thị kết nối Chúng ta nhắc lại định nghĩa của một siêu đồ thị. Một siêu đồ thị H = (V, E) chứa một tập các đỉnh V và tập các siêu cạnh E. Trong đó, tập đỉnh V tương ứng với tập các mục dữ liệu (thuộc tính), và mỗi siêu cạnh e ∈ E tương ứng với một tập các mục dữ liệu có liên quan với nhau (lớp, điều kiện). Siêu đồ thị là sự mở rộng của một đồ thị mà mỗi siêu cạnh của nó được kết nối từ tập các đỉnh. Trong bài báo này, chúng ta giới thiệu khái niệm siêu đồ thị kết nối biểu diễn cho câu truy vấn lồng trong CSDL hướng đối tượng, là một sự mở rộng phương pháp biểu diễn siêu đồ thị đối với các thành phần của câu truy vấn lồng. Trước hết, chúng ta xét biểu thức điều kiện trong mệnh đề Where, các biểu thức điều kiện được chia ra bốn dạng sau: A = a, (1) A = B (2) A θ B, θ ∈ { , ≥}, (3) A θ B, θ ∈ {⊂ , ⊆ , ≠ , ⊃ , ⊇}. (4) trong đó, A, B là thuộc tính của các lớp và a là hằng. Truy vấn OQL đơn chỉ có một khối Select...From...Where (SFW); Truy vấn OQL lồng có nhiều hơn 1 khối SFW. Mỗi khối SFW được biểu diễn bằng siêu đồ thị kết nối như sau: − Đồ thị có các cạnh là các tập với số lượng nút hữu hạn, ta gọi một cạnh như vậy là siêu cạnh. Siêu đồ thị này được gọi là siêu đồ thị kết nối, mỗi thuộc tính của lớp Ci được biểu thị bằng một nút. Nếu hai lớp Ci và Cj đều có cùng một số các thuộc tính kế thừa từ một siêu lớp nào đó, hoặc chúng cùng kế thừa tất cả các thuộc tính từ một siêu lớp, chúng ta vẫn tạo riêng cho các thuộc tính này các nút khác nhau. − Các siêu cạnh của siêu đồ thị kết nối được tạo thành từ các biểu thức điều kiện và các lớp Ci như sau: Đối với mỗi lớp Ci , có một siêu cạnh chứa tất cả các nút là các thuộc tính của Ci , ta gọi là siêu cạnh đối tượng và được vẽ bằng 1 đường khép kín bao quanh tất cả các nút của siêu cạnh. Đối với mỗi biểu thức điều kiện dạng (3) hoặc (4), chúng ta sẽ tạo ra một siêu cạnh chứa tất cả các thuộc tính có mặt trong biểu thức. Những siêu cạnh này được gọi là siêu cạnh điều kiện và chúng được biểu thị bằng đường nét chấm khép kín. Điều kiện có dạng (1) trong siêu đồ thị, được gán nhãn nút là “A = a”. Biểu thức điều kiện có dạng A = B (dạng (2)), với A, B là các thuộc tính trong hai lớp (có thể cùng là những thuộc tính được kế thừa từ một siêu lớp nào đó), thì chúng ta “trộn” các nút A và B lại với nhau đặt nhãn chung là tên của một trong hai thuộc tính. Các thuộc tính trong mệnh đề Select được bao trong một đường khép kín và gán nhãn là “head”, gọi là siêu cạnh đỉnh. Siêu cạnh đỉnh tương ứng với một lớp - kết quả của truy vấn. Nếu có hai điều kiện trên cùng một tập thuộc tính hoặc một điều kiện trên một tập thuộc tính của một lớp, chúng ta phải đặt tên cho mỗi siêu cạnh để có thể phân biệt được chúng. Một lớp trong CDSL hướng đối tượng hoặc lớp kết quả thu được từ mệnh đề Select được biểu diễn bằng một siêu cạnh đối tượng hay siêu cạnh đỉnh tương ứng. − Siêu cạnh kết hợp được vẽ bằng đường nét rời khép kín bao các thuộc tính có liên quan. Các siêu cạnh kết hợp được gán nhãn là IS, IN, UNION, FORALL, EXIST,...vv. Truy vấn lồng OQL được kết nối từ các siêu đồ thị của các khối SFW bởi các siêu cạnh kết hợp. 2. Biểu diễn kết nối trong OQL Phép kết nối trong ngôn ngữ truy vấn CSDL hướng đối tượng OQL được biểu diễn bằng 3 dạng thức kết nối là kết nối hàm (hay kết nối ẩn dùng ký hiệu “.”); kết nối đồng nhất tường minh (các thực thể được so sánh với nhau một cách trực tiếp) và kết nối quan hệ truyền thống là kết nối dựa vào giá trị. Ví dụ 2: (kết nối hàm) Xét truy vấn tìm tên các khoa của các trường Đại học ở thành phố “Hà Nội” select (e.tenkhoa.tenkh) from GIANG_VIEN as e where e.tpho = “Ha Noi” Truy vấn trên được viết lại như sau: define KHOA as d select (tenkhoa.tenkh) from GIANG_VIEN as e where e.tpho = “Ha Noi” AND e.tenkhoa IS (d) Trong đó, giá trị của thuộc tính tham chiếu e.tenkhoa được so sánh trực tiếp bằng toán tử IS với biến vùng d. Toán tử IS được dùng để so sánh các tham chiếu, nó trả về giá trị là true nếu hai tham chiếu trỏ đến cùng một đối tượng. Toán tử ISNOT được sử dụng để kiểm tra hai tham chiếu không quy về cùng một đối tượng. Thuộc tính tenkhoa là thuộc tính có kiểu KHOA, phép kết nối hàm được biểu diễn bằng một siêu cạnh kết hợp (IS). Truy vấn trên được biểu diễn bằng siêu đồ thị kết nối như sau: Hình 1. Siêu đồ thị kết nối của ví dụ 2 Ví dụ 3: (kết nối dựa vào giá trị) Tìm tên của tất cả các hộ sống trong cùng thành phố với sinh viên có tên là “Nga”. define SINH_VIEN as p1 select (p1.hoten) from p1, p2 in (SINH_VIEN union GIANG_VIEN) where p1.tpho = p2.tpho AND p2.hoten = “Nga” Truy vấn trên có một kết nối dựa vào giá trị (p1.tpho = p2.tpho) và được biểu diễn bằng việc trộn hai nút p1.tpho, p2.tpho lại với nhau và đặt tên nhãn là tpho như hình 2. KHOA tenkh ....... ‘ = “Ha Noi” ‘ tenkhoa tpho ............ GIANG_VIEN hoten head IS Hình 2. Siêu đồ thị kết nối của ví dụ 3 3. Biểu diễn các truy vấn lồng bằng siêu đồ thị kết nối Ví dụ 4: Xét truy vấn select e1.hoten from GIANG_VIEN as e1 where bomon =”Lap trinh” and (luong > ( select AVG(e2.luong) from GIANG_VIEN as e2 where e2.makhoa = e1.makhoa)) Trước tiên, chúng ta biểu diễn hai siêu đồ thị kết nối (a), (b) cho hai khối SFW trong câu truy vấn ở ví dụ 4, sau đó thực hiện việc trộn hai siêu đồ thị kết nối vào siêu đồ thị kết quả (c) bằng phép kết nối e2.makhoa = e1.makhoa và các biểu thức điều kiện tương ứng. Ví dụ 5: Xét truy vấn cho biết tên các CBGV ở khoa có ngân sách được cấp lớn hơn 250 (đơn vị tính: triệu đồng) và có mức lương lớn hơn hoặc bằng 2.4. select e.hoten from GIANG_VIEN as e where e.luong >= 2.4 AND e.makhoa IN ( select s.makhoa from KHOA as s where s.ngansach > 250) Truy vấn được biểu diễn bằng siêu đồ thị kết nối như sau: Các siêu cạnh đối tượng biểu diễn các lớp GIANG_VIEN và KHOA. Đối với các siêu cạnh đỉnh, chúng ta có 2 siêu cạnh đỉnh: e.hoten- siêu cạnh đỉnh (kết quả của truy vấn), s.makhoa - siêu cạnh đỉnh của khối SFW lồng. Hai siêu cạnh điều kiện e.luong >= 2.4, s.ngansach > 250 và siêu cạnh kết hợp e.makhoa được gán nhãn là IN. Hình 4. Biểu diễn siêu đồ thị kết nối của ví dụ 5 III. PHƯƠNG PHÁP ƯỚC LƯỢNG CÁC TRUY VẤN LỒNG BẰNG SIÊU ĐỒ THỊ KẾT NỐI 1. Ước lượng các siêu cạnh trong siêu đồ thị kết nối Định nghĩa: Lớp cơ sở là một lớp được lưu trữ trong CSDL hướng đối tượng. Lớp dẫn xuất là lớp trung gian được sản sinh trong quá trình ước lượng truy vấn và được sử dụng như là đầu vào trong các bước ước lượng sau. Chúng ta biểu diễn hình thức cho siêu đồ thị kết nối của truy vấn hướng đối tượng là dãy các maso hoten ...... bomon GIANG_VIEN ‘= “Lap trinh” ‘ head maso hoten Avg (luong) ......... head (b) (a) ‘= “Lap trinh” ‘ con hoten luong maso tenkhoa bomon con maso bomon (luong ) hoten GIANG_VIEN GIANG_VIEN head Avg > (c) GIANG_VIEN Hình 3. Biểu diễn siêu đồ thị kết nối của ví dụ 4 hoten makhoa luong ...... makhoa tenkh ngansach >250 ........ >= 2.4 head IN GIANG_VIEN KHOA hoten tpho ............. GIANG_VIEN SINH_VIEN ........... hoten ‘ “Nga” = ‘ head (a) (b) sự kiện: S = (E1, E2 , ..., En), trong đó, các sự kiện Ei có thể là siêu cạnh đối tượng, siêu cạnh điều kiện hoặc siêu cạnh kết hợp. Lớp dẫn xuất thu được sau tác động của một sự kiện Ej được ký hiệu là TRAN(E1, ..., Ej), trong đó E1 phải là siêu cạnh đối tượng (trường hợp siêu đồ thị kết nối chỉ có 1 siêu cạnh thì đó phải là siêu cạnh đối tượng). Thủ tục được giới thiệu sau đây thực hiện việc ước lượng lớp dẫn xuất với sự kiện Ej trong S. Thủ tục nhận tham số vào là lớp dẫn xuất thu được sau khi thực hiện sự kiện Ej-1 và sự kiện Ej, kết quả trả về của thủ tục là lớp dẫn xuất sau tác động của Ej. Procedure EVAL(TRAN(E1, ..., Ej-1), Ej) {với tham số vào TRAN(E1, ..., Ej-1), Ej và kết quả là TRAN(E1, ..., Ej)} Begin (1) Khởi tạo, EVAL(E1) cho kết quả: TRAN(E1) = C1, trong đó C1 tương ứng với siêu cạnh đối tượng E1. (2) If (Ej là một điều kiện hoặc siêu cạnh điều kiện) then TRAN(E1, ..., Ej) = σF(TRAN(E1, ..., Ej-1)) {F là biểu thức điều kiện}. (3) If (Ej là siêu cạnh đối tượng đối với lớp Cj có giao với siêu đồ thị kết nối) then TRAN(E1, ..., Ej) = TRAN(E1, ..., Ej-1)) Cj (4) If (Ej là siêu cạnh đối tượng không giao với siêu đồ thị) then TRAN(E1, ..., Ej) = TRAN(E1, ..., Ej-1)) × Cj End; Xét ở ví dụ 2, ta có S = (GIANG_VIEN, KHOA), thì TRAN(GIANG_VIEN, KHOA) = TRAN(GIANG_VIEN)× KHOA. Trong ví dụ 3, S = (GIANG_VIEN, SINH_VIEN), TRAN(GIANG_VIEN, SINH_VIEN) = TRAN(GIANG_VIEN) SINH_VIEN. Khi tất cả các siêu cạnh, điều kiện cùng được ước lượng bằng cách thực hiện các phép toán đối tượng tương ứng, ta chiếu lớp dẫn xuất lên các thuộc tính đặc trưng (các thuộc tính tham gia ở mệnh đề Select - các nút ở siêu cạnh đỉnh), thu được lớp kết quả (siêu cạnh đỉnh) - Đây chính là câu trả lời của truy vấn. Từ đó, ta có giải thuật ước lượng các siêu cạnh trong siêu đồ thị kết nối như sau: Giải thuật: Input: Siêu đồ thị kết nối S = (E1, E2, ..., En) Output: Các lớp dẫn xuất. Method (1) Biểu diễn siêu đồ thị kết nối với dãy S = (E1, E2, ..., En); (2) for j = 1 to n do (3) Call EVAL(TRAN(E1, ..., Ej-1), Ej); (4) Chiếu TRAN(E1, ..., En) lên trên các thuộc tính đặc trưng. 2. Các quy tắc ước lượng các siêu cạnh trong siêu đồ thị kết nối dựa trên các phép toán chọn và chiếu Trong tiến trình thực hiện truy vấn, việc đưa phép chọn và phép chiếu lên trước các phép kết nối và tích đề các được thực hiện càng sớm càng tốt (nếu có thể). Phép chọn thực hiện việc loại bỏ các đối tượng không liên quan trong các lớp, làm giảm không gian tìm kiếm; phép chiếu loại bỏ các thuộc tính không có mặt trong kết quả truy vấn, hoặc không phải là các thuộc tính kết nối, làm giảm đáng kể kích thước các lớp trong tham gia kết nối, tích đề các. Vì vậy, việc áp dụng các quy tắc hueristic trong ước lượng siêu đồ thị kết nối trên các siêu cạnh điều kiện đối với các phép toán chọn, chiếu được phát biểu như sau: (Q1) Sử dụng một ràng buộc (điều kiện có kiểu A = a, A > a, ... hoặc một tập hạn chế các giá trị của một thuộc tính) để truy vấn trên một lớp (nếu có thể). (Q2) Ước lượng một điều kiện hoặc một siêu cạnh điều kiện càng sớm càng tốt nếu như có thể. (Q3) Sau khi một siêu cạnh đã được đánh dấu, chiếu loại bỏ các thuộc tính không liên quan từ lớp suy dẫn. IV. KẾT LUẬN Với phạm vi trong bài báo này, chúng tôi tập trung nghiên cứu mở rộng phương pháp biểu diễn câu truy vấn lồng trong CSDL hướng đối tượng (với ngôn ngữ truy vấn OQL) bằng siêu đồ thị kết nối và trình bày giải thuật ước lượng các siêu cạnh trong siêu đồ thị kết nối nêu trên. Phương pháp ước lượng này chưa phải là thuật toán tối ưu truy vấn lồng bằng siêu đồ thị kết nối trên CSDL hướng đối tượng. Hướng nghiên cứu tiếp theo của chúng tôi là giải thuật tối ưu hoá truy vấn lồng trên siêu đồ thị kết nối. TÀI LIỆU THAM KHẢO [1] Đoàn Văn Ban, Lê Mạnh Thạnh và Hoàng Bảo Hùng, Sự tương đương trong biểu diễn giữa ngôn ngữ truy vấn OQL và đại số đối tượng, Tạp chí Tin học và Điều khiển học, Viện Khoa học và Công nghệ Việt Nam, Tập số 20, số 3, 2004, p. 257- 269. [2] Cluet, Sophie and Moerkotte, Guido, Nested Queries In Object Bases, In Fifth International Workshop on Database Programming Languages, Gubbio, Italy, September, 1995. [3] Han, Jia Liang, Optimizing Relational Queries in Connection Hypergraphs: Nested Queries, Views, and Binding Propagations, The VLDB Journal, Springer Verlag, 1998. [4] Lê Mạnh Thạnh, Hoàng Bảo Hùng, Ngôn ngữ truy vấn hướng đối tượng và tối ưu hoá truy vấn trên CSDL hướng đối tượng bằng phương pháp biến đổi đại số, Hội nghị khoa học kỷ niệm 25 năm thành lập Viện Công nghệ thông tin, Hà nội, 12/2001. [5] Trigoni, Agathoniki, Semantic Optimization of OQL Queries, Technical Report,Number 547, University of Cambridge, Computer Laboratory, UCAM-CL-TR-547, ISSN 1476-2986, October, 2002. [6] Trigoni A. and Bierman G.M., Inferring the Principal Type and the Schema Requirements of an OQL Query. In 18th British National Conference on Databases (BNCOD), pp.185–201, 2001. [7] Ullman, Jeffrey D. , Principles of Database and Knowledge-Base Systems, Vol I, II, Computer Science Press, Rockville, 1989. [8] Vanderberg, Scott Lee, Algebras For Object-Oriented Query Languages, A thesis submitted in partial fulfilment of the requirements for the degree of Doctor of Philosophy (Computer Sciences), at the University of Winconsin-Madison, 1993. [9] Yu, Clement T., Meng, Weiyi, Principles of Database Query Processing for Advanced Applications, Morgan Kaufmann Publishers, Inc. San Francisco, California, 1998. Ngày nhận bài 30/8/2004 SƠ LƯỢC TÁC GIẢ LÊ MẠNH THẠNH Sinh ngày 1/6/1953 tại Quảng Trị. Tốt nghiệp Đại học Bách khoa Hà Nội chuyên ngành Toán công trình năm 1977, bảo vệ luận án Tiến sỹ tại Hungari, chuyên ngành Đảm bảo toán học cho máy tính năm 1993. Hiện là Hiệu trưởng trường Đại học Khoa học Huế. Hướng nghiên cứu: cơ sở dữ liệu suy dẫn và cơ sở dữ liệu hướng đối tượng. Email: lmt.hue@dng.vnn.vn ĐOÀN VĂN BAN Sinh ngày 18/02/1949 tại Nam Định. Tốt nghiệp Đại học Tổng hợp Warszawa năm 1975. Bảo vệ luận án tiến sỹ tại Đại học Tổng hợp Warszawa năm 1978. Hiện đang công tác tại Viện Công nghệ thông tin Hướng nghiên cứu hiện nay: Mô hình hoá các hệ thống thông tin sử dụng ngôn ngữ UML trong phân tích, thiết kế hệ thống hướng đối tượng. Email: dvban@ioit.ncst.ac.vn HOÀNG BẢO HÙNG Sinh ngày 23/10/1971 tại Huế. Tốt nghiệp Đại học Sư phạm Huế chuyên ngành Toán học năm 1993, tốt nghiệp Đại học Bách khoa Hà Nội chuyên ngành Tin học năm 1995, tốt nghiệp Thạc sĩ tại Đại học Bách khoa Hà Nội, chuyên ngành Công nghệ thông tin năm 2002, hiện đang là nghiên cứu sinh của Viện Công nghệ thông tin. Hiện đang công tác tại Trường Cao đẳng Sư phạm Thừa Thiên Huế. Hướng nghiên cứu: CSDL hướng đối tượng. Email: hbhung@hueuni.edu.vn