intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 

Đề tài : XỬ LÝ CÂU TRUY VẤN BẰNG PHÉP TOÁN ĐẠI SỐ KẾT HỢP THỜI GIAN

Chia sẻ: Vu Dinh Hiep | Ngày: | Loại File: PDF | Số trang:20

Thêm vào BST
Báo xấu
138
lượt xem 10
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tìm hiểu các phép toán đại số kết hợp thời gian Thiết kế CSDL đối tượng cho một ứng dụng Xây dựng các luật sinh để xử lý câu truy vấn trên ứng dụng minh họa.Công cụ truy vấn dữ liệu, tên ngắn hơn là công cụ tìm kiếm (tiếng Anh: search tool), là một loại chương trình tiện ích được nhiều trang Web hay các phần mềm ứng dụng hỗ trợ nhằm giúp cho người dùng có thể tìm kiếm cụm từ, bài viết, đề tài, tập tin, hay dữ liệu được cung cấp bởi trang Web (hay bởi...

Chủ đề:

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

Lưu

Nội dung Text: Đề tài : XỬ LÝ CÂU TRUY VẤN BẰNG PHÉP TOÁN ĐẠI SỐ KẾT HỢP THỜI GIAN

  1. LUAÄN VAÊN TOÁT NGHIEÄP ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC KỸ THUẬT TP. HỒ CHÍ MINH KHOA CÔNG NGHỆ THÔNG TIN  LUẬN ÁN TỐT NGHIỆP Đề tài : Xử lý câu truy vấn bằng phép toán đại số kết hợp thời gian Nhiệm vụ đề tài : Tìm hiểu các phép toán đại số kết hợp thời gian - Thiết kế CSDL đối tượng cho một ứng dụng - Xây dựng các luật sinh để xử lý câu truy vấn trên ứng dụng minh họa - Trang 1
  2. LUAÄN VAÊN TOÁT NGHIEÄP LỜI MỞ ĐẦU Trong xã hội ngày nay, việc quản lý dữ liệu diễn ra trên mọi ngành trong đó việc vi tính hoá các khâu lưu trữ và quản lý dữ liệu ngày càng được áp dụng cả chiều sâu lẫn chiều rộng. Cụ thể, dựa vào các tính năng của chương trình quản lý trên máy tính giúp cho người quản lý đưa ra được những thông tin chính xác, kịp thời. Tuy nhiên, trong thực tế mọi thông tin đều có thể gắn với thời gian và việc lưu trữ thời gian cùng với dữ liệu là cần thiết giúp cho quá trình quản lý được hiệu quả hơn, nhưng thực tế vì nhu lý do mà việc gắn thời gian vào dữ liệu chưa được thực hiện trong các chương trình quản lý. Từ thực tế đó, đề tài "Xử lý câu truy vấn bằng phép toán đại số kết hợp thời gian" đ ược xây dựng nhằm giúp cho mọi người thấy được khả năng và tính hiệu quả mang lại khi gắn thời gian vào dữ liệu, từ đó có thể áp dụng vấn đề này vào thực tế giúp cho việc quản lý dữ liệu được hiệu quả hơn. NGƯỜI THỰC HIỆN Trang 2
  3. LUAÄN VAÊN TOÁT NGHIEÄP PHẦN 1 : ĐẠI SỐ KẾT HỢP THỜI GIAN Trang 3
  4. LUAÄN VAÊN TOÁT NGHIEÄP 1- GIỚI THIỆU TAA trình bày dưới đây theo các đặc trưng : (1) TAA dùng 1 mô hình theo mẫu cơ bản thay cho mô hình theo bảng và thuộc tính cơ bản được dùng trong đại số quan hệ và sự mở rộng thời gian, nghĩa là lĩnh vực đại số chứa đựng các tập mẫu thời gian của sự kết hợp đối t ượng. Ở mỗi mẫu có thể có 1 cấu trúc tuyến tính, cây hoặc mạng được phân chia và đồng nhất biểu diễn bởi tập các nguyên mẫu của sự kết hợp đối tượng. Thao tác trên các mẫu này bởi phép toán đại số bảo to àn ngữ nghĩa của sự kết hợp hoặc không kết hợp trực tiếp và gián tiếp giữa các đối tượng. (2) Các toán tử đại số xử lý trên 1 hoặc 2 tập mẫu đồng bộ và không đồng bộ của sự kết hợp đối tượng để tạo ra 1 tập các mẫu mà có thể được xử lý tiếp bởi 1 toán tử khác. Do đó, t ương tự như đại số quan hệ, tính chất bao đóng vẫn được duy trì. (3) TAA hỗ trợ trực tiếp việc xử lý ngữ nghĩa của sự không kết hợp (xem T-Complement và T- Nonassociate của mục 3.5.1), mối quan hệ không quan tâm đến thời gian (xem NT -Intersect, NT- Union, NT-Difference mục 3.5.2) và ngữ nghĩa nhánh AND/OR (xem T-Join và T-Ojoin mục 3.5.2). Nó cũng duy trì sự kết hợp giữa các đối tượng về các đường thông duyệt khác nhau trong khi xử lý truy vấn thời gian. 2.1- DỮ LIỆU THỜI GIAN Cơ sở dữ liệu thời gian xem sự kiện cơ sở dữ liệu như sự kiện thời gian và ghi nhận ảnh hưởng của sự kiện này như diễn tiến của thể hiện thời gian. Có 3 sự kiện thời gian tiêu biểu mà đối tượng có liên quan : cập nhật, xoá và thêm. Ví dụ "cập nhập lương của John thành 35 đồng", "Xoá hồ sơ của Mary", "Thêm hồ sơ của Brown" là những sự kiện thời gian trong cơ sở dữ liệu thời gian. Ở phép toán cập nhật, 1 thể hiện đối t ượng đạt được 1 sự cụ thể thời gian mới và 1 số giá trị thuộc tính mới. Thể hiện cũ trở thành 1 phần quá khứ của thể hiện. Do đó, diễn tiến của 1 thể hiện được xem như 1 phiên bản cũ của thể hiện được gọi là thể hiện thời gian. Thời gian hiệu lực và thời gian phát sinh có liên quan hầu hết đến việc mô hình hoá dữ liệu thời gian. Thời gian hiệu lực của 1 sự việc là thời gian khi sự việc là đúng trong mô hình hiện thực. Thời gian hiệu lực thường được cung cấp bởi người dùng. Thời gian phát sinh của sự việc cơ sở dữ liệu là thời gian khi sự việc được ghi nhận trong 1 cơ sở dữ liệu. Nói chung, mô hình dữ liệu không chỉ lưu giữ thời gian hiệu lực mà còn lưu giữ cả thời gian hiệu lực và thời gian phát sinh; và thời gian hiệu lực là phổ biến nhất sử dụng khái niệm thời gian. D iễn tiến của 1 thể hiện được biểu diễn bởi sự tuần tự của thể hiện thời gian. Thể hiện thời gian được sắp xếp theo thời gian. Điều đó tạo thành dòng thời gian. Dòng thời gian mà ghi nhận thời gian hiệu lực và thời gian phát sinh của 1 thể hiện được gọi là dòng thời gian hiệu lực và dòng thời gian phát sinh. Chúng ta chỉ dùng thời gian hiệu lực để mô tả phép toán đại số. Vì vậy, chúng ta sẽ dùng dòng thời gian để để diễn tả dòng thời gian hiệu lực, đó là sự tuần tự của khoảng thời gian hiệu lực. Khoảng thời gian hiệu lực của 1 thể hiện thời gian đ ược cụ thể bởi thời gian bắt đầu ts và thời gian kết thúc te. Nếu 1 thể hiện biểu diễn 1 số thông tin hiện hành theo quan hệ sau : ts = te = now, với now thay cho 1 giá trị cụ thể mà cho biết rằng thông tin là hiện hành. Do đó, phép toán đại số trình bày ở đây xử lý trên cả 2 dữ liệu hiện hành và quá khứ. 2.2.1- ĐỒ THỊ SƠ ĐỒ Một cơ sở dữ liệu được xem như 1 tập hợp lại các lớp đối tượng quan hệ lẫn nhau với đa dạng các kiểu kết hợp. Ví dụ về đồ thị sơ đồ của 1 cơ sở dữ liệu về công ty được trình bày trong hình 1. Hình vuông biểu diễn các lớp thực thể, hình tròn biểu diễn các thuộc tính xác định trên nền tảng các lớp miền. Các lớp trong các lớp thực thể là các thực thể được quan tâm trong miền Trang 4
  5. LUAÄN VAÊN TOÁT NGHIEÄP ứng dụng. Mỗi đối tượng được gán 1 bộ nhận dạng đối t ượng (Object Identifier (OID)) duy nhất của hệ thống mở. Dữ liệu biểu diễn 1 đối t ượng trong 1 lớp được gọi là 1 thể hiện đối tượng mà được nhận dạng duy nhất bởi bộ nhận dạng thể hiện (Instance Identifier (IID)). Một IID đ ược tạo thành bởi sự nối kết của 1 bộ nhận dạng lớp và OID. Mỗi đối tượng trong 1 lớp miền được đặt chính tên của nó và hỗ trợ như 1 giá tr ị thuộc tính để xác định hoặc mô tả các đối t ượng lớp thực thể/miền còn lại. Các cạnh trong đồ thị sơ đồ biểu diễn sự kết hợp giữa các lớp đối tượng. Mũi tên đậm biểu thị sự kết hợp tổng quát (Lớp Employee là 1 siêu lớp của lớp Manager và Engineer) và đường thẳng biểu thị sự kết hợp to àn bộ giữa các lớp đối tượng. 2.2.2- TỔ CHỨC DỮ LIỆU THỜI GIAN VÀ ĐỒ THỊ ĐỐI TƯỢNG THỜI GIAN Phạm vi của 1 cơ sở dữ liệu thời gian có thể được biểu diễn bởi đồ thị đối t ượng thời gian. Trong đó, các đỉnh biểu diễn thể hiện thời gian. Sự kết hợp giữa các thể hiện thời gian được biểu diễn bởi các mối liên kết qua lại. Mối liên kết thì không có kiểu bởi vì khi sơ đồ của cơ sở dữ liệu được xác định, ngữ nghĩa của kiểu kết hợp bị áp đặt vì sự thao tác đối tượng bị ép buộc bởi hệ thống quản lý cơ sở dữ liệu thời gian hướng đối tượng và người dùng không cần liệt kê rõ ràng kiểu kết hợp khi lập công thức truy vấn. Do đó, trong đồ thị đối t ượng thời gian, 1 cơ sở dữ liệu được trình bày như 1 sự tập hợp lại của các thể hiện thời gian nối kết lẫn nhau qua mối liên kết không kiểu. Một thể hiện thời gian trong đồ thị đối t ượng thời gian có thể được xác định bởi 1 IID mà được tạo bởi sự nối vào của 1 mốc thời gian và 1 IID. Diễn tiến của thể hiện thời gian và các mối quan hệ của chúng trong 1 c ơ sở dữ liệu hướng đối tượng có thể được ghi nhận sử dụng 2 phương pháp mốc thời gian : mốc thời gian thể hiện và mốc thời gian thuộc tính. Trong phương pháp cũ, 1 sự kiện thời gian trên 1 thuộc tính của 1 thể hiện được xem như 1 sự kiện trên toàn thể thể hiện. Do đó, diễn tiến của thể hiện mà chứa đựng cả 2 bản dữ liệu cũ và mới và sự tham khảo kết hợp được ghi nhận trong 1 dòng thời gian chung. Trong phương pháp sau, 1 sự kiện thời gian trên 1 thuộc tính của 1 thể hiện được xử lý như 1 sự kiện riêng lẽ trên cùng thuộc tính đó và do đó sự tiến triển của những thuộc tính khác nhau được ghi nhận riêng biệt trong những dòng thời gian khác nhau. Tổ chức dữ liệu thời gian dựa trên 2 phương pháp mốc thời gian nàyđược biểu diễn bằng đồ thị bởi đồ thị đối t ượng thời gian và bảng trong hình 2. Trong hình này : (1) Kỹ sư en1 kết hợp với phòng d1 tại thời điểm t3 và thay đổi chuyên môn của cô ta thành "DB" tại thời điểm t6. (2) en2 kết hợp với d1 tại thời điểm t9 và thay đổi chuyên môn của anh ta thành "DB" tại thời điểm t16. (3) Cả 2 kỹ sư rời bỏ phòng d1 tại thời điểm t25 (cụ thể bởi dấu "-" trong bảng). Chú ý rằng d1 liên quan tại thời điểm t9 nhờ sự tham gia mới của en2 và vì vậy d1 có cả 2 kỹ sư trong khoảng T[9,24]. Do đó, en# (như en1 và en2) và d# (như d1) thay cho IID hệ thống gán. Mũi tên trong hình là con trỏ hoặc sự tham khảo từ IID đến IID. Nhiều dòng thời gian của 1 thể hiện trong phương pháp mốc thời gian thuộc tính có thể được chuyển đổi thành 1 dòng thời gian duy nhất bởi phép toán sắp thời gian. Ví dụ, 2 dòng thời gian của en1 trong hình 2b có thể liên kết thành 1 dòng thời gian duy nhất của en1 trong hình 2a. Hơn nữa, diễn tiến của 1 thuộc tính riêng lẻ trong phương pháp mốc thời gian thể hiện có thể được thiết lập trên 1 dòng thời gian duy nhất bởi phép toán xác lập thời gian. Trang 5
  6. LUAÄN VAÊN TOÁT NGHIEÄP 2.2.3- PHƯƠNG PHÁP TRUY VẤN THỜI GIAN KHUÔN MẪU CƠ BẢN Những ngôn ngữ thời gian này có 3 thành phần truy vấn cơ bản : sự cụ thể thời gian, điều kiện chọn lựa dữ liệu, phép toán cơ sở dữ liệu. Sự khác biệt từ phương pháp cụ thể hoá truy vấn truyền thống dùng trên cơ sở dữ liệu quan hệ hơn là thuộc tính cơ bản (nghĩa là bằng giá trị của khoá phù hợp và khoá ngoại để đạt được quá trình duyệt các quan hệ), phương pháp truy vấn theo mẫu cơ bản cho phép người sử dụng truy vấn 1 cơ sở dữ liệu thời gian hướng đối tượng bằng sự chi tiết hoá đơn giản các khoảng thời gian và các khuôn mẫu của sự kết hợp đối tượng chẳng hạn như điều kiện t ìm kiếm. Sự thuận lợi của phương pháp truy vấn này là sự đơn giản hoá các câu truy vấn cụ thể phức tạp mà liên quan đến nhiều lớp. Khi những đối t ượng thỏa 1 sự chi tiết các mẫu kết hợp đã được chọn, chúng có thể được xử lý thêm bởi phép toán người dùng hoặc hệ thống xác định. Mẫu của sự kết hợp đối tượng thời gian có thể được được chi tiết bởi 1 biểu thức đại số thời gian bao gồm các lớp đối t ượng và các phép toán đại số mà được nối kết trong 1 cấu trúc tuyến tính, cây hoặc mạng. Ví dụ về phương pháp truy vấn thời gian khuôn mẫu cơ bản sau : Câu hỏi 1 : Tìm kiếm những bằng cấp của những kỹ sư mà tham gia vào những dự án trong khi làm việc trong phòng có dept_no = "1" trong khoảng thời gian T[15,30]. Biểu thức tương ứng của ngôn ngữ OQL/T là : CONTEXT Engineer AND (*Work_On*Project,*Dept) WHEN T[15,30] WHERE Dept.dept_no = "1" RETRIEVE Engineer.degree Câu truy vấn trên tạo nên 1 khuôn mẫu kết hợp cấu trúc cây với 1 nhánh AND. Dấu ‘*’biểu thị cho phép toán T-Associate (xem mục 3.5.1). Những câu truy vấn phức tạp với nhiều nhánh và vòng lặp có thể được cụ thể bằng mẫu cùng quan hệ đơn giản. Điều kiện tìm kiếm phức tạp hơn (số lượng nhiều hơn và sự so sánh thuộc tính lẫn nhau) có thể được cụ thể trong mệnh đề WHERE (mệnh đề con của CONTEXT). Mệnh đề WHEN cụ thể khoảng thời gian hiệu lực được quan tâm. Câu truy vấn trên liên quan đến việc t ìm kiếm sự kết hợp thể hiện trong đường thông duyệt (Engineer*Work_On*Project) và (Engineer*Dept) và rồi nối kết quả vào thể hiện Engineer. Nhánh AND trong câu truy vấn này có thể thay bằng nhánh OR. Các mẫu phức t ãp còn lại mà chứa nhiều cấp của cấu trúc nhánh AND/OR và vòng lặp thì đều có thể có trong 1 ngôn ngữ truy vấn theo mẫu cơ bản. Ngữ nghĩa truy vấn trên đưọc cung cấp trực tiếp từ các phép toán TAA. 3.1- NGUYÊN MẪU KẾT HỢP THỜI GIAN Trong xử lý câu truy vấn theo mẫu cơ bản, 1 mẫu kết hợp phức tạp có thể được phân chia vào 1 tập nguyên mẫu và sự biểu diển đại số tương ứng của chúng có thể được thao tác bởi các phép toán đại số. Khái niệm của mối liên kết kết hợp và không kết hợp được dùng để xác định 5 nguyên mẫu về kết hợp thời gian và sự biểu diển đại số của chúng.Trong hình 5, mối liên kết kết hợp thời gian của thể hiện đối t ượng được biểu diển bởi mũi tên liền nét. Nếu 2 thể hiện đối tượng thời gian không được kết hợp trong 1 số khoảng thời gian, 1 mối liên kết bổ sung (biểu thị bằng mũi tên đứt nét) được vẽ giữa chúng. Mặc dù mối liên kết bổ sung không được cất giữ rõ ràng để lưu trữ lâu dài, nếu 1 câu truy vấn yêu cầu 1 cách rõ ràng thể hiện đối tượng mà không được kết hợp với 1 thể hiện đối t ượng khác nó có thể được đặt trong bộ nhớ chính trong khi xử lý. Năm nguyên mẫu được mô tả dùng đồ thị đối tượng thời gian trình bày trong hình 5. Trang 6
  7. LUAÄN VAÊN TOÁT NGHIEÄP (1) Mẫu thời gian bên trong (Temporal Inner Pattern) : là 1 đỉnh đơn trong 1 đồ thị đối tượng thời gian, biểu diển cho 1 thể hiện đối t ượng (nghĩa là 1 phiên bản thời gian của 1 1 thể hiện đối tượng) và được biểu thị bằng đại số {[ts,te]ai}. Ví dụ : {[0,12]en1},{[13,20]en1} v à {[21,n]en1} là mẫu thời gian bên trong của thể hiện en1. (2) Liên mẫu thời gian (Temporal Interpattern) : cụ thể 1 sự kết hợp giữa 2 thể hiện thời gian kết nối lẫn nhau và được biểu thị đại số {[ts,te]aibj}. Ví dụ {[0,12]en1w1},{[13,20]en1w2} và {[21,n]en1w1} là liên mẫu thời gian giữa thể hiện của Engineer và Work_on. (3) Mẫu thời gian bổ sung (Temporal Complement Pattern) : cụ thể 1 mối liên hệ không kết hợp giữa 2 mẫu thời gian bên trong và được biểu thị bởi {[ts,te]C(aibj)}. Ví dụ : có 2 mẫu thời gian bổ sung (biểu thị bởi mũi tên đứt nét) : {[13,20]C(en1w1)} và {[21,n]C(en1w2)}. Ơ đây giả sử thế giới đóng được tạo. (4) Liên mẫu thời gian dẫn xuất (Temporal Derived Interpattern) : cụ thể sự kết hợp của 2 đỉnh không gần kề mà được nối kết qua đường thông của những liên mẫu thời gian và được biểu thị bởi {[ts,te]D(aibj)}. Nó biểu thị rằng 2 thể hiện thì được nối kết 1 cách gián tiếp với thể hiện còn lại. Ví dụ : {[0,12]D(en1pj1)},{[21,n]D(en1pj1)}, {[15,20]D(en1pj1)} là liên mẫu thời gian dẫn xuất giữa en1 và pj1 với sự xem xét đến w1 và w2. (5) Mẫu thời gian bổ sung dẫn xuất (Temporal Derived Complement Pattern) : biểu thị bởi {[ts,te]DC(aicj)} cụ thể sự không kết hợp giữa 2 đỉnh không kề nhau mà được nối kết qua 1 đường thông chứa đựng ít nhất 1 mẫu thời gian bổ sung. Ví dụ {[13,20]DC(en1pj1)} là mẫu thời gian bổ sung dẫn xuất giữa en1 và pj1 với sự xem xét đến w1. Tương tự, {[21,n]DC(en1pj1)} là mẫu thời gian bổ sung dẫn xuất giữa en1 và pj1 có xem xét đến w2. Các nguyên mẫu trên được trình bày bằng đồ thị và đại số hình 6. Liên mẫu thời gian dẩn xuất và mẫu thời gian bổ sung dẫn xuất duy trì các cặp kết hợp / không kết hợp gián tiếp của thể hiện đối t ượng thời gian khi thể hiện và sự kết hợp của chúng xác lập theo đường thông nối kết giữa chúng (xem phép toán T-Project mục 3.5.2). Mẫu kết hợp phức tạp có thể trình bày bằng đại số bởi tập nguyên mẫu về kết hợp thời gian được mô tả trong hình 7. 3.2- THỂ HIỆN KHUÔN MẪU THỜI GIAN VÀ TẬP KHUÔN MẪU THỜI GIAN Thể hiện mẫu thời gian (Temporal Pattern Instance (TPI)) là 1 mẫu mở rộng (hoặc 1 mẫu của thể hiện thời gian) mà phù hợp với sự cụ thể hoá mẫu mở rộng. Tập mẫu thời gian (Temporal Pattern Set (TPS)) là 1 tập của tất cả TPI mà phù hợp với sự chi tiết mẫu mở rộng và sự cụ thể khoảng thời gian của 1 câu truy vấn. Ví dụ : dựa trên hình 5 phát biểu 1 câu truy vấn theo sau tạo ra 1 TPS và những TPI của nó. "Những kỹ sư mà làm việc trên những dự án trong những thời gian T[0,n]"=>{[0,12]en1w1,[0,12]w1pj1},{[15,20]en1w2,[15,20]w2pj1},{[21,n]en1w1,[21,n]w1pj1 }. Bởi vậy 1 TPS là 1 tập của bộ nguyên mẫu về kết hợp thời gian (nghĩa là các TPI), được trình bằng đồ thị hình 8. Các phép toán TAA xử lý trên 1 hoặc 2 TPS sẽ tạo ra 1 TPS và 1 câu truy vấn thời gian cấp cao được dịch ra 1 cấu trúc của các phép toán đại số cùng cách như sự xử lý của 1 câu truy vấn quan hệ trong đại số quan hệ. TPS được xem là đồng nhất nếu tất cả TPI của nó là của cùng 1 mẫu mở rộng (nghĩa là thể hiện đối tượng trong những TPI là những thành viên tương ứng của cùng 1 tập các lớp đối tượng). Ví dụ được trình bày ở trên là đồng nhất. Một TPS được xem là không đồng nhất nếu có tồn tại vài TPI mà không có cùng mẫu mở rộng. Một TPS không đồng Trang 7
  8. LUAÄN VAÊN TOÁT NGHIEÄP nhất nếu có tồn tại vài TPI mà không có cùng mẫu mở rộng. 1 TPS không đồng nhất có thể cho kết quả từ 1 phép toán đại số giữa 2 TPS không t ương hợp. Tập toán tử được xác định để xử lý trên mẫu kết hợp của cả cấu trúc đồng nhất hoặc không đồng nhất. Điều này được xem xét trong 1 môi trường cơ sở dữ liệu hướng đối tượng khi những đối tượng phức tạp bị thao tác không cần thiết mà có cùng mẫu mở rộng. Do đó 2 toán hạng là sự tương thích thống nhất không cần thiết. 3.3- SỰ SO SÁNH KHOẢNG THỜI GIAN Thể hiện mẫu thời gian (TPI) biểu diển cho mẫu kết hợp mà có hiệu lực trong các khoảng thời gian khác nhau. Vì vậy TAA cần thao tác khoảng thời gian cũng như mẫu kết hợp phù hợp với ngữ nghĩa trong câu truy vấn khác nhau. Hầu hết sự tồn tại của đại số thời gian không hỗ trợ cho 1 đoạn liên tục của các phép toán so sánh thời gian. Ví dụ phép toán chọn thời gian (s - IFTP). Sử dụng 2 bộ định lượng khoảng thời gian cho thể hiện thời gian chọn lựa, cho tất cả vài để xác định 1 thể hiện đã có hiệu lực hay không qua toàn bộ khoảng thời gian cụ thể hoặc tại vài thời điểm trong khoảng. Trong ứng dụng thế giới thực có sự so sánh khoảng thời gian còn lại mà được yêu cầu. Ví dụ theo 2 yêu cầu câu truy vấn mà mối quan hệ thời gian giữa 2 khoảng thời gian được xác định : "Trình độ của những kỹ sư mà tham gia từ khi bắt đầu và rời khỏi trước khi dự án kết thúc" và "Kiếm tiền lương của John trước khi Tom lần đầu tiên trở thành giám đốc". Ngữ nghĩa của sự so sánh khoảng thời gian có thể cụ thể hoá bằng thuật ngữ của từ khoá trong ngôn ngữ truy vấn cấp cao (xem mục 4.1). TAA trình bày đa dạng sự so sánh khoảng thời gian bằng cách so sánh thời điểm bắt đầu và kết thúc của 2 khoảng thời gian mà có thể được xác định bởi 2 hàm thời gian s() và e(). Ví dụ "e(t1)
  9. LUAÄN VAÊN TOÁT NGHIEÄP thành những mẫu phức tạp hơn phù hợp với biểu thức ngữ nghĩa trong câu truy vấn. V í dụ sau trong mục này trình bày 3 phép toán lo ại này (hình 9). (1) T-Associate (* [R(A,B)]) . Toán tử này nhận dạng sự kết nối lẫn nhau giữa các đối tượng của 2 lớp A và B qua 1 mối liên kết cụ thể R(A,B) dựa trên dữ liệu được gán trong cả bộ nhớ chính hoặc cơ sở dữ liệu tồn tại lâu dài khi có nhiều hơn 1 mối liên kết giữa A và B. Điều này cần thiết được cụ thể qua những gì mà mối liên kết của phép toán kết hợp đã được định sẵn. Các phép toán này trả về tập của nguyên liên mẫu nối kết đối tượng thời gian A và B. a *[R(A,B)]b = g g = { tg k½ P(g k) = P(a i) P(b j) ambn, am Í P(a i), bn Í P( b j), ambn Ỵ P{R(A,B)}, T(g k) = T(a i) Ç t T(b j) ¹ 0} am là1 mẫu bên trong P(a i ) và bn là 1 mẫu bên trong P(b j). g k được xây dựng bởi mối liên kết giữa 2 TPI a i và b j nếu nó được kết nối trong cơ sở dữ liệu được lưu trữ qua 1 liên mẫu ambn mà có 1 mối liên kết R(A,B) trong 1 khoảng thời gian chung T(g k). Khi mỗi TPI được biểu diển bởi 1 tập nguyên mẫu thời gian không chứa đựng bản sao, g k là 1 tập nguyên mẫu được xây dựng bởi việc thực hiện phép hội của a i và b j và ambn trong 1 khoảng thời gian chung T(g k) mà kết quả từ khoảng thời gian hội (Ç t) giữa khoảng thời gian của a i (nghĩa là T(a i)) và b j (T(b j)). tg k hợp nhất khoảng thời gian gần kề mà có khuôn mẫu kết hợp giống hệt nhau (2) T-Complement(½ [R(A,B]). Toán tử T-Complement xác định tất cả các cặp đối tượng trong các lớp A và B mà không kết hợp qua mối liên kết cụ thể R(A,B). Kết quả là 1 tập khuôn mẫu bổ sung thời gian. Một đối t ượng trong A có thể được kết hợp với 1 vài đối tượng trong B nhưng không được kết hợp với 1 đối t ượng cụ thể nào trong B. Sự không kết hợp của cặp này được bao gồm trong kết quả. Nó có ích để thể hiện truy vấn chẳng hạn "Tìm kiếm những kỹ sư mà không thuộc về mỗi 1 phòng". a ½ [R(A,B)]b = g g = {g k½ P(g k) = P(a i) P(b j) C(ambn), am Í P(a i), bn Í P( b j), C(ambn)Ỵ P{R(A,B)}, T(g k) = T(a i) Ç t T(b j) ¹ 0} Trong trường hợp đặc biệt này khi a (hoặc b ) rỗng hoặc không có thời gian bên trong mẫu (Ví dụ không có thể hiện nào thỏa điều kiện chọn lựa), tất cả mẫu bên trong thời gian của b (hoặc a ) đưọc muợn trong kết quả TPS hình thành mối liên kết bổ sung thời gian với null OIDS. Ví dụ hình 3, chúng ta giả sử rằng TPS của Engineer là rỗng thì kết quả của mối liên kết bổ sung thời gian là :{{[5,9]C(en0d1)},({[10,24]C(en0d1)}, {[25,n]C(en0d1)},{[5,24]C(en0d2)},{[25,n]C(en0d2)}, với 0 biểu thị 1 null OID. Bộ xác định lớp "en" cho Engineer thì vẫn là 1 phần của IID và do đó phạm vi mẫu được bảo toàn. T-Complement thì tương đương tích Đề Các của 2 tập đối tượng trong cặp của các lớp trừ đi kết quả của a *[R(A,B)]b . Do đó nếu TAA chứa đựng 1 toán tử tích Đề Các. T-Complement sẽ không có toán tử nguyên thủy. Tuy nhiên, 1 phép toán tích Đề Các sẽ luôn luôn tạo cặp đối tượng vô nghĩa mà không phản hồi sự kết hợp đối tượng thế giới thực và tận dụng hết thời gian để hiện thực. Do đó, chúng ta có sự chọn lựa sử dụng các toán tử này và những toán tử còn lại có ý nghĩa hơn thay cho tích Đề Các. Chú ý rằng toán tử T-Complement có ngữ nghĩa khác biệt từ toán tử T-Nonassociate cho đến các toán tử kế tiếp. Trang 9
  10. LUAÄN VAÊN TOÁT NGHIEÄP Lớp đối tượng, như Engineer và Project A,B Tập các lớp, như W = {Engineer, Dept} W,X,Y,Z Mối liên kết giữa lớp A và B. R là tên của mối liên kết cụ thể nối 2 lớp R(A,B) R(Engineer,Dept). Mối liên kết đa hướng có thể được nối kết giữa 2 lớp Một tập nguyên mẫu thời gian tr ình bày tất cả sự kết hợp và không kết hợp {R(A,B)} giữa thể hiện A và mối liên kết R B qua {R(Engineer,Work_On}={{[0,12]en1w1},{[13,20]C(en1w1)},{[13,20]en1 w2},{[21,n]en1w1},{[21,n]C(en1w2}} P{R(A,B)} Phần mẫu kết hợp của {R(A,B)}. Ví dụ : P{R(Engineer,Work_On}} ={{en1w1},{C(en1w1)},{en1w2},{en2w2},{C(en2w2)}} a , b , g , w Mỗi TPS mà chứa đựng 1 tập của các TPI TPI của a , b , g , 1£ i, j, k £ n, ví dụ nếu a ={{[0,12]en1w1}, a i, b j, g k {[21,n]en1w1}} thì a 1 = {[0,12]en1w1}, a 2 = {[21,n]en1w1} Tập mẫu kết hợp của a , nghĩa là phần dữ liệu của tất cả những TPI trong a P(a ) Một phần mẫu kết hợp của a i. Cho a i ={[0,12]en1w1,[0,12]w1pj1}, P(a P(a i) i)={en1w1,w1pj1}, do đó P(a i) Ỵ P(a ) Một phần mẫu kết hợp của w , 1 £ e £ n, với các lớp được cụ thể bởi W. Ví P(w e) dụ : nếu W ={Work_On,Project} và w = {{[0,n]w1pj1}, {[15,n]w2pj1}} thì P(w 1)={w1pj1} và P(w 2)={w2pj1} Khoảng thời gian, như [9,25], [0,n] T Khoảng thời gian của a 1, nếu a i ={[0,12]en1w1,[0,12]w1pj1} thì T(a T(a i) i)=[0,12] Tập toán tử thời gian : thời gian giao, thời gian hội, thời gian hiệu; [5,10] Ç Ç t, t, -t t [8,12]=[8,10]; [5,10] t [8,12]=[5,12]; [5,10] t [11,15]=[5,15] và [5,10]-t [8,12]=[5,7] Toán tử tập con thời gian, ví dụ nếu T=[2,5] và T(g k)=[2,10] thì TÍ t T(g k) Í t, Ì (3) T-Nonassociate (![R(A,B)]). Toán tử T-Nonassociate xác định tất cả các cặp đối tượng trong 2 lớp cụ thể A và B. Một đối tượng của 1 lớp trong 1 cặp không có những mối quan hệ thời gian với đối tượng của lớp còn lại qua mối liên kết cụ thể R(A,B) trong vài khoảng thời gian. Do đó tạo ra kết quả là 1 tập mẫu bổ sung thời gian. Toán tử giữ được ngữ nghĩa truy vấn chẳng hạn như "Những kỹ sư đã không làm việc trong những phòng mà không có kỹ sư ". a ![R(A,B)]b ={(a i- [P(a i)](a i*[R(A,B)] b j)) ½ [R(A,B)] (b j- [P(a i)](a i*[R(A,B)] b j))} Biểu thức trên bao gồm 1 toán tử T-Complement (½ ) và 2 khoá. Mỗi khoá chứa đựng 1 toán tử T-Project( ) và 1 toán tử T_Difference(-). Trong khoá thứ 1, [P(a i)](a i*[R(A,B)] b j) xác lập tất cả TPI của a mà kết hợp với những TPI của b . Sau đó, 1 toán tử T-Difference loại bỏ những TPI này từ a , do đó chỉ giữ lại những TPI của a mà không nối kết với những TPI của b . Cùng thủ tục thực hiện cho b rồi thì toán tử T-Complement (½ ) xác định mối liên kết bổ sung giữa những TPI được giữ lại của a và b qua quan hệ R(A,B). Vì vậy T-Nonassociate không phải là phần gốc. Tuy nhiên các phép toán này rất có ích cho phương pháp truy vấn do đó được bao gồm trong tập các toán tử TAA. Trường hợp đặc biệt đã được mô tả trước đây trong phép toán T- Complement thì tương đương trong phép toán T-Nonassociate. Ví dụ phép toán sau trình bày các phép toán của 3 toán tử định dạng khuôn mẫu trên và hình 9 mô tả chúng bằng đồ thị. Trang 10
  11. LUAÄN VAÊN TOÁT NGHIEÄP Ví dụ : a là TPS tạo bởi thể hiện Engineer và b là TPS tạo bởi thể hiện Dept của T[5,n]. Theo hình 3 : a= {{[5,24]en1}, {[25,n]en1}, {[5,9]en2}, {[10,24]en2}, {[25,n]en2}} b= {{[5,9]d1}, {[10,24]d1}, {[25,n]d1}, {[5,24]d2}, {[25,n]d2}} thì : (1) a *[R(Engineer,Dept)]b = {{[5,24]en1d1}, {[10,24]en2d1}, {[25,n]en2d2}} (2)a ½ [R(Engineer,Dept)]b ={{[5,9]C(en2d1)}, {[5,9]C(en2d2)}, {[10,24]C(en2d2)}, {[25,n]C(en2d1)}, {[25,n]C(en1d1)}, {[5,24]C(en1d2)}, {[25,n]C(en1d2)}} (3) a ![R(Engineer,Dept)]b = {{[25,n]C(en1d1)}, {[5,9]C(en2d2)}} Đường đứt nét biểu thị mối liên kết bổ sung thời gian. Chú ý rằng, trong phép toán T - Nonassociate, không có mối liên kết bổ sung tạo thành giữa {[5,9]en2} và {[5,9]d1} bởi vì d1 được kết hợp với en1 trong {[5,9]en1d1}. T ương tự, không có mối liên kết bổ sung được tạo giữa {[25,n]en2} và {[25,n]d1}. Toán t ử T-Complement(½ ) giữ được ngữ nghĩa của "tất cả các cặp không kết hợp của những TPI của 2 lớp". Trong khi toán tử T -Nonassociate(!) giữ được ngữ nghĩa của "các cặp không kết hợp của những TPI, mỗi phần trong 1 cặp không có sự kết hợp với 2 TPI của lớp còn lại". Do đó, kết quả sau đó là tập con của kết quả trước đó. 3.5.2- SỰ THAO TÁC MẪU Toán tử thao tác khuôn mẫu thì tương tự toán tử đại số quan hệ ngoại trừ : (1) Một vài toán tử cho phép liệt kê mẫu của sự kết hợp đối tượng trong các phép toán để chắc rằng các tính chất ngữ nghĩa không bị mất trong quá trình xử lý. (2) Tất cả các toán tử có thể xử lý trên TPS đồng nhất cũng như không đồng nhất (3) Khoảng thời gian thao tác là 1 phần ngữ nghĩa của các phép toán này. (1) T-Join ( [W]). T-Join nối kết 1 cặp TPI. Lấy 1 từ mỗi 2 toán hạng TPS cụ thể, nếu 2 TPI có mẫu con chung được cụ thể bởi W và khoảng thời gian chồng lên nhau của chúng (nghĩa là chia sẽ 1 khoảng thời gian hoặc thời điểm chung). Các phép toán này thực hiện ngữ nghĩa của 1 nhánh AND cụ thể trong đồ thị truy vấn (hình 4). Ví dụ 1 TPS được hình thành bởi (Engineer*Work_On) có thể được nối kết với (Work_On*Project) bởi T-Join theo Work_On để hình thành 1 TPS phức tạp hơn mà bao gồm mẫu (Engineer*Work_On*Project). Mẫu này có thể thực hiện nối kết bằng toán tử T-Join trở lại với (Engineer*Dept) theo Engineer để hiện thực đồ thị truy vấn như hình 4. Trong cách xử lý này, cấu trúc cây phức tạp và cấu trúc mạng với nhánh Trang 11
  12. LUAÄN VAÊN TOÁT NGHIEÄP AND được diễn đạt trong ngôn ngữ truy vấn theo mẫu cơ bản có thể được tiến hành. T-Join thì tương đương với phép nối thời gian quan hệ ngoại trừ T-Join liên quan đến cặp TPI mà có thể có cấu trúc rất phức tạp được tạo bởi rất nhiều lớp thay vì cặp cố định của 2 quan hệ thời gian. Hơn nữa, W có thể là 1 mẫu con phức tạp với mối quan hệ kết hợp và không kết hợp mà không thể diễn đạt bởi phép nối quan hệ. Ở đây ta chú ý rằng các phép toán này thì khác với phép toán T-Associate (*) trong ngữ nghĩa lẫn chức năng. Mẫu trước đây nối với liên nguyên mẫu thời gian được đồng nhất bằng mẫu sau này để tạo ra 1 đường thông duyệt (cấu trúc tuyến tính) và cấu trúc phức tạp (cấu trúc cây và mạng nối với nhánh AND) giữa các thể hiện thời gian. a [W]b =g g ={g k½ P(g k) = P(a i) P(b j), P(w e) Í (P(a i) Ç P(b j) ¹ 0), T(g k) = T(a i) Ç t T(b j) ¹ 0} Biểu thức P(g k) = P(a i) P(b j) biểu diễn cho sự nối mẫu của a i và b j. Biểu thức P(w 1) Í (P(a i) Ç P(b j) ¹ 0) cụ thể rằng 1 mẫu con chung cho cả 2 TPI. Ví dụ dưới đây trình bày mẫu phức tạp được tạo ra như thế nào bởi phép toán T-Join. Ví dụ : a là TPS được tạo ra bởi (Employee*Engineer*Work_On) của T[15,n]. b là TPS được tạo ra bởi (Engineer*Dept) của T[15,n]. Theo hình 3 : a= {{[21,n]e1en1,[21,n]en1w1}, {[21,n]e1en1,[21,n]en1w2}, {[15,20]e2en2,[15,20] en2w2}} b= {{[15,24]en1d1}, {[15,24]en2d1}, {[25,n]en2d2}} thì : g = a [W]b = {{[21,24]e1en1,[21,24]en1w1,[21,24]en1d1}, {[21,24]e1en1,[21,24]en1w2,[21,24]en1d1}, {[15,20]e2en2,[15,20]en2w2,[15,20]en2d2}} (Employee*Engineer*Work_On) là ngôn ngữ cấp cao OQL/T biểu diễn của (Employee*Engineer) [(Engineer)](Engineer*Work_On). Hình 10 trình bày bằng đồ thị phép toán T-Join. T-Join có phép đảo và phép kết hợp điều kiện như trình bày dưới : a [W]b = b [W]a (Comm.) (a [W’]b ) [W’’]g = a x [W’](b y [W’’]g z) (Assn.) (nếu (w1 - w’’) Ç z = 0 và (w’’ - w’) Ç x = 0) Sự kết hợp không phải luôn đúng bởi vì có trường hợp mà 1 mẫu của b (biểu diễn bởi y) mà không đủ để phù hợp với những mẫu trong g (biểu diễn bởi z), có thể thành công bởi phép giao lần đầu với 1 mẫu trong a (biểu diễn bởi z) trong phép toán [w’] và rồi thực hiện phép giao với 1 mẫu g trong phép toán [w’’] (2) T-OJoin (¨ [W]). T-OJoin là tương tự phép nối bên ngoài quan hệ. Phép nối (T-Join) các TPI của 2 toán hạng TPS nếu nó chia sẽ cùng khuôn mẫu con được cụ thể bởi W. Thêm nữa, nó cũng bao gồm các TPI của 1 toán hạng mà chứa đựng khuôn mẫu con cụ thể bởi W, nhưng không có TPI tương ứng trong toán hạng còn lại mà chứa đựng cùng mẫu con. Phép toán này thực hiện ngữ nghĩa của 1 nhánh được cụ thể trong 1 đồ thị truy vấn. Ví dụ hình 3, 1 TPS được tạo bởi (Engineer*Work_On*Project) có thể T-OJoin với (Engineer*Dept) theo Engineer để tạo Trang 12
  13. LUAÄN VAÊN TOÁT NGHIEÄP ra 1 TPS phức tạp hơn với 1 nhánh OR mà cụ thể "Những kỹ sư mà làm việc trên 1 số dự án hoặc thuộc 1 số phòng". a¨b=g g ={g k ½ (1) g k Ỵ (a ¨ [W]b ) hoặc (2) P(w e) Í (P(g k) = P(a i)), T(g k) Í T(a i) hoặc (3) P(w e) Í (P(g k) = P(b j)), T(g k) Í T(b j)} Biểu thức (1) biểu diễn 1 kết quả TPI từ 1 T-Join. Biểu thức (2) và (3) biểu diễn những phần thời gian của a i vàb j, như kết quả của 1 phép toán T-Join mà khoảng thời gian không chia sẻ 1 khoảng thời gian chung (g 1, g 3, g 4, g 5 hình 11). Những tính chất này được mô tả theo ví dụ sau bằng đồ thị trong hình 11. Ví dụ : a là giống a dùng T-Join với Work_On[work_no="1"] được chọn và b giống như b dùng T-Join, theo hình 3 và hình 10 : a= {{[21,n]e1en1,[21,n]en1w1}} b= {{[15,24]en1d1}, {[15,24]en2d1}, {[25,n]en2d2}} thì : g =a ¨ [(Engineer)]b = {{[15,20]en1d1}, {[21,24]e1en1,[21,24]en1w1,[21,24]en1d1}, {[25,n] e1, en1,[25,n]en1w1}, {[15,24]en2d1},{[25,n]en2d2}}. Phép toán T_OJoin giữa kết quả a 1 và b 1 trong phép nối (T-Join) 1 TPI (là g 2) và 2 TPI thêm vào (là g 1 và g 3) mà không có đoạn thời gian tương ứng trong TPI còn lại. Ngoài ra, b 2 và b 3 được bao gồm trong kết quả như g 4 và g 5 từ khi chúng không làm phù hợp với những TPI trong a . T-OJoin thì bao gồm phép đảo và phép kết hợp điều kiện. (Xem lại phần điều kiện của T-Join) (3) T-Select (d [b ]). T-Select trích những TPI từ 1 toán hạng TPS mà thỏa biểu thức Boolean biểu thị bởi b . Biểu thức Boolean thì được đánh giá đối với mỗi TPI. Nếu kết quả đánh giá là đúng, TPI được bao gồm trong kết quả cuả TPS. d [b ](a ) = g g = {g k ½ g k = a k nếu b (a k) = true}. Ở đây, b (a k) có thể là : (1) So sánh giữa 2 thuộc tính (hoặc giữa 1 thuộc tính và 1 giá trị cụ thể). (2) Kiểm tra của sự nối kết giữa 2 thể hiện (nghĩa là sự kết hợp (*) hoặc không kết hợp (!)). (3) So sánh của 2 khoảng thời gian chẳng hạn T1 Í t T2, (T1 Í t T2) ¹ 0 và e(T1) < s(T2) (đề cập ở mục 3.3). Ví dụ : a là kết quả của phép toán T-Join, theo hình 3 và hình 10 : a= {{[21,24]e1en1,[21,24]en1w1,[21,24]en1d1}, {[21,24]e1en1,[21,24]en1w2,[21,24]en1d1}, {[15,20]e2en2,[15,20]en2w2,[15,20]en2d2}}, thì : g = d [T(a i) t (16,19]^[en2*d2)](a ) = {{[15,20]e2en2,[15,20]en2w2,[15,20]en2d2}} Kết quả trình bày rằng chỉ a 3 thỏa tất cả điều kiện chọn lựa. Phép toán trên trình bày bằng đồ thị hình 12. Biểu thức b so sánh khoảng thời gian phức tạp hơn sẽ trình bày mục 4.2. Trang 13
  14. LUAÄN VAÊN TOÁT NGHIEÄP (4) T_Project( [W,T]). T-Project trích mẫu con hoặc 1 khoảng thời gian liên quan hoặc cả 2 từ những TPI của 1 toán hạng TPS. Mẫu con và khoảng thời gian được xác lập cụ thể bởi W và T. Trong TAA, toán hạng TPS có thể là không đồng nhất và phép toán T-Project có thể thường trích cấu trúc đồng nhất từ cấu trúc không đồng nhất. [w,T](a ) = g g = { tg k ½ P(g k) Í P(a i), P(g k) Ỵ P(w ), T(g k) Í t T} Phép toán này có thể tạo những TPI mà thời gian hiệu lực thì gần kề nhau hoặc chồng lên nhau. Khoảng thời gian này có thể được hợp nhất bởi tg k để duy trì ngữ nghĩa thời gian (tham khảo lại mục 3.4). Ví dụ : a thì giống như a được dùng trong T-Select trên. Theo hình 3 và 12 : a= {{[21,24]e1en1,[21,24]en1w1,[21,24]en1d1}, {[21,24]e1en1,[21,24]en1w2, [21,24]en1d1}, {[15,20]e2en2,[15,20]en2w2,[15,20]en2d2}} thì : g = [(Employee,Dept),[22,24]]½ (a ) = {{[22,24]D(e1d1)}}. Hình 13 trình bày bằng đồ thị phép toán trên. Kết quả TPI từ a 1 và a 2 được t ìm thấy giống nhau và do đó nó được hợp nhất vào g 1 . T-Project đã được tạo 1 liên mẫu dẫn xuất mà kiểm soát kết quả của 1 câu truy vấn mà sự kết nối lẫn nhau giữa những thể hiện đối t ượng là "gián tiếp" và sự giải thích chính xác của những liên mẫu dẫn xuất sẽ phải bao gồm cấu trúc mà đã được xác lập. Một hệ quản trị cơ sở dữ liệu (DBMS) thời gian nên giữ dấu của cấu trúc và kết hợp nó với kết quả của 1 T-Project để mà không mất ngữ nghĩa gốc. Ví dụ, nếu 1 kỹ sư en1 được kết hợp với phòng d1 và d1 được kết hợp với dự án pj1 mà là kết quả của 1 phép chiếu quan hệ đúng cách trên Engineer và Project. Nhưng nếu kết quả phép chiếu là 1 đồ thị với liên mẫu dẫn xuất, nó sẽ không bị suy luận sai. Liên mẫu dẫn xuất được duy trì bởi bộ xử lý truy vấn và cho người sử dụng nhận được dữ liệu xuất ra. (5) T-Union(+). T-Union xây dựng 1 TPS chứa đựng tất cả TPI mà xuất hiện trong 1 hoặc cả 2 của 2 toán hạng TPS. Những TPI trong kết quả của TPS mà các mẫu thì giống hệt nhau và khoảng thời gian thì gần nhau hoặc chồng lên nhau thì được kết nối vào 1 khoảng thời gian duy nhất bởi 1 phép toán hợp nhất thời gian. Khái quát, T-Union thì tương đương với phép toán quan hệ hội áp dụng cho cơ sở dữ liệu thời gian. Tuy nhiên, những toán hạng không phải là tương hợp. a+b=g g = { tg k ½ g k Ỵ a hoặc g k Ỵ b } Ví dụ sau tr ình bày 1 phép toán giữa 2 tập toán hạng đồng nhất nhưng không tương hợp. Hình 14 trình bày phép toán trên bằng đồ thị. Ví dụ : a là TPS được tạo bởi (Employee*Engineer*Work_On[Work_no = "1"]) của T[15,n]. Theo hình 3 : a= {{[15,24]e1en1,[15,24]en1d1}, {[15,24]e2en2,[15,24]en1d1]}} b= {{[21,n]e1en1,[21,n]en1w1}} thì : g=a+b= {{[21,n]e1en1,[21,n]en1w1}, {[15,24]e1en1,[15,24]en1d1}, {[15,24] e2en2,[15,24]en2d1}}. Trang 14
  15. LUAÄN VAÊN TOÁT NGHIEÄP Phép toán T-Union trên liên kết tất cả các TPI của 2 toán hạng để tạo 1 TPS không đồng nhất. Trong ví dụ này, ta giả sử rằng dept_no ="1" và work_no="1" xác định bộ nhận dạng thể hiện d1 và w1. (6) T-Intersect(· ).T-Intersect tạo ra 1 TPS chứa tất cả các TPI mà xuất hiện trong cả 2 TPS cụ thể trong vài khoảng thời gian chung. Đó là 1 phép toán tập giao dựa trên 2 tập mẫu thời gian. a·b=g {g k½ P(g k) Ỵ P(a ) và P(g k) Ỵ P(b ), g= T(g k) = T(a i) Ç T(b j) với P(a i) = P(b j)} Ví dụ : a là kết quả của T-Union trên. b là TPS được tạo bởi (Employee*Engineer*Work_On) của T[15,24]. Theo hình 3 và hình 14 : a= {{[21,n]e1en1,[21,n]en1w1}, {[15,24]e1en1,[15,24]en1d1}, {[15,24]e2en2, [15,24]en2d1}} b= {{[21,24]e1en1,[21,24]en1w1}, {[21,24]e1en1,[21,24]en1w2}, {15,20]e2en2, [15,20] en2w2}} thì g = a · b = {{[21,24]e1en1,[21,24]en1w1}}. Hình 15 trình bày bằng đồ thị phép toán trên. Khi chỉ a 1 và b 1 chứa đựng cùng mẫu {e1en1,en1w1} và có 1 kho ảng thời gian chung [21],[24]. TPI được bao gồm trong kết quả. (7) T-Difference(-).Toán tử T-Difference loại trừ tất cả các TPI của toán hạng TPS thứ 1 nếu cùng khuôn mẫu xuất hiện trong toán hạng TPS thứ 2 trong vài khoảng thời gian hiệu lực chung. Giống như T-Union và T-Intersect, phép toán này có thể xử lý trên những toán hạng mà có cùng cấu trúc đồng nhất hoặc không đồng nhất và sự tương hợp giữa các toán hạng thì không yêu cầu. a-b=g g= {g k½ P(g k) = P(a i), T(g k) = T(a i) với P(a i) P(b ), T(g k) = T(a i)-T(b j) với P(a i) = P(b j)} Điều kiện trong khoá thứ 2 biểu diễn cho 1 mẫu của 1 TPI trong a mà không tồn tại trong b , và điều kiện trong khoá thứ 3 biểu diễn cho 1 mẫu giống hệt tồn tại trong cả a và b . Ví dụ : a giống như a trong T-Intersect, b giống như b trong T-Intersect, Theo hình 3 và hình 15 : a= {{[21,n]e1en1,[21,n]en1w1}, {[15,24]e1en1,[15,24]en1d1}, {[15,24]e2en2, [15,24] en2d1}} b= {{[21,24]e1en1,[21,24]en1w1}, {[21,24]e1en1,[21,24]en1w2}, {[15,20]e2en2, [15,20]en2w2}} g=a-b= {{[25,n]e1en1,[25,n]en1w1}, {[15,24]e1en1,[15,24]en1d1}, {[15,24] e2en2,[15,24]en2d1}} Khi TPI a 2 và a 3 không xuất hiện trong b và chỉ T[25,n]của a 1 còn lại sau phép trừ 1 khoảng thời gian giữa a 1 và b 1, nó bao gồm trong kết quả của TPS. Phép toán này trình bày bằng đồ thị hình 16. Trang 15
  16. LUAÄN VAÊN TOÁT NGHIEÄP (8) T-Divide(¸ [W]). T-Divide xác định 1 nhóm TPI với 1 cấu hình dữ liệu chung cụ thể (là mẫu con) trong TPS toán hạng đầu tiên mà chứa tất cả TPI trong toán hạng TPI thứ 2. Mẫu con chung được cụ thể bởi 1 tập các lớp biểu thị bởi W. Sau đó, mẫu con chung được trích ra từ những TPI được tuyển chọn bởi T-Project. Nếu W không được cụ thể, phép toán vẫn giữ lại tất cả các TPI của toán hạng TPS đầu tiên, mỗi toán hạng chứa đựng ít nhất 1 TPI của b và chúng cùng chứa tất cả các TPI của b (T-Project không liên quan). a ¸ [W]b = [W](g s) a s là 1 tập con của những TPI của a mà có mẫu con chung mà các lớp được cụ thể trong W và cùng chứa tất cả TPI của b . T-Project trích ra mẫu con. Ví dụ : a là TPS tạo bởi (Employee*Engineer*Work_OnProject) của T[15,n] b là TPS được tạo bởi (Project) của T[25,n] Theo hình 3 : a= {{[21,n]e1en1,[21,n]en1w1,[21,n]w1pj1}, {[21,n]e1en1,[21,n]en1w1,[21,n]w1pj2}, {[21,n]e1en1,[21,n]en1w2,[21,n]w2pj1}} b= {{[25,n]pj1}, {[25,n]pj2}} g s= {{[25,n]e1en1,[25,n]en1w1,[25,n]w1pj1}, {[25,n]e1en1,[25,n]en1w1,[25,n]w1pj2}, {[25,n]e1en1,[25,n]en1w2,[25,n]w2pj1}}, thì : a ¸ [Employee,Engineer}]b = [{Employee,Engineer}](g s) = {{[25,n]e1en1}}. Phép toán trên được trình bày bằng đồ thị hình 17. Khi TPI a 1, a 2, a 3 có mẫu con cụ thể chung {e1en1} và cùng chứa tất cả TPI trong b (nghĩa là b 1 và b 2) trong khoảng thời gian chung [25,n], TPI {[25,n]e1en1} được xác định như kết quả của [{Employee,Engineer}] biểu hiện "công nhân e1, cùng với kỹ sư en1 làm việc trên tất cả dự án (pj1 và pj2) trong thời gian T[25,n]". 3.5.3- THAO TÁC KHUÔN MẪU MÀ KHÔNG TÍNH ĐẾN THỜI GIAN Trong xử lý câu truy vấn thời gian, các toán tử đại số thể hiện c ơ bản (do đó không liên quan đến thời gian) có ích để xử lý câu truy vấn thời gian mà gồm nhiều mẫu thời gian, mà không quan tâm đến thời gian xảy ra đồng thời. Ví dụ, câu truy vấn chẳng hạn "Tìm kiếm những kỹ sư mà tham gia trong những dự án trong thời gian T[5,30] và thuộc phòng trong thời gian [20,n]", "Tìm kiếm những kỹ sư mà làm việc trong những dự án trong thời gian T[0,20] hoặc không phụ thuộc những phòng trong thời gian T[0,25]" và "Tìm kiếm những kỹ sư mà làm việc trên 1 dự án trong thời gian T[21,n] nhưng không thuộc những phòng trong thời gian T[0,20]", sở hữu ngữ nghĩa của phần giao không liên quan thời gian, phần hội không liên quan và phần hiệu không liên quan thời gian. TAA giữ những ngữ nghĩa này 1 cách rõ ràng bởi 3 toán tử đại số không liên quan thời gian. Ví dụ hình 18 : (1) NT-Intersect( ° [W]).NT-Intersect xây dựng 1 TPS chứa tất cả các TPI mà có 1 mẫu con chung được cụ thể trong W và những khuôn mẫu kết hợp mà xuất hiện trong cả 2 toán hạng TPS, mà không kiểm tra khoảng thời gian. a ° [W]b = g g = { tg k½ g k Ỵ a và g k Ỵ b , P(w e) Í P(g k)} Mặc dù, phép toán không xác đ ịnh sự cụ thể thời gian của những TPI, những thể hiện đồng hoá mang mẩu và chi tiết thời gian của chúng. Kết quả của những TPI với khoảng thời gian gần nhau hoặc gối chồng lên nhau thì được hợp nhất bởi tg k để duy trì tính chất ngữ nghĩa của khoảng thời Trang 16
  17. LUAÄN VAÊN TOÁT NGHIEÄP gian được bàn trong mục 3.4. NT-Intersect thì có phép đảo và phép kết hợp điều kiện (tham khảo lại T-Join cho phần điều kiện). (2) NT-Union ( [W]). NT-Union xây dựng 1 TPS chứa tất cả các TPS mà có 1 mẫu con cụ thể W và mẩu kết hợp mà xuất hiện trong cả 2 toán hạng TPS mà không kiểm tra khoảng thời gian cua chúng . a [W]b = g g = { tg k½ g k Ỵ a hoặc g k Ỵ b , P(w e) Í P(g k)} Kết quả của TPS với khoảng thời gian gần kề và gối chồng lên nhau thì được hợp nhất bởi tg k để duy trì tính chất ngữ nghĩa khoảng thời gian. NT -Union thì có phép đảo và phép kết hợp điều kiện (xem lại T-Join cho phần điều kiện). (3) NT-Difference( [W]).NT-Difference xây dựng 1 TPS chứa tất cả những TPI mà có 1 mẫu con chung được cụ thể bởi W và mẫu kết hợp mà xuất hiện trong toán hạng thứ 1 nhưng không có trong toán hạng thứ 2 mà không kiểm tra khoảng thời gian. a b=g g = { tg k½ g k Ỵ a và g k b , P(w e) Í P(g k)} Ví dụ sau mô tả các phép toán của 3 toán tử không liên quan thời gian trên. Hình 18 mô tả chúng bằng đồ thị. Ví dụ : a là kết quả của T-Union trình bày trong hình 14. b là TPS được tạo bởi (Employee[emp_no="1"]*Engineer*Work_On) của T[15,n] Theo hình 3 và hình 14 : a := {{[21,n]e1en1,[21,n]en1w1}, {[15,24]e1en1,[15,24]en1d1}, {[15,24]e2en2, [15,24]en2d1}} b := {{[21,n]e1en1, [21,n]en1w1}, {[21,n]e1en1, [21,n]en1w2}} thì : 1. a ° [{Employee,Engineer}]b = {{[21,n]e1en1, [21,n]en1w1}, {[21,n]e1en1,[21,n]en1w2}, {[15,24]e1en1,[15,24]en1d1}} (2) a [{Employee,Engineer}] b = {{[21,n]e1en1, [21,n]en1w1}, {[21,n]e1en1,[21,n]en1w2}, {[15,21]e1en1,[15,24]en1d1}, {[15,24]e2en2,[15,24]en2d1}} (3) a [{Employee,Engineer}]b = {{[15,24]e2en2,[15,24]en2d1}} Trong phép toán NT-Intersect, khi a 1, a 2, b 1, b 2 có 1 mẫu con chung {e1en1}, chúng được bao gồm trong kết quả. Chú ý rằng 2 TPI giống hệt nhau a 1 và b 1 được liên kết bởi tg k. Trong phép toán NT-Union mặc dù mẫu con {e2en2} của a 3 không xuất hiện trong những TPI của b , a 3 được giữ nguyên trong kết quả. Hai TPI giống hệt nhau a 1 và b 1 được liên kết bởi tg k. Trong phép toán NT-Difference, a 1 và a 2 được bao gồm từ kết quả khi mẫu con trong chúng (nghĩa là en1d1) xuất hiện trong b 1 và b 2. Chú ý rằng khoảng thời gian thì không được quan tâm trong phép toán này. Mối quan hệ ưu tiên của các toán tử trên theo thứ tự sau : d và có mức ưu tiên cao hơn toán tử nhị phân, và toán tử thời gian có mức ưu tiên cao hơn toán tử không liên quan thời gian. Mức ưu tiên của các tu nhị phân thời gian được sắp theo thứ tự sau :*, ½ , !, , ¨ , · , ¸ ,-,+. Thứ tự được chọn dựa trên ngữ nghĩa của các toán tử. Bảng 2 tóm tắt các tính chất của toán tử TAA. Trang 17
  18. LUAÄN VAÊN TOÁT NGHIEÄP 4.1- CÁC HÀM THỜI GIAN VÀ CÁC PHÉP TOÁN SO SÁNH THỜI GIAN Nói chung, ngôn ngữ truy vấn thời gian cấp cao cung cấp 1 số hàm thời gian có sẵn và các phép toán so sánh các ngữ nghĩa truy vấn thời gian để diễn đạt sự khác nhau. Những hàm và phép toán này có thể được dùng cùng với các toán tử đại số trong sự phân loại các dạng đại số của truy vấn thời gian cấp cao. Trong mục này, ta mô tả tóm tắt những hàm và phép toán thời gian xác định trong OQL/T[36]. Một vài đã được dùng trong truy vấn thời gian ở mục 4.2. (1) Hàm chi tiết khoảng thời gian (Interval Specification Functions) : Hàm trong loại này bao gồm INTERVAL, TIME(NOW+/-) và trả về thời gian hiệu lực của thể hiện thời gian. Khoảng thời gian có thể được cụ thể rõ ràng hoặc tuyệt đối. Ví dụ, trong câu truy vấn thời gian "Khôi phục lại lương của Mary khi cô ta đã là 1 giám đốc bán hàng". Miền thời gian của câu truy vấn này không được cụ thể rõ ràng. Hàm INTERVAL xác định khoảng thời gian tuyệt đối của câu truy vấn. Hàm TIME(NOW+/-) xác định thời điễm của thể hiện mẫu liên quan đến thời điểm hiện tại. (2) Các phép toán so sánh khoảng thời gian (Interval Comparison Operations) : Các phép toán so sánh khoảng thời gian có thể được dùng để xác định quan hệ thời gian giữa 2 khoảng thời gian rõ ràng / tuyệt đối. Cho 2 khoảng thời gian T1 và T2, OQL/T chi tiết 7 phép toán cơ bản so sánh khoảng thời gian T1 BEFORE T2 hoặc T2 AFTER T1, T1 PRECEDE T2 hoặc T2 FOLLOW T1, T1 P-CROSS hoặc T2 F-CROSS T1, T1 EQUAL T2, T1 L-CONTAIN hoặc T2 R-WITHIN T1. Ở đây, P thay cho PRECEDE, F thay cho FOLLOW, L thay cho LEFT, R thay cho RIGHT, O thay cho OUTER và I thay cho INNER. Ví dụ 1 câu truy vấn thời gian "Tìm kiếm lương của John khi hắn làm việc cho phòng mà có dept_no ="1" trước khi Mary lần đầu tiên trở thành giám đốc bán hàng" có thể được biểu diễn bởi 2 hàm INTERVAL và phép toán so sánh miền thời gian BEFORE trong OQL/T. Biểu thức đại số của nó được trình bày trong Q2 ở mục kế. Sự chuẩn hoá của những phép toán so sánh này dựa trên 2 hàm thời gian s() và e() đã được tóm tắt trong mục 3.3. (3) Hàm sắp thứ tự (Ordering Functions) : Hàm trong loại này bao gồm : FIRST, LAST, N-TH, B-FIRST (B thay cho "Backward"), B-LAST, B-NTH, FORMER, NEXT. Nó trả về thể hiện thời gian của dòng thời gian mà được sắp xếp dựa trên sự chi tiết khoảng thời gian. Ví dụ, trong câu truy vấn thời gian "Tìm kiếm lương khởi đầu của những kỹ sư mà làm việc trong dự án", người sử dụng quan tâm đến khoảng thời gian hiệu lực đầu tiên của tất cả thể hiện mẫu "Engineer-Project". (4) Hàm tính tổng (Aggregate Functions) : Hàm GROUP-BY nhóm những TPI mà được xác định có những mẫu con chung. Hàm COUNT đếm số tăng dần của 1 thể hiện mẩu được tập hợp lại. Nó được biểu thị bởi GROUP-BY (mẫu, (mẫu con)) và COUNT trong 1 biểu thức đại số. Thêm vào những hàm tính tổng thông thường, hàm tính tổng thời gian T-MIN, T-MAX, T- SUM, TC-SUM và T-AVG được xác nhận trong OQL/T. Nó thực hiện trên khoảng thời gian hiệu lực của tập thể hiện mẫu thời gian và trả về đoạn thời gian của những thể hiện mẫu khác nhau mà thỏa tính chất của hàm. TC-SUM trả về tổng của đoạn thời gian liên tục của những thể hiện mẫu được tập hợp lại. Trong khi T-SUM trả về tổng đoạn thời gian. T-MIN trả về khoảng thời gian ngắn nhất trong 1 dòng thời gian. Ví dụ, xử lý 1 câu truy vấn thời gian "Những phòng nào mà có những giám đốc mà công tác trong khoảng thời gian ngắn nhất ?". Hàm T-MIN có thể thực hiện trên thể hiện thời gian Dept mà có sự kết hợp Dept-Manager. (5) Phép toán cửa sổ thời gian (Time Window Operations) : OQL/T định nghĩa 2 phép toán trong loại này : ANY và EVERY. Nó trình bày về khái niệm cửa sổ trượt. Một cửa sổ thời gian là 1 giai đoạn thời gian mà di chuyển 1 bước cố định từ giới hạn thấp hơn đến giới hạn cao hơn của 1 khoảng thời gian. Trong ứng dụng cửa sổ trượt, những điều kiện trong 1 truy vấn thời Trang 18
  19. LUAÄN VAÊN TOÁT NGHIEÄP gian được xác định như là cửa sổ dịch trong khoảng thời gian đó. Ví dụ, 1 câu truy vấn thời gian "Tìm những phòng mà thay đổi trưởng phòng nhiều hơn 2 lần trong 1 năm từ năm 1976 đến 1990?" cần 1 phép toán về cửa sổ trượt. Những hàm / phép toán thời gian này cùng với những toán tử đại số thời gian hỗ trợ việc thi hành của cấu trúc ngôn ngữ truy vấn thời gian cấp cao. 4.2- VÍ DỤ VỀ PHÂN LOẠI ĐẠI SỐ Trong mục này cung cấp vài ví dụ để phân loại đại số của câu truy vấn cấp cao được diễn tả bằng ngôn ngữ OQL/T sử dụng các phép toán đại số của TAA và các hàm / phép toán về thời gian. Ta kiểm tra về các phép toán phù hợp và sự phân loại các phép toán của toán tử TAA và của các hàm thời gian dùng 1 số kiểu câu truy vấn được chọn. Có thể có biểu thức đại số chuyển đổi cho 1 câu truy vấn. Câu hỏi 2 : Tìm kiếm lương của John trong khi hắn ta làm việc cho phòng mà có dept_no = "1" trước khi Mary lần đầu tiên trở thành trưởng phòng. Biểu thức OQL/T : CONTEXT e 1:Employee WHEN i : INTERVAL(CONTEXT e 2 : Emp.*Eng.*d:Dept WHERE e 2.name = "John" and d.dept_no = "1") WHERE e 1.name = John and i BEFORE FIRST(INTERVAL(CONTEXT e 3 : Employee * Manager WHERER e 3.name = "Mary")) RETRIEVE e 1.salary Biểu thức đại số : s 1 = d [name=John](Employee) s 2 = d [dept_no=1](Dept) s 3 = (s 1*Engineer) ¨ [{Engineer}](Engineer*s 2 ) T1 = INTERVAL(s 3) s 4 = d [name=Mary](Employee) s 5 = s 4*Manager T2 = FIRST(INTERVAL(s 5)) s 6 = d [e(T1)
  20. LUAÄN VAÊN TOÁT NGHIEÄP s 5 = P [{Dept}](s 4) Tất cả thể hiện mẫu Dept_Manager mà được chọn trong s 1 và s 2 được tạo bởi T-Associate(*) và gán vào s 3, rồi T-MIN(s 3) xác định những TPI mà có khoảng thời gian hiệu lực ngắn nhất. Phép chiếu T-Project(P ) xảy ra sau tạo ra những phòng tương ứng với kết quả. Câu hỏi 4 : Tìm kiếm những kỹ sư mà tham gia vào dự án trong T[J5,20] làm trong phòng mà có dept_no ="8" trong T[30,40]. Biểu thức OQL/T : CONTEXT((CONTEXT Engineer*Work_On*Project WHEN T[5,20]° [{Engineer}] (CONTEXT Engineer*d:Dept WHEN T[30,40] WHERE d.dept_no = "8")) DISPLAY Engineer Biểu thức đại số : s 1 = P [[5,20]](Engineer) s 2 = P [[5,20]](Work_On) s 3 = P [[5,20]](Project) s 4 = (s 1*s 2) [{Work_On}](s 2 *s 3) s 5 = P [[30,40]](Engineer) s 6 = d [T(d1) t[30,40]^dept_no=8](Dept) s 7 = P [[30,40]](s 6) s 8 = s 5*s 7 s 9 = s 4° [{Engineer}]s 8 s 10 = P [{Engineer}](s 9) Ví dụ này mô tả 1 sự phân loại đại số của 1 phép toán không quan tâm về thời gian mà kết quả vẫn giữ nguyên tất cả các thể hiện kỹ sư mà thỏa 2 mẫu độc lập thời gian. Trang 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.09: Bộ Luận Văn Tốt Nghiệp Chuyên Ngành Quản Trị Kinh Doanh
81 tài liệu
1641 lượt tải
THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

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