Bài giảng Cơ sở dữ liệu đa phương tiện - Chương 5: Trình diễn dữ liệu đa phương tiện - Nguyễn Thị Oanh

Nội dung text: Bài giảng Cơ sở dữ liệu đa phương tiện - Chương 5: Trình diễn dữ liệu đa phương tiện - Nguyễn Thị Oanh

1. Trình diễn dữ liệu ĐPT  Để có thể trình diễn DL, cần phải trả lời 3 câu hỏi: – WHAT ? – WHEN ? – WHERE ?  Khi đã có đáp án, Presentation Server phải tạo được 1 kế hoạch truy hồi (Retrieval Plan) để lấy được các đối tượng cần thiết. Lưu ý:  Khi nào đối tượng được trình diễn  Giới hạn về băng thông của đường truyền  Giới hạn về tài nguyên (bộ đệm) ở phía client và server 2  Không khớp giữa tốc độ truyền DL và tốc độ sử dụng DL
2. Trình diễn dữ liệu ĐPT 4
3. Trình diễn với r/buộc không gian  Chỉ rõ các đối tượng được sắp đặt thế nào trong không gian (2D) – O1 trình diễn bên trái O2 – O1 trình diễn phía trên O3 6
4. Ngôn ngữ mô tả ràng buộc  Hằng số : số nguyên  Biến: – Với 1 đối tượng oi, có 2 biến nguyên: thời điểm bắt đầu (si), thời điểm kết thúc (ei)  Số hạng cơ bản (Elementary terms): – Tất cả các hằng số – Tất cả các biến số 8
5. Định nghĩa  Trình diễn với ràng buộc thời gian (temporal presentation): T P = (O, DC) – O: tập các đối tượng, O = {o1, o2, , o3} – DC: tập các rằng buộc sai phân biểu diễn bằng ngôn ngữ mô tả ràng buộc trên các đối tượng thuộc O  Giải pháp (solution) của DC: gán các số nguyên cho các biến si, ei sao cho tất cả các ràng buộc trong DC đúng  1 DC có thể có 0, 1 hoặc nhiều giải pháp 10
6. Định nghĩa  TP = (0, DC) gọi là có thể thực thi được nếu và chỉ nếu DC có 1 giải pháp , : biểu thời gian (schedule) của TP start() = min({(si) | 1 i n}) end() = max({(ei) | 1 i n}) 12
7. Thuật toán Bell-Ford  Để tìm giải pháp hiệu quả cho trình diễn với ràng buộc thời gian  Bài toán quy hoạch tuyến tính với đk các biến nhận giá trị nguyên  Thuật toán Bell-Ford: – Đầu vào: tập các ràng buộc sai phân DC  Chuyển DC thành 1 đồ thị có trọng số GDC  DC có giải pháp nếu và chỉ nếu đồ thị không có chu trình âm  Tìm đường ngắn nhất đến mỗi nút – Ra: 1 giải pháp cho 14
8. Chuyển DC GDC Thêm 1 nút ảo start GDC= (V, E, w) V = {si, ei, i = 1 n} E: với mỗi x – y c 1 cạnh từ y sang x với w(y,x) = c cạnh từ start tới s , e , i = 1 n có trọng số 0 16 i i
9. Thuật toán  Mỗi nút N trên GDC có 2 trường: – Bestval(N): đường đi ngắn nhất từ start cho đến N – Bestpar(N): chỉ đến nút ngay trước N trên đường đi ngắn nhất từ start N  Đường đi ngắn nhất = đường đi có chi phí thấp nhất = tổng trọng số trên các cạnh là nhỏ nhất 18
10. Khởi tạo các giá trị Cập nhật lại các giá trị Bestval và Bestpar cho mỗi nút K/ tra xem có chu trình âm không ? 20
11. Ví dụ Sau lần lặp 1 Sau lần lặp 2 22
12. Trình diễn với r/buộc không gian 24
13. Ví dụ Y (Ri, Ui) (R , U ) voi j j vo (Xi, Yi) j (Xj, Yj) X Relationship Constraint voi is to the left of voj Ri – Xj 0 voi is to the right of voj Rj – Xi 0 voi is to above of voj Uj – Yi 0 voi is to below of voj Ui – Yj 0 Giải quyết tương tự cho bài toán trình diễn với ràng buộc thời gian 26