Xem mẫu
- 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
- 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
- LUAÄN VAÊN TOÁT NGHIEÄP
PHẦN 1 :
ĐẠI SỐ KẾT HỢP THỜI GIAN
Trang 3
- 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
- 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
- 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
- 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
- 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)
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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)
- 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
nguon tai.lieu . vn
