Luận Văn Xử lý câu truy vấn bằng phép toán đại số kết hợp thời gian

TÊN ĐỀ TÀI: Xử lý câu truy vấn bằng phép toán đại số kết hợp thời gian​

Information

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.



PHẦN 1 :


ĐẠI SỐ KẾT HỢP THỜI GIAN


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. Diễ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 ứ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.