BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI DE -Đào Văn Tâm TRUY VẤN CƠ SỞ DỮ LIỆU HƯỚNG ĐỐI TƯỢNG SỬ DỤNG BIỂU THỨC ĐƯỜNG DẪN CHUYÊN NGHÀNH : CÔNG NGHỆ THÔNG TIN LUẬN VĂN THẠC SĨ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TS NGUYỄN KIM ANH HÀ NỘI – Năm 2010 MỤC LỤC LỜI CÁM ƠN LỜI CAM ĐOAN Danh mục ký hiệu, chữ viết tắt .6 Danh mục hình vẽ MỞ ĐẦU Chương – TỔNG QUAN CƠ SỞ DỮ LIỆU HƯỚNG ĐỐI TƯỢNG 10 1.1 Cơ sở liệu hướng đối tượng 12 1.2 Khái niệm sở liệu hướng đối tượng 13 1.2.1 Định danh đối tượng 14 1.2.2 Thuộc tính đối tượng 15 1.2.3 Trạng thái đối tượng 15 1.2.4 Hành vi đối tượng 16 1.2.5 Lớp đối tượng 16 1.2.6 Đóng gói liệu 16 1.2.7 Thừa kế 17 1.2.8 Đa hình 18 1.2.9 Đối tượng phức hợp 18 1.3 Hệ quản trị sở liệu hướng đối tượng 22 1.3.1 Hệ quản trị OODB 22 1.3.2 Vấn đề toàn vẹn cho OODB 23 Chương – XỬ LÝ TRUY VẤN TRONG HỆ CƠ SỞ DỮ LIỆU HƯỚNG ĐỐI TƯỢNG 26 2.1 Các vấn đề liên quan đến truy vấn sở liệu hướng đối tượng 26 2.2 Quá trình xử lý truy vấn 28 -2- 2.2.1 Phương pháp xử lý truy vấn 29 2.2.2 Tối ưu hóa truy vấn 30 2.3 Kỹ thuật tối ưu hóa 35 2.3.1 Các vấn đề tối ưu hóa đại số 35 2.3.2 Tối ưu hóa biểu thức đường dẫn 41 Chương – KỸ THUẬT XỬ LÝ TRUY VẤN LỒNG NHAU 46 3.1 Truy vấn biểu thức đường dẫn lồng 46 3.2 Các loại truy vấn 47 3.2.1 Truy vấn đơn giản 48 3.2.2 Truy vấn lồng 49 3.2.1 Truy vấn tương quan 49 3.3 Kỹ thuật xử lý truy vấn lồng 50 3.3.1 Mô hình hệ thống 50 3.3.2 Đồ thị truy vấn 51 3.3.2.1 Định nghĩa 51 3.3.2.2 Chuyển đổi đồ thị truy vấn 56 3.4 Kỹ thuật Access Support Relations (ASRs) 59 3.4.1 Các toán tử thao tác ASRs 59 3.4.2 Sơ đồ thực thi chung 61 Chương - KẾT QUẢ VÀ HƯỚNG PHÁT TRIỂN 63 TÀI LIỆU THAM KHẢO 64 PHỤ LỤC 65 -3- LỜI CÁM ƠN Lời luận văn xin gửi lời cảm ơn chân thành đến cô giáo, PGS.TS Nguyễn Kim Anh người trực tiếp hướng dẫn, giúp đỡ tạo điều kiện thuận lợi cho từ lúc tìm hiểu, định hướng tìm kiếm tài liệu để hoàn thành luận văn tốt nghiệp Tôi xin gửi lời cám ơn tới thầy, cô giáo Viện Công nghệ thông tin Truyền thông - Trường Đại học Bách khoa Hà Nội trang bị cho kiến thức quý báu suốt trình học tập trường Tôi xin gửi lời cám ơn tới Viện đào tạo Sau đại học - Trường Đại học Bách khoa Hà nội tạo điều kiện giúp đỡ thời gian học tập nghiên cứu Cuối cùng, muốn nói lời cám ơn tới gia đình, người thân, bạn bè đồng nghiệp Trường Đại học Công Nghiệp Hà Nội nơi công tác bên cạnh động viên, khích lệ suốt trình nghiên cứu hoàn thành luận văn Hà Nội, ngày 28 tháng 10 năm 2010 -4- LỜI CAM ĐOAN Tôi xin cam đoan công trình nghiên cứu riêng Các số liệu, kết nêu luận văn trung thực chưa công bố công trình khác Tác giả luận văn -5- Danh mục ký hiệu, chữ viết tắt STT Từ viết tắt ODBMS OODB OODBMS Viết đủ Ý nghĩa Object Database Management Hệ quản trị sở liệu Systems đối tượng Object Oriented Database Cơ sở liệu hướng đối tượng Object-Oriented Database Hệ quản trị sở liệu Management Systems hướng đối tượng OID Object Identifier Định danh đối tượng OO Object Oriented Hướng đối tượng DBMS Database Management Systems Hệ quản trị sở liệu OQL Object Query Language CSDL Cơ sở liệu Ngôn ngữ truy vấn đối tượng Cơ sở liệu -6- Danh mục hình vẽ Hình 1.1 Các thành phần CSDL hướng đối tượng 12 Hình 1.2 Ví dụ complex object 19 Hình 2.1 Phương pháp xử lý đối tượng truy vấn 29 Hình 2.2 Phân vùng không gian tìm kiếm vào vùng 33 Hình 2.3 Tối ưu hóa phần hệ thống loại 34 Hình 2.4 Tối ưu hóa biểu thức đường dẫn 43 Hình 3.1 Lược đồ sở liệu Employee 48 Hình 3.2 Kiến trúc xử lý truy vấn 51 Hình 3.3 Ví dụ đại điện đồ họa Navigation-Link 53 Hình 3.4 Đại điện đồ họa e.Supervisor = d.Manager 54 -7- MỞ ĐẦU Các mô hình liệu hệ sở liệu (CSDL) truyền thống, quan hệ, mạng phân cấp, vốn thành công việc vận hành, phát triển hệ thống thông tin chương trìn phần mềm ứng dụng Tuy nhiên với phát triển nhanh chóng Công nghệ thông tin, CSDL quan hệ dần bộc lộ yếu điểm nhiều hạn chế, đặc biệt việc xây dựng ứng dụng có liệu phức tạp, liệu đa chiều, kiểu liệu để lưu hình ảnh, văn lớn, âm thanh, video, CSDL hướng đối tượng giải pháp cho vấn đề Trong CSDL hướng đối tượng, liệu lưu trữ dạng đối tượng ngôn ngữ lập trình nên cho phép lưu trữ dạng liệu phức tạp, lượng thông tin lớn, đa chiều, âm thanh, video Các liệu không lưu trữ đơn thuần, mà hành vi đối tượng liệu lưu trữ CSDL Trong năm qua có số nghiên cứu quan trọng việc xác định định hướng mô hình, đối tượng truy vấn bao gồm tính toán , đại số, ngôn ngữ người dùng Một chức hệ thống quản lý sở liệu để xử lý truy vấn người dùng khai báo Một số truy vấn biểu thức đường dẫn yêu cầu giá trị có sở liệu lấy sau sử dụng điều kiện so sánh, truy vấn thường hình thành cách sử dụng truy vấn lồng nhau, truy vấn lồng đơn giản hóa truy vấn sở liệu cho người dùng Sau nghiên cứu số tài liệu liên quan tới vấn đề xử lý truy vấn, truy vấn lồng sở liệu hướng đối tượng, đồng ý, động viên cô giáo hướng dẫn khoa học chọn đề tài “Truy vấn sở liệu hướng đối tượng sử dụng biểu thức đường dẫn” để nghiên cứu luận văn tốt nghiệp Mục đích luận văn nghiên cứu xử lý truy vấn biểu thức đường dẫn sở liệu hướng đối tượng kỹ thuật xử lý truy vấn lồng -8- Việc tổ đồ án thực sau Chương trình bày khái niệm sở liệu hướng đối tượng hệ sở liệu hướng đối tượng, Chương trình bày xử lý truy vấn biểu thức đường dẫn sở liệu hướng phương pháp xử lý truy vấn Chương trình bày kỹ thuật xử lý truy vấn cho truy vấn lồng sở liệu hướng đối tượng cuối Chương kết luận với số ý kiến, công việc đạt hướng nghiên cứu -9- Chương – TỔNG QUAN CƠ SỞ DỮ LIỆU HƯỚNG ĐỐI TƯỢNG Các mô hình liệu hệ cở sở liệu (CSDL) truyền thống, quan hệ, mạng phân cấp, vốn thành công việc phát triển kỹ thuật CSDL cấn thiết cho nhiều ứng dụng CSDL kinh doanh Tuy nhiên chúng có khiếm khuyết định phải thiết kế thực CSDL phức hợp hơn, ví dụ CSDL dùng thiết kế sản xuất công nghiệp (CAD/CAM CIM2), thí nghiệm khoa học, viễn thông, hệ đồ địa lý đa phương tiện Các ứng dụng mẻ có yêu cầu đặc tính khác với ứng dụng kinh doanh truyền thống, cấu trúc phức hợp đối tượng, thời gian giao dịch lâu hơn, kiểu liệu để lưu hình ảnh văn lớn nhu cầu định nghĩa xử lý đặc trưng ứng dụng CSDL hướng đối tượng xem phù hợp với đòi hỏi ứng dụng Việc tiếp cận hướng đối tượng tạo tính linh động để xử lý số yêu cầu mà không bị hạn chế kiểu liệu ngôn ngữ truy vấn có sẵn hệ CSDL truyền thống Tính then chốt CSDL hướng đối tượng lực mà chúng trao cho nhà thiết kế để cấu trúc đối tượng phức hợp thao tác áp dụng lên đối tượng Một nguyên nhân khác đời CSDL hướng đối tượng việc vận dụng ngày nhiều ngôn ngữ lập trình hướng đối tượng để xây dựng ứng dụng phần mềm Ngày CSDL trở thành thành phần hệ thống phần mềm khó sử dụng CSDL truyền thống để nhúng ứng dụng phần mềm hướng đối tượng xây dựng ngôn ngữ lập trình hướng đối tượng C++, SMALLTALK hay JAVA Object-Oriented Database (OODB) thiết kế để tích hợp trực tiếp với phần mềm xây dựng ngôn ngữ lập trình hướng đối tượng - 10 - Hình 3.2 Mô hình hệ thống xử lý truy vấn 3.3.2 Đồ thị truy vấn Đồ thị truy vấn đại diện biểu thức truy vấn Đồ thị truy vấn phân cấp, phù hợp với đặc tính phân cấp cho đặc tính lồng truy vấn OQL 3.3.2.1 Định nghĩa Định nghĩa Một đồ thị truy vấn G đồ thị bao gồm nút N, Liên kết L Nó thể G = [N, L] Định nghĩa Các nút N chia thành ba loại Bao gồm Simple-Node NS, Collection-Node NC, Path Node NP Định nghĩa Simple-Node NS nút nguyên thủy mà chia thành nút khác Nó sử dụng để đại diện cho biến thuộc tính nút trung gian biểu thức đường dẫn (thuộc tính dây chuyền) Nó bao gồm ba yếu tố: Var, Type, Filter Var tên biến Type loại tương ứng biến Filter vị từ ngược lại nút NS biểu diễn [Var, Type, Filter] - 51 - Các loại Simple-Node không Literal int, char, float, ,vv Simple-Node sử dụng để đại diện cho thuộc tính phức tạp thuộc tính chữ.Ví dụ, e.Name = "John" thể sau: NS(e) = [e, Employee, Name= "John"], Định nghĩa Collection-Node NC chia thành đồ thị truy vấn Gsub sau toán tử project(toán tử project tương tự mô hình quan hệ) áp dụng cho đồ thị Các projection-list danh sách thuộc tính projected ProjectO từ đồ thị Gsub Một collection node NC ký hiệu [Var, Type, Filter] nơi mà Type Project(Gsub, projection list) Các kiểu trả nút bag tập đối tượng Trong hệ thống phân cấp loại chống lại ODMG mô hình,bag set kiểu phụ loại cấu trúc đối tượng Thực với persistence class quản lý đối tượng để lưu kết truy vấn trung gian Định nghĩa Các Path Node NP không khai triển sử dụng để đại diện cho tập thuộc tính tương ứng với biến khai báo lượng hóa phổ dụng lượng hóa tồn Một Path Node ký hiệu NP =[Var, Path, Filter] Định nghĩa Các liên kết L chia thành năm loại Gồm Navigation-Link Ln , Join-Link Lj, All-Link Lall, Exist-Link Lext In-Link Lin Định nghĩa Các Navigation-Link Ln hướng liên kết nguyên thủy mà phân tách Nó có ba yếu tố, hai nút kết nối liên kết, tương ứng với thuộc tính Ln biểu diễn [(N1, N2) , Attrihute] Ln sử dụng để đại diện cho biểu thức đường dẫn Ví dụ, e.Workon liên kết nguyên thủy nối hai nút Employee Project Các biểu thức đường dẫn xây dựng sau NS(e) = [e, Employee, null], Ln(workon) = [(Ns(e), Ns(p)) , Workon], - 52 - Ns(p) = [p, Project, null], Các đại diện đồ họa Navigation-Link phác thảo hình Hình 3.3 Ví dụ đại điện đồ họa Navigation-Link Định nghĩa Các Join-Link Lj liên kết vô hướng nguyên thủy Nó kết nối hai nút cách sử dụng thuộc tính join JoinAttr Các đối tượng hai nút join oids họ giá trị thuộc tính họ Lj biểu diễn [N1, N2, JoinAttr] Nếu JoinAttr null, có nghĩa loại hai nút loại nguyên thủy Lj sử dụng để xác định điều kiện join truy vấn Ví dụ, điều kiện join Q1:e.Supervisor = d.Manager xây dựng cách sử dụng chuỗi simple nodes navigational links cuối join Lj (xem bên dưới) NS(e) = [e, Employee, Name= "John"], Ln(supervisor) = [(Ns(e), Ns(e’)) , Supervisor], Ns(e) = [e’, Employee, null], Ns(d) = [d, Department, null], Ln(manager) = [(Ns(d), Ns(d’)) , Manager], Ns(d’) = [d’, Employee, null], Lj(supervisor,manager) = [(Ns(e’), Ns(d’)) , null], Các đại diện đồ họa biểu thức thể hình 3.4 - 53 - Hình 3.4 Đại điện đồ họa e.Supervisor = d.Manager Định nghĩa Các All-Link Lall liên kết có hướng phân tách Nó tương đương với đồ thị truy vấn Gsub chứa Path-Node Cả nút nối Lall phải loại Lall biểu diễn [(N1, N2), Gsub], nơi Gsub xây dựng Path-Node Lall sử dụng để đại diện cho lượng hóa phổ dụng Ví dụ, vị từ Q3 mệnh đề where "for all x in e.Workon: x.Contorlled.Location=Taipei" Chúng ta xem lọc biến e bên có điều kiện lọc x.Controlled.Location = "Taipei" Các vị từ mệnh đề where Q3 xây dựng sau : NS(e) = [e, Employee, null], Lall = [(Ns(e), Ns(e’)) , Gsub], Ns(e’) = [e’, Employee, null], Gsub = [ Np(x) = [x, e.Workon, null], Ln(controller) = [(Np(x), Ns(controlled)) , Controlled], Ns(d) = [d, Department, Location=”Taipei”], ] Các đại diện đồ họa biểu thức vẽ hình 3.5 - 54 - Hình 3.5 Đại điện đồ họa Q3 Định nghĩa 10 Exist-Link Lext tương tự All-Link ngoại trừ lượng hóa Exist() Định nghĩa 11 In-Link Lin liên kết trực tiếp nguyên thủy In-Link Lin biểu diễn [( N1, N2 )] N1 N2 hai đồ thị truy vấn Sau minh họa cách sử dụng truy vấn sau Q5 Q5: “Lấy tên nhân viên có giám sát supervisee người quản lý phận Taipei” select e.Name from e in Employee, d in Department where e.supervisor in d.Manager.Supervisee and d.Location = "Taipei" Các vị từ mệnh đề where xây dựng cách sử dụng biểu thức sau đây: Ns(e) = [e, Employee, null], Ln(supervisor) = [(Ns(e), Ns(supervisor)) , Supervisor], Ns(e’) = [e’, Employee, null], Ns(d) = [d, Department, Location=”Taipei”], Ln(manager) = [(Ns(d), Ns(e’’)) , Manager], Ns(e’’) = [e’’, Employee, null], Ln(supervisee) = [(Ns(e’’), Ns(ee)) , Supervisee], Ns(ee) = [ee, Employee, null], - 55 - Lin(supervisor, supervisee) = [(Ns(e’), Ns(ee))], Các đại diện đồ họa biểu thức vẽ hình 3.6 Hình 3.6 Đại điện đồ họa Q4 3.3.2.2 Chuyển đổi đồ thị truy vấn Trong phần này, đề xuất thuật toán để chuyển biểu thức truy vấn vào đồ thị truy vấn Truy vấn thể OQL Ý tưởng chuyển đổi dựa vào cấu trúc lưu trữ nội bộ, Access Support Relation Có đồ thể đường dẫn truy vấn đến cấu trúc lưu trữ ASR Một biểu thức đường dẫn đến kết hợp Simple-Nodes Navigate-Links Một đường định thứ tự thực hướng Mỗi cấu trúc đồ thị truy vấn ánh xạ đến chuỗi toán tử Simple-Node ánh xạ vào trạng thái trung gian ASRs, Navigate-Link ánh xạ đền toán tử navigate, Join-Link ánh xạ đền toán tử join, điều kiện lọc ánh xạ đến toán tử select, projection list ánh xạ đến toán tử - 56 - project Ưu điểm thiết kế dễ dàng để dịch đồ thị truy vấn để thực thi sơ đồ Thuật toán chuyển đổi : Biến non-literal thuộc tính non-literal biểu thức đường dẫn chuyển thành Simple-Node Ns.Tên nút giống hệt biến Nếu tên biến, hệ thống định tên để nút tự động Hai thuộc tính non-literal biểu thức đường dẫn cấu trúc Navigation-Link Ln Điều kiện join mệnh đề lượng hóa cấu trúc Join-Link Kết việc đánh giá from -where bag tập đối tượng Nó đại diện Collection-Node Nc Mệnh đề select sau yêu cầu thuộc tính giá trị projects Mệnh đề lượng hóa chuyển thành hình thức phân ly bình thường, nghĩa là, (query and query and ) (query and query and ) Mỗi biểu thức cặp dấu ngoặc đơn xây dựng Collection-Node CollectionNode kết hợp toán tử union sau sản xuất CollectionNode Một mệnh đề có chứa cho tất lượng hóa phổ biến thành All-Link Lall Một mệnh đề có chứa có định lượng phổ biến thành Exist-Link Lext Một mệnh đề có chứa lượng hóa biến đổi thành In-Link Lin Đồ thị truy vấn QG1 QG3 bắt nguồn từ truy vấn Q1 Q3a tương ứng cách áp dụng thuật toán chuyển đổi trên.Các đồ thị truy vấn hiển thị hình 7a 7b, tương ứng - 57 - Hình 3.7a Đồ thị truy vấn QG1 Hình 3.7b Đồ thị truy vấn QG3a - 58 - 3.4 Kỹ thuật Access Support Relations (ASRs) Kỹ thuật Access Support Relations (ASRs) đề xuất Kemper Moerkotte ASRs giới thiệu phương tiện để tối ưu hóa xử lý truy vấn hệ thống sở liệu hướng đối tượng Theo định nghĩa [9] Một biểu thức đường dẫn có dạng : o.A1 An, o cấu trúc tuple đối tượng có chứa thuộc tính A, o.A1 An đề cập đến đối tượng tập đối tượng Kết biểu thức đường dẫn tập hợp đối tượng (hoặc giá trị) loại đạt từ o thông qua chuỗi thuộc tính xác định 3.4.1 Các toán tử thao tác ASRs Định nghĩa tập hợp toán tử để thao tác ASRs việc xử lý truy vấn Các toán tử mô tả Toán tử I/O • NewAsr : Đây toán tử sử dụng để tạo chuẩn mở rộng ASRs (ký hiệu ASRcan) Điều mở rộng kinh điển khởi tạo cách điền vào mức độ lớp định Định dạng toán tử ASRcan = NewAsr(initial class) • SetAttrToAsr : Toán tử tạo mở rộng kinh điển ASRcan1để lưu trữ oid oi.A, mà oi đối tượng quy định ASRcan [S0, ,Si, ,Sn] A tập thuộc tính oi Định dạng toán tử ASRcan1 = SetAttrToASR(ASRcan, oi.A) nơi ASRcan1 ASR tạm thời • AsrToCIs : Đây toán tử save [S0, ,Sn]can để lớp tạm thời qua quản lý đối tượng Các [S0, ,Sn]can hình thức thể lớp mà thuộc tính đặc điểm kỹ thuật định S0, ,Sn Các định dạng toán tử temporal class ==AsrToCls(ASRcan) - 59 - Các toán tử • Select : Toán tử select sử dụng để chọn tập hợp liệu ASR đáp ứng điều kiện lựa chọn Định dạng toán tử sau: ASRcan = Select(ASRcan , selection condition), [S0, ,Sn]can = δ( [S0, ,Sn]can) • Navigate: Nếu biểu thức đường dẫn [tn-1.An] đường dẫn biểu thức đường dẫn [t0.A1…An] có tồn mở rộng kinh điển ARScan[S0,…,Sn1]can Ngoài ra, miền tn-1 giống Sn-1 Toán tử mở rộng lý thuyết ASRcan[S0,…,Sn-1]can để ASRcan[S0,…,Sn-1, Sn]can, nơi mà Sn miền thuộc tính An Định dạng toán tử sau ASRcan2 = Navigate(ASRcan1 , tn-1.An), [S0,…,Sn]can2 = Vtn-1.An ([S0, ,Sn-1]canl ) • Join : Toán tử sử dụng để nối hai ASRs theo điều kiện join Định dạng toán tử sau : ASRcan3=Join(ASRcan1, ASRcan2, join condition), Hoặc [S0,…,S2n+1]can3 = [S0,…,Sn]can1 [S0,…,Sn]can2 • Union: Toán tử sử dụng để kết hợp hai ASRs có lĩnh vực phù hợp Định dạng toán tử sau : ASRcan3=Union(ASRcan1, ASRcan2 ), Hoặc [S0,…,Sn]can3 = [S0,…,Sn]can1 [S0,…,Sn]can2 • Difference : Toán tử sử dụng để khác biệt hai ASRs có lĩnh vực phù hợp Định dạng toán tử sau : ASRcan3= Difference (ASRcan1, ASRcan2 ), Hoặc [S0,…,Sn]can3 = [S0,…,Sn]can1 - [S0,…,Sn]can2 - 60 - • Project : Toán tử select lựa chọn số cột từ ASR quy định loại bỏ cột khác Định dạng toán tử : ASRcan2= Project (ASRcan, projection-list), Hoặc [S0,…,Si]can2 = Π([S0,…,Sn]can) (0 ≤ i ≤ n) nơi project-list danh sách thuộc tính ASRcan quy định Các toán tử mở rộng • All: Toán tử sử dụng để thực All-Link • Exist: Tương tự vậy, toán tử sử dụng để thực Exist-Link 3.4.2 Sơ đồ thực thi chung Sơ đồ thực thi chung trình ánh xạ đồ thị truy vấn tới tập hợp toán tử xác định phần trước Một ví dụ để minh họa cho sơ đồ thực thi chung Xem xét đồ thị truy vấn thể hình 3.7 cho Query Các sơ đồ thực thi thể sau Bước 1: asrl = NewAsr ("Employee"); Bước 2: asr2= Navigate(asr1, e.Supervisor); Bước 3: asr3= NewAsr("Department"); Bước 4: Select(asr3, d.Location= "Taipei"); Bước 5: asr4= Navigate(asr3, d.Manager); Bước 6: asr5=Join(asr2, asr4, tmpVarl= tmpvar2); Bước 7: asr6= Project(asr5, e.Name); Bước 8: TmpClsl= AsrToCls(asr6); - 61 - Trong chương này, trình bày kỹ thuật xử lý truy vấn lồng sở liệu hướng đối tượng Truy vấn lồng thể OQL khai báo ngôn ngữ định nghĩa ODMG-93 Một truy vấn chuyển thành đồ thị truy vấn cách sử dụng thuật toán chuyển đổi biểu đồ Đã định nghĩa tập hợp toán tử để thao tác ASRs việc xử lý truy vấn - 62 - Chương - KẾT QUẢ VÀ HƯỚNG PHÁT TRIỂN Đánh giá ưu điểm hạn chế luận văn: Luận văn trình bày cách có hệ thống kiến thức liên quan đến vấn đề truy vấn sở liệu sử dụng biểu thức đường dẫn , tập trung nghiên cứu sâu vấn đề xử lý truy vấn sở liệu hướng đối tượng nói chung xử lý truy vấn sử dụng biểu thức đường dẫn nói riêng vấn đề truy vấn biểu thức đường dẫn lồng sở liệu hướng đối tượng Bên cạnh đó, trình bày kỹ thuật Access Support Relations (ASRs) để đại diện thao tác biểu thức đường dẫn Một truy vấn chuyển đổi thành đồ thị truy vấn cách sử dụng thuật toán chuyển đổi biểu đồ Tuy nhiên luận văn dừng lại mức nghiên cứu lý thuyết Hướng phát triển luận văn: - Lượng hóa biểu thức đường dẫn - Kỹ thuật tối ưu hóa lập mục kỹ thuật tối ưu hóa dựa mô hình chi phí sở - 63 - TÀI LIỆU THAM KHẢO Michael Kifer, Won Kim, Yehoshua Sagiv (1992), “Querying object-oriented databases”, pp 6-11 Jeonghee Kim, Taisook Han, Kyu-young Whang (1999), “Visualization of Path Expressions in a Virtual Object-Oriented Database Query Language” R Elmasri and S B Navati, Addison Wesley (2003), “Fundamental of Database Systems – 4th Edition”, chapter 21 Đ.T Nhân, N.T.N Mai, N.T.K Trang (2007), “Lý thuyết sở liệu 2” M Tamer Özsu, José A Blakeley (1994), “Query Processing in ObjectOriented Database Systems”,pp.3-12 “Nested Query Processing Techniques in Object-oriented Databases” Straube D , and OZSU M (1990), “Queries and query processing in object oriented database systems”, pp387–430 Ioannidis Y, and Cha Kang Y (1990), “Randomized algorithms for optimizing large join queries”,pp312–321 - 64 - PHỤ LỤC - 65 - ... quan tới vấn đề xử lý truy vấn, truy vấn lồng sở liệu hướng đối tượng, đồng ý, động viên cô giáo hướng dẫn khoa học chọn đề tài Truy vấn sở liệu hướng đối tượng sử dụng biểu thức đường dẫn để... xử lý truy vấn biểu thức đường dẫn sở liệu hướng đối tượng kỹ thuật xử lý truy vấn lồng -8- Việc tổ đồ án thực sau Chương trình bày khái niệm sở liệu hướng đối tượng hệ sở liệu hướng đối tượng, ... CSDL hướng đối tượng - 11 - 1.1 Cơ sở liệu hướng đối tượng Cơ sở liệu hướng đối tượng (Object – Oriented Database) kiểu CSDL, mà liệu lưu trữ dạng đối tượng Hay Cơ sở liệu hướng đối tượng xây