Luận văn Thạc sĩ Công nghệ thông tin: Tối ưu hóa truy vấn cơ sở dữ liệu hướng đối tượng

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

Thêm vào BST

Báo xấu

29
lượt xem 6
download

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

Mục tiêu nghiên cứu của đề tài là các mô hình CSDL hướng đối tượng để giải bài toán tối ưu hóa truy vấn đối tượng. Đây là vấn đề luôn được các nhà khoa học quan tâm nghiên cứu. Trong khuôn khổ của luận văn, tôi tập trung nghiên cứu vào phương pháp tối ưu hóa truy vấn mà hay được sử dụng nhất đặc biệt là đối với các truy vấn lồng đó là sử dụng phương pháp siêu đồ thị. Nghiên cứu các đặc trưng trong mô hình dữ liệu hướng đối tượng; Tìm hiểu các kỹ thuật xử lý truy vấn, sự biểu diễn câu truy vấn bằng ngôn ngữ truy vấn đối tượng OQL; Giới thiệu ký pháp siêu đồ thị [10] trong biểu diễn truy vấn. Từ đó, sử dụng phương pháp này để tối ưu hóa truy vấn cho lớp các truy vấn lồng trong CSDL hướng đối tượng [3].

Chủ đề:

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

Lưu

Nội dung Text: Luận văn Thạc sĩ Công nghệ thông tin: Tối ưu hóa truy vấn cơ sở dữ liệu hướng đối tượng

1 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ PHẠM THỊ CHANH TỐI ƢU HÓA TRUY VẤN CƠ SỞ DỮ LIỆU HƢỚNG ĐỐI TƢỢNG LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN HÀ NỘI – 2014.
2 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ PHẠM THỊ CHANH TỐI ƢU HÓA TRUY VẤN CƠ SỞ DỮ LIỆU HƢỚNG ĐỐI TƢỢNG Ngành: CÔNG NGHỆ THÔNG TIN Chuyên ngành : HỆ THỐNG THÔNG TIN Mã số: 60480104 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC : PGS. TS. ĐOÀN VĂN BAN HÀ NỘI – 2014
3 LỜI CAM ĐOAN Tôi xin cam đoan, kết quả của luận văn hoàn toàn là kết quả của tự bản thân tôi tìm hiểu, nghiên cứu. Các tài liệu tham khảo đƣợc trích dẫn và chú thích đầy đủ. Tác giả Phạm Thị Chanh
4 LỜI CẢM ƠN Lời đầu tiên của luận văn em xin gửi lời cảm ơn chân thành nhất đến PGS.TS Đoàn Văn Ban, ngƣời đã trực tiếp hƣớng dẫn, giúp đỡ và tạo mọi điều kiện thuận lợi cho em từ lúc tìm hiểu, định hƣớng cũng nhƣ tìm kiếm tài liệu trong lĩnh vực cơ sở dữ liệu hƣớng đối tƣợng cho đến lúc hoàn thành luận văn. Em xin gửi lời cám ơn sâu sắc đến tất cả các thầy cô giáo đã dạy dỗ và truyền đạt những kinh nghiệm quý báu cho chúng em trong suốt hai năm cao học ở trƣờng Đại học Công nghệ - Đại học Quốc gia Hà nội. Cuối cùng, em xin biểu thị sự biết ơn tới những ngƣời thân trong gia đình và bạn bè đã ƣu ái, giúp đỡ, động viên, khích lệ để em hoàn thành luận văn này. Hà nội, ngày ….., tháng ….., năm 2014
5 DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT CÁC KÝ HIỆU STT Ký hiệu Diễn giải 1 Att (Attribute) Thuộc tính 2 R Tập thuộc tính trong mệnh đề Select 3 E Siêu cạnh 4 Oid OID của đối tƣợng 5 O (Object) Tập các đối tƣợng 6 V (Value) Giá trị 7 D Tập các đối tƣợng 8 H (HyperGraph) Siêu đồ thị 9 Mid (Method Identify) Định danh phƣơng thức 10 Odb (Object database) Cơ sở dữ liệu đối tƣợng 11 Dom (Domain) Miền trị 12 Obj (Object) Đối tƣợng 13 Val (Value) Giá trị 14 Sup (Super) Siêu lớp/ lớp cha 15 Meth (Method) Phƣơng thức 16 Attrs (Attributes) Tập thuộc tính CÁC CHỮ VIẾT TẮT STT Ký hiệu Diễn giải 1 CSDL Cơ sở dữ liệu 2 OID (Object Identifier) Định danh đối tƣợng 3 UML (Unified Modeling Language) Ngôn ngữ mô hình hợp nhất 4 ODMG Nhóm quản trị CSDL đối tƣợng (Object Database Management Group) 5 ODL(Object Definition Language) Ngôn ngữ định nghĩa đối tƣợng 6 OQL (Object Query Language) Ngôn ngữ truy vấn đối tƣợng 7 OODB(Object-Oriented Database) CSDL Hƣớng đối tƣợng 8 OODBMS (Object-Oriented Database Hệ quản trị CSDL Hƣớng đối tƣợng Management System) 9 ADTs (Abtract Data Types) Tập kiểu dữ liệu trừu tƣợng 10 SFW (Select...From...Where) Khối lệnh trọng tâm của ngôn ngữ truy vấn OQL
6 DANH MỤC CÁC THUẬT NGỮ Biến thể hiện dựa trên giá trị Value based instance variable Biến thể hiện lớp Class instance varSSiable Đối tƣợng phức hợp Composite object Kiểu đặc trƣng Specific types Kiểu dữ liệu “túi”, đa tập là kiểu sƣu tập Bag Kiểu tổng quát General types Lƣợc đồ đối tƣợng Object schemas Mối quan hệ kế thừa Inheritance relationship Mối quan hệ kết nhập Aggregation relationship Phân cấp lớp Class hierarchy Phân cấp lớp hợp thành Class composition hierarchy Phƣơng thức nạp chồng Overloading method Phƣơng thức thuộc tính - suy dẫn Derived-attribute method Siêu lớp Metaclass/Superclass Lớp con Subclass Truy vấn lồng Nested query Mô hình dữ liệu hƣớng đối tƣợng Object-Oriented Model Thực thể Entity Viết đè Overriding Liên kết muộn Late binding Thuộc tính đơn Single attribute Thuộc tính đơn trị Single-valued attribute Thuộc tính đa trị Multivalued attribute Thuộc tính phức hợp Composite attribute Tính đa hình Polymorphism Tính đóng gói thông tin Encapsulation Tính kế thừa bội Multiple inheritance
7 DANH MỤC CÁC HÌNH VẼ Hình 1.1. Sự phát triển của các mô hình dữ liệu ........................................................ 4 Hình 1.2. Mô hình dữ liệu hƣớng đối tƣợng nguyên mẫu .......................................... 6 Hình 1.3. Kế thừa đơn................................................................................................. 14 Hình 1.4. Kế thừa bội từ hai lớp khác nhau và có lớp cơ sở chung ........................... 14 Hình 1.5. Kế thừa bội không có lớp cơ sở chung ....................................................... 15 Hình 1.6. Sự phân cấp các kiểu trong OQL ................................................................ 20 Hình 1.7. Lƣợc đồ CSDL Quản lý Nhân viên ............................................................ 21 Hình 2.1. Siêu đồ thị H ............................................................................................... 28 Hình 2.2. Siêu đồ thị kết nối đối tƣợng của ví dụ 2.1 ................................................. 30 Hình 2.3. Siêu đồ thị kết nối của ví dụ 2.2 ................................................................. 34 Hình 2.4. Siêu đồ thị kết nối của ví dụ 2.3 ................................................................. 35 Hình 2.5. Siêu đồ thị kết nối của ví dụ 2.4. ................................................................ 36 Hình 3.1. Lƣợc đồ CSDL Quản lý Nhân sự ............................................................... 52 Hình 3.2. Form luận văn ............................................................................................. 61 Hình 3.3. Kết quả truy vấn 1 ....................................................................................... 62 Hình 3.4. Kết quả truy vấn 2 ....................................................................................... 63 Hình 3.5. Kết quả truy vấn 3 ....................................................................................... 65
8 DANH MỤC CÁC BẢNG, BIỂU ĐỒ Bảng 2.1. Kết quả ƣớc lƣợng siêu cạnh của ví dụ 2.3 ................................................ 44 Bảng 2.2. Kết quả ƣớc lƣợng khi áp dụng thuật toán 2.5 Tinh chỉnh siêu đồ thị của ví dụ 2.3 .......................................................................................................................... 46 Bảng 2.3. Kết quả ƣớc lƣợng siêu cạnh của ví dụ 2.4 ................................................ 46 Bảng 2.4. Kết quả ƣớc lƣợng khi áp dụng thuật toán 2.5 Tinh chỉnh siêu đồ thị của ví dụ 2.4 .......................................................................................................................... 47 Biều đồ 3.1. So sánh thời gian thực hiện truy vấn 1 ................................................... 62 Biều đồ 3.2. So sánh thời gian thực hiện truy vấn 2 ................................................... 64 Biều đồ 3.3. So sánh thời gian thực hiện truy vấn 3 ................................................... 65
9 LỜI MỞ ĐẦU Chúng ta đang sống trong một thời đại mới, thời đại của Công nghệ thông tin (CNTT). Công nghệ thông tin ngày một phát triển và trở thành một nhu cầu không thể thiếu trong mọi lĩnh vực của đời sống xã hội. CNTT là ngành quản lý công nghệ và mở ra nhiều lĩnh vực khác nhau nhƣ phần mềm máy tính, phần cứng máy tính, ngôn ngữ lập trình, ….Và cơ sở dữ liệu cũng là một lĩnh vực quan trọng của Công nghệ thông tin. Từ khi ra đời cho đến nay, những nghiên cứu về Cơ sở dữ liệu (CSDL) đã không ngừng phát triển và ngày càng trở nên cần thiết trong các ứng dụng về CNTT. CSDL đã trở thành một bộ phận chủ yếu không thể thiếu trong hầu hết các hệ thống thông tin. Hiện nay, các hệ thống thông tin hay các CSDL đều chủ yếu sử dụng một kiểu CSDL truyền thống đó là CSDL quan hệ, một trong những CSDL đã đƣợc phát triển và ứng dụng rộng rãi. Tuy nhiên với sự phát triển nhanh chóng của CNTT, CSDL quan hệ đã dần bộc lộ những yếu điểm và nhiều hạn chế, đặc biệt là trong việc xây dựng các ứng dụng cơ dữ liệu phức tạp, dữ liệu đa chiều, dữ liệu có nhiều mối quan hệ, hay các dữ liệu đa phƣơng tiện nhƣ: hình ảnh, âm thanh, video,… Ngày nay, phƣơng pháp hƣớng đối tƣợng đƣợc sử dụng rất phổ biến trong lĩnh vực phát triển phần mềm, vì cho phép lập trình viên tạo ra các đối tƣợng trong code trừu tƣợng hóa các đối tƣợng thực tế trong cuộc sống. Trong thế giới thực, đối tƣợng là thực thể tồn tại nhƣ con ngƣời, xe, máy tính,…Trong ngôn ngữ lập trình, đối tƣợng có thể là màn hình, điều khiển,…Kỹ thuật hƣớng đối tƣợng là kỹ thuật nhằm vào sự tƣơng tác giữa các đối tƣợng. Mỗi đối tƣợng có những thuộc tính (thông tin lƣu trữ), những phƣơng thức xác định các chức năng của đối tƣợng và các đối tƣợng chỉ đƣợc tạo ra và tồn tại trên bộ nhớ chính, còn việc lƣu trữ và tƣơng tác dữ liệu dƣới dạng các đối tƣợng trên bộ nhớ thứ cấp vẫn chủ yếu kế thừa từ mô hình quan hệ truyền thống. Hiện đã có rất nhiều kết quả nghiên cứu, cho phép chuyển đổi qua lại giữa các bảng trong mô hình quan hệ sang tập các đối tƣợng tƣơng ứng. Mặc dù kế thừa đƣợc tính năng mạnh của hƣớng đối tƣợng, nhƣng việc chuyển đổi qua lại này càng làm cho mã lệnh của chƣơng trình phức tạp thêm, đồng thời hiệu suất chƣơng trình cũng giảm đi rõ rệt. CSDL hƣớng đối tƣợng là giải pháp cho những hạn chế của CSDL quan hệ. Trong CSDL hƣớng đối tƣợng, dữ liệu đƣợc lƣu trữ dƣới dạng các đối tƣợng của ngôn ngữ lập trình nên cho phép lƣu trữ đƣợc các dạng dữ liệu phức tạp, lƣợng thông tin lớn, đa chiều, đa quan hệ, hay có thể mở rộng lƣu trữ các dữ liệu đa phƣơng tiện nhƣ hình ảnh, âm thanh, video. Trên thế giới, một số hệ quản trị cơ sở dữ liệu hƣớng đối tƣợng đƣợc phát triển bởi các nhà phân phối sản phẩm thƣơng mại, tại các phòng
10 nghiên cứu công nghệ và các Viện Đại học nhƣ: Gemstone, ObjectStores, IRIS, Orion, Extra, Oracle, Db4o,… Một mô hình dữ liệu đối tƣợng chuẩn ODMG đã đƣợc phát triển và dựa vào đó để thiết lập một số khái niệm cơ sở đƣợc gọi là mô hình hạt nhân cho mô hình CSDL hƣớng đối tƣợng. Mô hình hạt nhân đủ mạnh để thỏa mãn nhiều đòi hỏi của các ứng dụng mới, hơn nữa còn đƣợc dùng làm cơ sở để xác định những khác biệt chính giữa mô hình dữ liệu hƣớng đối tƣợng và các mô hình dữ liệu truyền thống khác. Hệ thống hƣớng đối tƣợng là tập các lớp đối tƣợng có mối quan hệ với nhau, trao đổi thông tin với nhau để thực hiện những nhiệm vụ đặt ra của bài toán ứng dụng trong thực tế. Một trong những hƣớng nghiên cứu quan trọng đƣợc đề cập trong các hệ thống CSDL hƣớng đối tƣợng là tối ƣu hoá truy vấn hƣớng đối tƣợng. Với một câu truy vấn, sẽ tồn tại nhiều phƣơng án mà hệ thống CSDL cho phép xử lý và đƣa ra kết quả cuối cùng tƣơng đƣơng nhau, việc tối ƣu hóa câu truy vấn sẽ cho chúng ta lựa chọn phƣơng án nào có tổng thời gian thực hiện truy vấn hiệu quả hơn, tức là chọn phƣơng án có chi phí ƣớc lƣợng nhỏ nhất. Hiện nay, các nhà nghiên cứu đã đề xuất rất nhiều kỹ thuật tối ƣu hoá truy vấn hƣớng đối tƣợng khả thi và đáp ứng đƣợc các yêu cầu này nhƣ: Scott Lee Vanderberg (1993), J. Fong (1997), C. Ramanathan and J. Hodges (1997), Clement Yu, Yi Zhang, Weiyi Meng, Wom Kim, Gaoming Wang, Tracy Pham and Son Daop (1997): Giới thiệu giải thuật chuyển đổi các truy vấn hướng đối tượng sang truy vấn quan hệ để tận dụng các kỹ thuật tối ưu hoá truy vấn đã có trên mô hình quan hệ; Jia Liang Han (1998): “Optimizing Relational Queries in Connection Hypergraph: Nested Queries, Views, and Binding Propagations”; Ullman and Jeffrey D. (1999), Lê Mạnh Thạnh và Hoàng Bảo Hùng (2009): Phương pháp tối ưu hóa truy vấn đối tượng bằng các phép biến đổi biểu thức đại số đối tượng OQL; Lê Mạnh Thạnh, Đoàn Văn Ban và Hoàng Bảo Hùng (2005): Phương pháp dùng ký pháp siêu đồ thị để biểu diễn và tối ưu hoá các truy vấn trong CSDL hướng đối tượng. Tuy nhiên đối với các truy vấn lồng, khi phân tích ƣớc lƣợng chi phí của biểu thức đại số lồng thì việc định giá sẽ cho chi phí chƣa đạt hiệu quả nhƣ mong muốn. Vì vậy, luận văn tập trung nghiên cứu việc làm phẳng các truy vấn con trong truy vấn lồng nhờ phương pháp dùng ký pháp siêu đồ thị để biểu diễn và tối ưu hoá các truy vấn trong CSDL hướng đối tượng. Từ đó, xây dựng thuật toán ƣớc lƣợng chi phí xử lý truy vấn đối tƣợng trên cơ sở ƣớc lƣợng các siêu cạnh trong siêu đồ thị để đạt đƣợc mức chi phí nhỏ hơn cho mỗi truy vấn. Chính vì lý do trên mà tôi chọn đề tài “TỐI ƢU HOÁ TRUY VẤN CƠ SỞ DỮ LIỆU HƢỚNG ĐỐI TƢỢNG” làm luận văn tốt nghiệp. Mục tiêu của luận văn là nghiên cứu các mô hình CSDL hƣớng đối tƣợng để giải bài toán tối ưu hóa truy vấn đối tượng. Đây là vấn đề luôn đƣợc các nhà khoa
11 học quan tâm nghiên cứu. Trong khuôn khổ của luận văn, tôi tập trung nghiên cứu vào phƣơng pháp tối ƣu hóa truy vấn mà hay đƣợc sử dụng nhất đặc biệt là đối với các truy vấn lồng đó là sử dụng phƣơng pháp siêu đồ thị. Nghiên cứu các đặc trƣng trong mô hình dữ liệu hƣớng đối tƣợng; Tìm hiểu các kỹ thuật xử lý truy vấn, sự biểu diễn câu truy vấn bằng ngôn ngữ truy vấn đối tƣợng OQL; Giới thiệu ký pháp siêu đồ thị [10] trong biểu diễn truy vấn. Từ đó, sử dụng phƣơng pháp này để tối ƣu hóa truy vấn cho lớp các truy vấn lồng trong CSDL hƣớng đối tƣợng [3]. Với mục tiêu của luận văn nhƣ vậy, bố cục của luận văn gồm: phần mở đầu, ba chƣơng nội dung và phần kết luận. Chƣơng 1: Giới thiệu các khái niệm, định nghĩa cơ bản nhƣ: lớp, đối tƣợng, định danh đối tƣợng trong mô hình CSDL hƣớng đối tƣợng; kế đến, trình bày sự mở rộng ngữ nghĩa của mô hình nhƣ hệ thống phân cấp và quan hệ kế thừa. Tìm hiểu kỹ thuật xử lý truy vấn và các thay đổi so với kỹ thuật xử lý truy vấn quan hệ. Để thực hiện đƣợc các câu truy vấn đối tƣợng một cách hiệu quả và tiếp tục nghiên cứu các vấn đề về tối ƣu hoá truy vấn trong các CSDL hƣớng đối tƣợng, ngôn ngữ truy vấn OQL là ngôn ngữ truy vấn đƣợc chọn giới thiệu trong chƣơng này. Chƣơng 2: Trình bày khái niệm siêu đồ thị kết nối đối tƣợng. Sau đó sử dụng ký pháp siêu đồ thị để biểu diễn truy vấn OQL. Xây dựng giải thuật khởi tạo siêu đồ thị trong các trƣờng hợp truy vấn đối tƣợng đơn và lồng. Đƣa ra giải thuật ƣớc lƣợng siêu cạnh cho các trƣờng hợp tách biệt hay liên thông của các siêu đồ thị con hợp thành siêu đồ thị mà biểu diễn cho một truy vấn đối tƣợng lồng. Cuối chƣơng, là mở rộng thuật toán tối ƣu hóa truy vấn trên cơ sở xây dựng danh sách các bƣớc thực thi câu truy vấn theo quy tắc có thứ tự loại bỏ siêu cạnh. Chƣơng 3: Giới thiệu về hệ quản trị CSDL đối tƣợng DB4O. Phát biểu bài toán quản lý nhân sự trong công ty, đó là bài toán đƣợc áp dụng trong các ví dụ cho thuật toán tối ƣu hóa truy vấn. Đƣa ra kết quả thực nghiệm cho bài toán tối ƣu hóa truy vấn CSDL hƣớng đối tƣợng dựa trên siêu đồ thị. Cuối cùng là kết luận và hƣớng phát triển của đề tài. Nội dung cơ bản của luận văn đã đƣợc trình bày, thảo luận tại xêmina khoa học ở Bộ môn Hệ thống thông tin, khoa Công nghệ Thông tin, trƣờng Đại học Công nghệ - Đại học Quốc gia Hà nội.
12 Chƣơng 1 MÔ HÌNH CƠ SỞ DỮ LIỆU HƢỚNG ĐỐI TƢỢNG 1.1. Tổng quan về hệ thống dữ liệu hƣớng đối tƣợng 1.1.1. Mô hình dữ liệu Các hệ thống quản trị cơ sở dữ liệu (CSDL) đầu tiên xuất hiện trƣớc những năm 1970. Những hệ thống này đƣợc phát triển từ hệ thống các tệp tin (File Systems) để hỗ trợ cho việc lƣu trữ và xử lý số lƣợng lớn các dữ liệu. Tuy nhiên, các nhà nghiên cứu trong lĩnh vực CSDL nhận thấy giá trị của dữ liệu cần đƣợc lƣu trữ để xử lý, và các mô hình dựa trên dữ liệu cần đƣợc nghiên cứu để cải thiện độ tin cậy, đảm bảo an ninh, an toàn dữ liệu và nâng cao hiệu quả của việc truy cập vào hệ thống. Mô hình dữ liệu cung cấp cách thức tổ chức các dữ liệu đƣợc lƣu trữ theo cấu trúc đặc biệt hoặc theo các mối quan hệ sao cho việc truy cập và quản lý nhanh chóng, hiệu quả. Nhiều mô hình CSDL nhƣ mô hình phân cấp (Hierarchical model), mô hình mạng (Network model), mô hình quan hệ (Relational model), mô hình hƣớng đối tƣợng (Object-Oriented model) nhƣ Hình 1.1 đã xuất hiện và đóng vai trò quan trọng trong việc nghiên cứu phát triển các hệ thống quản trị CSDL (DataBase Management System). File Systems Network Hierarchical Relational Object-Oriented Semantic Data Complex Object System Model (ERD) Model Object-Oriented Databases Hình 1.1. Sự phát triển của các mô hình dữ liệu [1] 1.1.2. Những hạn chế của cơ sở dữ liệu quan hệ Mô hình CSDL quan hệ truyền thống đƣợc sử dụng nhiều nhƣng chƣa đáp ứng đƣợc hết các yêu cầu của thực tế. Mô hình quan hệ chỉ phù hợp cho những bài toán có bộ dữ liệu nhỏ và không đáp ứng đƣợc cho những bài toán ở lĩnh vực ứng dụng mới, nhiều kiểu dữ liệu phức tạp. Ví dụ, khi cần lƣu trữ và xử lý một số lƣợng lớn dữ liệu, dữ liệu hình ảnh, âm thanh hay video, … thì việc sử dụng mô hình quan hệ sẽ không đạt hiệu quả. Nhƣng đa phần những ứng dụng mới hiện nay đòi hỏi hệ thống cơ sở dữ
13 liệu phải xử lý đƣợc các tính năng nhƣ: các kiểu dữ liệu phức tạp, đóng gói dữ liệu (Data Encapsulation) và cấu trúc dữ liệu trừu tƣợng, cùng với những phƣơng pháp mới để lập chỉ mục và truy vấn thông tin. Phần lớn các hệ quản trị CSDL phổ biến hiện nay trên thị trƣờng là các hệ quản trị dữ liệu theo mô hình quan hệ. Tuy nhiên, các hệ quản trị CSDL quan hệ có những hạn chế nhƣ sau [13,19]: Hạn chế trong vấn đề biểu diễn thế giới thực (Real world): Các quan hệ (relations) không đủ mạnh để thể hiện các thực thể (entities) trong thế giới thực. Rất khó để mà biểu diễn đƣợc mối quan hệ kế thừa, mối quan hệ thành viên (IS-A relationships). Ví dụ nhân viên là một ngƣời, trong ví dụ này, hệ quản trị CSDL quan hệ phải định nghĩa 2 bảng là bảng Nguoi và bảng NhanVien, trong đó bảng NhanVien nhận đƣợc những thông tin từ lớp cha (superclass) Nguoi để kết nối lại. Hạn chế về nạp chồng ngữ nghĩa (Semantic overloading): Thành phần chuẩn trong mô hình quan hệ là quan hệ (relation) không đủ mạnh để biểu diễn cho dữ liệu và các mối quan hệ phức tạp của dữ liệu. Nó thƣờng phải chia một đối tƣợng thành một số các quan hệ (bảng) và truy vấn tin thì phải thực hiện các phép: chiếu, chọn và kết nối để tái cấu trúc các đối tƣợng đó. Chỉ biểu diễn những dữ liệu thuần nhất: Những hạn chế về kiểu dữ liệu trong mô hình quan hệ làm nó không thể biểu diễn đƣợc các đối tƣợng trong thế giới thực. Một mục (item) bất kỳ trong một bộ dữ liệu (tuple) thực chất là phần giao nhau của hàng với cột, nó phải là dữ liệu của một kiểu dữ liệu nguyên tố, bởi vì theo giả thuyết, cả chiều ngang và chiều dọc đều phải có kiểu thuần nhất. Hệ thống khép kín: Những lĩnh vực ứng dụng còn tồn tại không thể bổ sung đƣợc vào hệ thống sau khi phát triển hệ quản trị CSDL, nhƣ không thể bổ sung các kiểu dữ liệu mới vào hệ thống. Nhƣng thực tế đòi hỏi các hệ quản trị CSDL phải hỗ trợ để xử lý những kiểu dữ liệu mới nhƣ kiểu hình ảnh (images), video, audio, … Giới hạn các phép toán: Mô hình quan hệ có một tập cố định các phép toán trong SQL. Ngoài ra, không cho phép mở rộng hay bổ sung thêm những phép toán mới. Khó thực hiện truy vấn đệ qui: Các câu truy vấn đệ qui cực kỳ khó đặc tả và cài đặt trong mô hình quan hệ. Đây cũng chính là điểm yếu làm cho SQL không thực hiện đƣợc đầy đủ trong tính toán. Những trở ngại trong đối sánh: Mô hình quan hệ sử dụng những mô thức lập trình hỗn hợp khác nhau, trong đó cho phép các dữ liệu với kiểu khác nhau và nhiều vị trí khác nhau có thể đƣợc xử lý trong cùng một thời điểm. 1.1.3. Mô hình dữ liệu hƣớng đối tƣợng Trong số các mô hình dữ liệu hiện nay, mô hình dữ liệu đối tƣợng là mô hình đảm bảo tính mềm dẻo, tính linh hoạt, và tính “mở” của hệ thống. Mô hình dữ liệu
14 hƣớng đối tƣợng đang đƣợc phát triển một cách phổ dụng trong lĩnh vực phát triển CSDL. Đƣợc xây dựng theo cách tiếp cận hƣớng đối tƣợng nhằm khắc phục những hạn chế của những mô hình dữ liệu truyền thống. Mô hình dữ liệu hƣớng đối tƣợng có các đặc trƣng cơ bản sau [6, 13]: - Thông tin đƣợc biểu diễn thành các đối tƣợng giống nhƣ các đối tƣợng trong lập trình hƣớng đối tƣợng. Lớp bao gồm các thông tin: + Dữ liệu thuộc tính mô tả các đặc trƣng của các thực thể (đối tƣợng) + Các phƣơng thức mô tả hành vi ứng xử của đối tƣợng + Mối quan hệ giữa các lớp với nhau. - Mỗi đối tƣợng (thực thể) có một định danh ID để xác định duy nhất trong hệ CSDL. - Các CSDL hƣớng đối tƣợng đƣợc thiết kế để làm việc tốt đối với những ngôn ngữ lập trình hƣớng đối tƣợng nhƣ: Java, C++, C#, Smalltalk,…. Mục đích của CSDL hƣớng đối tƣợng là để quản trị hiệu quả những kiểu dữ liệu phức hợp, dữ liệu đa phƣơng tiện nhƣ âm thanh, hình ảnh, ... , nhằm khắc phục những hạn chế của CSDL quan hệ. Hình vẽ sau đây giới thiệu về mô hình dữ liệu hƣớng đối tƣợng nguyên mẫu. Hệ thống CSDL Lập trình hướng đối truyền thống tượng - Sự bền vững - Nhận dạng đối tƣợng - Tính chia sẻ Ngữ nghĩa mô - Sự đóng gói - Các giao dịch hình dữ liệu - Sự kế thừa - Kiểm soát trùng lặp - Sự tổng quát hoá - Kiểu và các lớp - Kiểm soát phục hồi - Sự kết nhập - Phƣơng thức - Tính bảo mật - Đối tƣợng phức Các chức năng đặc - Tính toàn vẹn - Tính đa hình thái biệt - Truy vấn - Tính mở - Phiên bản - Sự tiến hoá lƣợc đồ MÔ HÌNH DỮ LIỆU HƢỚNG ĐỐI TƢỢNG Hình 1.2. Mô hình dữ liệu hướng đối tượng nguyên mẫu [13] Trên cơ sở kế thừa và phát triển các điểm mạnh của CSDL quan hệ thì CSDL đối tƣợng đã bổ sung các tính chất mà CSDL quan hệ vẫn còn thiếu sót. Cũng nhƣ hệ thống CSDL truyền thống, hệ thống CSDL hƣớng đối tƣợng có tính bền vững, tính chia sẻ dữ liệu, tính bảo mật, tính toàn vẹn và truy vấn dữ liệu. Ngoài ra, CSDL hƣớng đối tƣợng còn có những ƣu điểm khác nhƣ [13]:
15 Hỗ trợ những kiểu dữ liệu được định nghĩa bởi người sử dụng: CSDL hƣớng đối tƣợng có khả năng lƣu trữ các kiểu phức hợp, kiểu đƣợc định nghĩa bởi ngƣời sử dụng, cho phép thao tác trong kiểu dữ liệu một cách dễ dàng. Cải tiến đáng kể về chất lượng dữ liệu: Ta có thể đƣa ra nhiều ràng buộc vào cấu trúc dữ liệu. Mô hình còn cho phép thể hiện đƣợc cả những ràng buộc không có cấu trúc mà chƣơng trình phải thoả mãn khi nó thực hiện trong hệ CSDL. Một CSDL quan hệ đƣợc chuẩn hóa có thể xem nhƣ một trƣờng hợp đặc biệt của CSDL hƣớng đối tƣợng. Tốc độ phát triển phần mềm nhanh hơn: Cấu trúc CSDL nhất quán và rõ ràng giúp cho lập trình ứng dụng trở nên đơn giản và nhanh hơn. Những ngƣời phát triển ứng dụng có kinh nghiệm thƣờng sử dụng những câu lệnh rất mạnh của các hệ quản trị CSDL thay cho những đoạn chƣơng trình của ngƣời sử dụng. Tích hợp dữ liệu dễ dàng và tiện lợi: Việc tích hợp nhiều hệ thống độc lập có thể làm giảm bớt sự sao chép dữ liệu của con ngƣời và mở rộng những câu truy vấn có thể trả lời đƣợc. Mô hình hƣớng đối tƣợng cung cấp cách biểu diễn thống nhất làm thuận tiện hơn cho việc tìm hiểu và tích hợp thông tin. Không cần các khóa chính (Primary Keys): ngƣời sử dụng hệ quản trị CSDL quan hệ thƣờng phải lo lắng về tính duy nhất để phân biệt các bộ dữ liệu và đảm bảo rằng không có hai bộ dữ liệu có cùng giá trị của khóa chính để tránh xảy ra xung đột. Nhƣng trong một hệ quản trị CSDL hƣớng đối tƣợng, việc xác định duy nhất của các đối tƣợng đƣợc thực hiện bởi định danh đối tƣợng (OID) và ngƣời sử dụng không cần phải quan tâm về chúng. Một mô hình dữ liệu thống nhất: Một mô hình dữ liệu thông thƣờng phải mô hình hóa các thực thể, các mối quan hệ, các ràng buộc và các hoạt động thay đổi trạng thái của dữ liệu trong hệ thống. Với hệ quản trị CSDL quan hệ ta không thể mô hình đƣợc các hoạt động và không đƣa ra đƣợc những quy tắc để làm thay đổi trạng thái của dữ liệu trong hệ thống, bởi vì điều này vƣợt quá phạm vi của cơ sở dữ liệu. Vì vậy, các ứng dụng sử dụng hệ thống CSDL quan hệ thƣờng sử dụng một sơ đồ quan hệ - thực thể để mô hình các bộ phận tĩnh của hệ thống và một mô hình riêng biệt cho các hoạt động và hành vi của các thực thể trong ứng dụng. Với hệ quản trị CSDL hƣớng đối tƣợng, không có sự tách biệt giữa các mô hình dữ liệu và mô hình ứng dụng để mô tả đầy đủ các đặc trƣng, tính chất tĩnh cũng nhƣ hành vi ứng xử động của các đối tƣợng. Toàn bộ ứng dụng nhƣ vậy có thể đƣợc mô hình đầy đủ trong các biểu đồ UML. 1.2. Các khái niệm cơ sở 1.2.1. Đối tƣợng, Định danh đối tƣợng và Lớp đối tƣợng Đối tƣợng (Object)
16 Đối tƣợng là một khái niệm cơ sở quan trọng nhất của cách tiếp cận hƣớng đối tƣợng. Đối tƣợng là thực thể của hệ thống, của CSDL chỉ một ngƣời, một địa điểm hay một vật nào đó tồn tại trong thế giới thực. Một thực thể bất kỳ trong thế giới thực là một đối tƣợng. Đối tƣợng trong thế giới thực đƣợc xác định duy nhất, chứa một tập nhất định các thông tin về đối tƣợng và các hành vi dựa trên các thông tin đó. Một đối tƣợng cũng có thể có các mối quan hệ hay có khả năng trao đổi thông tin với các đối tƣợng khác. Ví dụ: Một đối tƣợng Nhân viên là một ngƣời đang làm việc cho một công ty hay doanh nghiệp nào đó, đƣợc xác định duy nhất trong thế giới thực, chứa một tập nhất định các thông tin về Nhân viên đó nhƣ: mã nhân viên, họ tên, ngày sinh, nơi sinh, lƣơng, dự án mà nhân viên đang tham gia,…Một đối tƣợng Nhân viên có thể có các quan hệ với các đối tƣợng khác, nhƣ quan hệ với đối tƣợng Phòng ban hay đối tƣợng Dự án mà nhân viên đó đang tham gia làm việc. Trong CSDL hƣớng đối tƣợng, các đối tƣợng trong thế giới thực đƣợc mô hình hóa, biểu diễn vào CSDL theo các đặc trƣng của đối tƣợng và luôn duy trì sự tƣơng ứng trực tiếp giữa các đối tƣợng trong CSDL với các đối tƣợng trong thế giới thực. Định danh đối tƣợng (OID: Object Identity) Một đối tƣợng đƣợc xác định duy nhất trong thế giới thực, và do đó cũng phải đƣợc biểu diễn duy nhất trong CSDL. Việc xác định duy nhất đối tƣợng trong CSDL đƣợc thực hiện bằng cách sử dụng các Định danh đối tƣợng (Object Identity) hay OID. Hệ thống CSDL hƣớng đối tƣợng cung cấp một định danh duy nhất cho mỗi đối tƣợng và đƣợc lƣu trữ trong CSDL. Định danh duy nhất này do hệ thống tự động tạo ra và đƣợc gọi là định danh đối tƣợng. Giá trị OID ngƣời dùng không nhìn thấy đƣợc, nó đƣợc sử dụng bên trong hệ thống để xác định duy nhất một đối tƣợng và dùng để tạo ra các tham chiếu bên trong đối tƣợng. OID của mỗi đối tƣợng phải thỏa mãn hai tính chất sau: 1. Giá trị OID của một đối tƣợng không đƣợc thay đổi trong CSDL hƣớng đối tƣợng. Điều này đảm bảo tính duy nhất của mỗi đối tƣợng. Do đó, một hệ thống CSDL hƣớng đối tƣợng phải có cơ chế tạo ra các OID và đảm bảo tính bất biến. 2. Mỗi giá trị OID chỉ đƣợc sử dụng duy nhất một lần; nghĩa là khi một đối tƣợng bị xóa đi từ CSDL thì OID của nó cũng không đƣợc gán cho đối tƣợng bất kỳ nào khác. Định danh đối tƣợng OID khác với khóa chính của đối tƣợng. Khóa chính của đối tƣợng là một thuộc tính của đối tƣợng, đƣợc ngƣời dùng gán giá trị và có thể nhìn thấy, thay đổi đƣợc và có thể đƣợc cấp lại, còn OID thì không. Ví dụ: Một Nhân viên đƣợc biểu diễn trong CSDL có một OID duy nhất, xác định sự tƣơng ứng Nhân viên đó trong thế giới thực. Một Nhân viên khác trong thế
17 giới thực nếu đƣợc biểu diễn trong CSDL thì phải có một OID khác với OID của Nhân viên trên, thậm trí cả khi Nhân viên trên bị xóa khỏi hệ thống. Điều này đảm bảo sự tƣơng ứng của CSDL với thế giới thực, tránh sự nhầm lẫn về các đối tƣợng đƣợc biểu diễn trong CSDL. Lớp đối tƣợng (Class) Đối tƣợng là thể hiện, là đại diện của một lớp. Lớp là một mô tả về một nhóm các đối tƣợng có những tính chất (thuộc tính) giống nhau, có chung các hành vi ứng xử, có cùng mối liên quan với các đối tƣợng của các lớp khác và có chung ngữ nghĩa trong hệ thống. Trong các mô hình và các ngôn ngữ lập trình hƣớng đối tƣợng, lớp thƣờng đƣợc mô tả bằng từ khóa Class. Ví dụ trong lƣợc đồ quản lý nhân viên ta có các lớp: NhanVien, PhongBan, DuAn …Trong đó, lớp Nhân viên mô tả cấu trúc chung của các đối tƣợng Nhân viên, đƣợc khai báo nhƣ sau: Class NhanVien { Private: // khai báo các thuộc tính của đối tượng int manso; string hoten; datetime ngaysinh; string diachi; double luong; Public: // khai báo các hành vi của đối tượng Void Thongtin_nhanvien(); Float Tinhluong(); } 1.2.2. Thuộc tính và phƣơng thức Thuộc tính (Attribute) Thuộc tính để miêu tả những đặc điểm của đối tƣợng. Việc khai báo các thuộc tính thể hiện cấu trúc của lớp đƣợc khai báo. Mỗi thuộc tính có một tên duy nhất trong đối tƣợng và giá trị đƣợc biểu diễn trong miền giá trị của một kiểu dữ liệu nào đó. Các kiểu dữ liệu này có thể là các kiểu dữ liệu cơ bản nhƣ: kiểu số nguyên, số thực, kiểu xâu ký tự…, hoặc các kiểu phức tạp do ngƣời dùng định nghĩa, các kiểu đối tƣợng hoặc cũng có thể là các con trỏ hay vector đến các kiểu dữ liệu đó. Thuộc tính có thể là thuộc tính đơn trị hoặc thuộc tính đa trị, thuộc tính đa trị đƣợc khai báo bởi từ khóa set. Ngoài ra một thuộc tính có thể là thuộc tính phức hợp, đƣợc xác định từ tập các thuộc tính khác (sử dụng từ khóa tuple để khai báo). Ví dụ 1.1. Khai báo về các thuộc tính có trong lớp QuanLy
18 Class NhanSu Type tuple ( maso: string[20]; hoten: string[20]; gioitinh: string[10]; diachi: string[20]; ngaysinh: tuple (ngay: integer; thang: integer; nam: integer;) sonamcongtac: integer; luongcoban: double) Class QuanLy inherits NhanSu Type tuple ( chucvu: string; phong: PhongBan; duan: set( DuAn)) Trong ví dụ trên các thuộc tính hoten, giới tính, diachi… là các thuộc tính đơn trị, thuộc tính ngaysinh là thuộc tính phức hợp. Còn thuộc tính duan là thuộc tính đa trị, với ngữ nghĩa rằng mỗi đối tƣợng thuộc lớp QuanLy có thể tham gia vào nhiều dự án khác nhau; nghĩa là mỗi đối tƣợng thuộc lớp QuanLy cho tƣơng ứng một tập các giá trị OID của các đối tƣợng thuộc lớp DuAn. Phƣơng thức (Method) Phƣơng thức của một lớp thƣờng đƣợc dùng để mô tả các hành vi của đối tƣợng (hoặc của lớp). Ví dụ nhƣ đối tƣợng thuộc lớp điện thoại có các hành vi sau: Đổ chuông, chuyển tín hiệu từ sóng sang dạng nghe đƣợc, chuyển tín hiệu giọng nói sang dạng chuẩn, chuyển tín hiệu lên tổng đài.v.v. Khi thiết kế, ngƣời ta có thể dùng các phƣơng thức để mô tả và thực hiện các hành vi của đối tƣợng. Mỗi phƣơng thức thƣờng đƣợc định nghĩa là một hàm, các thao tác để thực hiện hành vi đó đƣợc viết tại nội dung của hàm. Khi thực hiện hành vi này, đối tƣợng có thể phải thực hiện các hành vi khác. Ví dụ nhƣ điện thoại phải chuyển tín hiệu giọng nói sang dạng chuẩn trƣớc khi chuyển lên tổng đài. Cho nên một phƣơng thức trong một lớp có thể sử dụng phƣơng thức khác trong quá trình thực hiện hành vi của mình. 1.2.3. Các kiểu dữ liệu Các khái niệm sau đây đƣợc sử dụng trong hầu hết các hệ CSDL hƣớng đối tƣợng, chẳng hạn nhƣ Gemstone, Orion, Ontos, O2, ObjectStore, ODMG. Để thuận tiện trong trình bày, chúng ta sử dụng một số ký hiệu sau [4, 6, 21]: T – tập hữu hạn các kiểu L – tập các kiểu nguyên thuỷ nhƣ: byte, int, long, float, double, char, string và boolean.
19 Att – tập tất cả thuộc tính của các đối tƣợng trong hệ thống O – tập tất cả đối tƣợng và các đại lƣợng trong một CSDL. Class – tập các tên lớp Tập Dom các giá trị nguyên thuỷ là hợp của tất cả các miền giá trị cơ sở của ngôn ngữ lập trình. Các phần tử của Dom đƣợc gọi là hằng, trong đó nil là một hằng đặc biệt biểu diễn giá trị không xác định. Tập Obj = {o1, o2, …} là tập vô hạn các định danh đối tượng (OID) và tập Oid là tập con các định danh đối tƣợng, Oid  Obj. Họ giá trị trên Oid, ký hiệu Val(Oid), đƣợc xác định nhƣ sau: (i) Hằng nil  Val(Oid) (ii) Nếu v  Dom thì v  Val(Oid) (iii) Nếu o  Oid thì o  Val(Oid) (iv) Tập {vi | vi  Val(Oid), (i = 1,..., n)}  Val(Oid) (v) Cho tập các giá trị {vi | vi  Val(Oid), (i = 1,..., n)} và tập các tên thuộc tính rời nhau {Ai | Ai, Aj  Att, (i  j  Ai  Aj), (i, j = 1, ..., n)} thì bộ [Ai : v1, ..., An : vn]  Val(Oid). Một đối tƣợng trong hệ thống thƣờng đƣợc mô tả là một cặp (o, v), trong đó o là định danh đối tƣợng và v là trạng thái hay bộ giá trị hiện thời của đối tƣợng. Các đối tƣợng cùng tính chất và hành vi đƣợc nhóm lại để tạo thành một lớp. Mỗi lớp C có một kiểu xác định, ký hiệu là σ(C) - kiểu của các đối tƣợng trong lớp. Thuật ngữ Class đƣợc sử dụng để mô tả định nghĩa kiểu của lớp các đối tƣợng. Ví dụ 1.2: Cho lƣợc đồ CSDL hƣớng đối tƣợng sau: Class NhanVien Type tuple (hoten: string; gioitinh: boolean,; luongCB: double; phongban: PhongBan) Class PhongBan Type tuple (tenphong : string; truongphong: NhanVien; SoNV: set (NhanVien )) Ta tiến hành biểu diễn một số đối tƣợng từ lƣợc đồ CSDL đối tƣợng trên, trong đó mỗi đối tƣợng là một cặp (o, v). Xét các đối tƣợng Ob1 = (o1, [hoten: “Nam Phong”, gioitinh: false, luong: 6000000, phong: o5]) Ob2 = (o2, [hoten: “Nguyên Minh”, gioitinh: true, luong: 4000000, phong: o5]) Ob3 =(o3, [hoten: “Trần Hùng”, gioitinh: false, luong: 5000000, phong: o5])
20 Ob4 =(o4, [hoten: “Minh Châu”, gioitinh: true, luong: 3500000, phong: o5]) Ob5 =(o5, [tenphong: “Kinh Doanh”, truongphong: o1, SoNV: {o1, o2, o3, o4}]) Đối tƣợng Ob1 theo định nghĩa trong lƣợc đồ trên sẽ gồm định danh o1 và một bộ (tuple) các giá trị: [hoten : “Nam Phong”, gioitinh : false, luong : 6000000, phong : o5]. Đối tƣợng Ob5 có định danh là o5 và một giá trị bộ: [tenphong : “Kinh Doanh”, truongphong : o1, SoNV : {o1, o2, o3, o4}], trong đó, thuộc tính tenphong có giá trị nguyên thủy, thuộc tính truongphong tham chiếu đến đối tƣợng có định danh đối tƣợng là o1, thuộc tính SoNV (số lƣợng nhân viên) có giá trị tập (set) tham chiếu đến các đối tƣợng với các định danh đối tƣợng o1, o2, o3, o4. Trong mô hình dữ liệu quan hệ, so sánh bằng của các bộ trong quan hệ luôn dựa trên các giá trị của bộ, hai bộ bằng nhau nếu tất cả các thuộc tính khoá của hai bộ có cùng giá trị. Tuy nhiên, trong mô hình CSDL hƣớng đối tƣợng cần phân biệt hai khái niệm “đồng nhất” và “bằng nhau” của các đối tƣợng nhƣ trong thực tế. Hai quan hệ này đƣợc định nghĩa nhƣ sau: Định nghĩa 1.1: Cho hai đối tƣợng S1(o1, v1) và S2(o2, v2). i. Đối tượng đồng nhất: Hai đối tƣợng S1 và S2 đƣợc gọi là đối tƣợng đồng nhất, ký hiệu S1 = oidS2 nếu chúng có cùng định danh đối tƣợng, tức là S1.o1 = S2.o2 ii. Đối tượng bằng nhau: Hai đối tƣợng S1 và S2 đƣợc gọi là bằng nhau về giá trị, ký hiệu S1 = vS2 - Nếu kiểu của đối tƣợng là nguyên thuỷ thì chúng phải có cùng giá trị - Nếu kiểu của đối tƣợng là kiểu không nguyên thuỷ thì chúng phải có cùng số các tính chất và với mọi tính chất pi của S1 đều tồn tại tính chất pj của S2 bằng nhau về giá trị. Các kiểu dữ liệu Các kiểu cơ sở bao gồm các kiểu chuẩn trong SQL nhƣ: integer, string, float, char, double, ….và các kiểu do ngƣời dùng định nghĩa nhƣ lớp hoặc cấu trúc Các kiểu tập hợp đây là các kiểu đặc trƣng chỉ có ở truy vấn hƣớng đối tƣợng nhƣ: set, bag, list, array chỉ đến một tập hợp các đối tƣợng. - Set: Với T là một kiểu bất kỳ, set(T) đƣợc định nghĩa là một kiểu tập hợp gồm các phần tử phân biệt nhau có kiểu là T. Ví dụ {1, 2, 5, 8, 9} là một thể hiện của set(integer) - Array: Với T là một kiểu bất kỳ và i có kiểu integer, array là một dãy gồm i phần tử có kiểu T. Mỗi phần tử đƣợc gắn liền với một chỉ số - Bag: Với T là một kiểu bất kỳ, bag(T) đƣợc định nghĩa nhƣ một kiểu tập hợp gồm các phần tử thuộc kiểu T. Khác với set, một phần tử trong bag có thể xuất hiện nhiều hơn một lần và không phân biệt thứ tự giữa chúng. Ví dụ {1, 2, 2, 5} là một thể hiện của bag(integer).