Luận án tiến sĩ toán học: Đặc tả, kiểm chứng hình thức và ứng dụng trong cơ sở dữ liệu thời gian thực

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (29.07 MB, 101 trang )

Trang 1<div class="page_container" data-page="1">

1.2 Điều khiển tương tranh trong CSDL ... 17

1.3. Các đặc điểm dữ liệu va giao tác của CSDL thời gian thực 19

1.4 Điều khiển tương tranh thời gian thực ... 23

</div>Trang 2<div class="page_container" data-page="2">

MÔ HÌNH HÌNH THỨC CỦA HỆ THỐNG CƠ SỞ DỮ

LIỆU THỜI GIAN THỤC TRONG LOGIC TÍNH TỐN

KHOẢNG 44

3.1 Mơ hình cđơsở...-..-. ee ees 44

3.2 Mơ hình tiến hành ...- 49

3.2.1 Mơ hình đơn bộ xử lý... 503.2.2 Mơ hình đa bộ xử lý... 5I

3.3. Các điều kiện đúng cho thực hiện song song của hệ thống

3.3.1 Khatuantu ... 523.3.2 Điều kiện nhất quán thời gian... 54

3.3.3. Một số điều kiện đủ cho việc duy tri tính nhất

Quan THƠI gÌHH psec cv ý ieee eRe ww c c 58

34 Kétluan ... 63

ĐẶC TẢ, KIỂM CHỨNG HÌNH THỨC GIAO THỨC

DIEU KHIỂN TƯƠNG TRANH VÀ UNG DỤNG TRONG

CƠ SỞ DU LIEU THỜI GIAN THỰC 64

S41 THỊNH [HỮU HH hie. sees eect eae eee wee ewe 65

4.2 Hinh thức hoa R/WPCP ... 66

4.3 Kiểm chứng hình thức giao thức R/WPCP... 7I

</div>Trang 3<div class="page_container" data-page="3">

4131 Nhà tein ti occ cee swe ieee lớn 2ì na ee 7I

4.3.2 Nghẽn nhiều nhất một lan của R/WPCP ... 7I

43.3 R/WPCP là không bế tắc... - 77

4.3.4 Chứng minh định lý về điều kiện lập lịch của

R/WPCP trong CSDL thời gian thuc... 77

4.4 Nghẽn cua R/WPCP trong môi trường da bộ xử lý .... 80

4.5 Ung dụng hệ thống cơ sở dữ liệu thời gian thực trong hệthống điều khiển giao thông hàng không... 81

KẾT LUAN...0. 000000 cece cence ees 90HƯỚNG PHÁT TRIEN ... 92

CÁC CƠNG TRÌNH ĐÃ CƠNG BỐ... 94

TÀI LIEU THAM KHẢO... 95

PHỤ LỤC... 103

</div>Trang 4<div class="page_container" data-page="4">

DANH MỤC CÁC TỪ VIET TAT

Số Viết tắt Diễn giải tiếng Anh Diễn giải tiếng Việt

1 ALE | Alert Detection Transac- | Giao tác phát hiện lỗi

tion |

2 BAP | Basic Aborting Protocol - Giao thức huỷ bỏ cơ sở ˆ

3 CSDL | Database Co sở dữ liệu |

4) DC | Duration Calculus [Logic tính tốn khoảng _

5 DDB | | Display Database | Cơ sở dữ liệu hiện thị

6 — DM. Data Manager Bộ quan trị dữ liệu

7 DOS Data Operator System Hệ thống thao tác dữ liệu

is | DT| Display Transaction | Giao tac hién thi

9 IL Interval Logic Logic khoảng _

10 | PCP-DA | Priority Ceiling Protocol Giao thức mức ưu tiên |

with Dynamic Adjust- cao nhất với điều chỉnh

ment of Serialization Or- | động của thứ tu khả tuần

. der | tự

NPL | Predicate Logic [Logic vi tr

| 12 RM_ Rate Monotonic . Thuật toán lập lịch xác

-1ng Protocol

| định mức ưu tiên theo

chu kỳ

R/WPCP | Read/Write Priority Ceil- iE Giao thức đọc/ghi- mức

ưu tiên cao nhất

14 | ST Sensor Transaction | Giao tác cam nhận

15 | TDB Target Database Co sở dữ liệu đích

14 | TM | Transaction Manager | Bộ quản tri giao tác

fee |

_ Two Phase LockingKhoa hai pha

</div>Trang 5<div class="page_container" data-page="5">

DANH SÁCH BANG

1.1 Các yêu cầu đặc trưng của CSDL thời gian thực

</div>Trang 6<div class="page_container" data-page="6">

DANH SÁCH HÌNH

Mơ hình CSDL thời gian thực... 19

Các ham giá trị của các kiểu giao tác thời gian thực ... 20

Nhất quán thời gian của dữ liệu... 21

Thực hiện của các giao tác dưới R/WPCP... 26

Thực hiện của các giao tác dưới BAP... 28

Thực hiện của các giao tác dưới PCP-DA ... 31

Đồ thị thể hiện các biến trạng thái... 47

D0 YLHiiiB TH IGG gee eee eee ee ee 57Thực hiện cập nhật của giao tac cảm nhận ... 59

Duy ti TẤT QUẦN : ¡ ¿ vẽ cee wes ewes HES ee HH 61Lich cua R/WPCP trong môi trường đa bộ xrly... 80

Mô hình hệ thống CSDL thời gian thực trong điều khiển giaothơng hang KHƠNH ¿ : ¿ keke eee RH SLED ER EME RE SS 82Thực hiện của các giao tác...- 83

Lịch của R/WPCP trong hệ thống điều khiển giao thông hàng

KHÔI cewek ws KỈ BS eo VY No HH HN 2 86

</div>Trang 7<div class="page_container" data-page="7">

MỞ ĐẦU

Hệ thống cơ sở dữ liệu thời gian thực đã được sử dụng rộng trong các ứng

dụng như hàng không vũ trụ, hệ thống điều khiển giao thông hàng không,

người máy, năng lượng hạt nhân, hệ thống tích hợp máy, hệ thống chươngtrình chứng khốn, và hệ thống quản trị mạng. Do đó nghiên cứu cơ sở dữ

liệu (CSDL) thời gian thực đã được nhiều người tập trung nghiên cứu và triển

khai ứng dụng [13, 14, 31, 34, 44].

Hệ thống cơ sở dữ liệu thời gian thực bao gồm hai lĩnh vực quan trọngtrong khoa học máy tính, đó là: hệ thống thời gian thực và hệ thống CSDL.Một mặt các giao tác trong CSDL thời gian thực thường kết hợp với các ràng

buộc thời gian đó là điểm tới hạn. Mặt khác, như là một CSDL, CSDL thời

gian thực phải duy trì dữ liệu của nó cho các thơng tin hữu ích, cung cấp

các thao tác của dữ liệu va xử lý các giao tác [34].

Hiện nay, hệ thống CSDL thời gian thực là một trong những lĩnh vực đang

được quan tâm nghiên cứu và phát triển. Sự phát triển này hứa hẹn một triển

vọng ứng dụng to lớn trong các hoạt động kinh tế, khoa học kỹ thuật, an

ninh và quốc phòng... Tuy nhiên để khai thác CSDL thời gian thực va phát

triển các ứng dụng, trong thực tế thì vẫn cịn nhiều vấn đề cần phải tiếp tục

nghiên cứu. Ở nước ta, CSDL thời gian thực vẫn còn là một lĩnh vực mới mẻ

cả trong nghiên cứu và triển khai ứng dụng. Hơn nữa, nước ta đang trong

thời kỳ phát triển của nền kinh tế nhiều thành phần và đa dạng, nên vai trị

của các hệ thống thơng tin, đặc biệt là các hệ CSDL thời gian thực lại càng

chiếm một vị trí quan trọng. Do vậy đầu tư cho nghiên cứu và triển khai ứng

dụng hệ thống CSDL thời gian thực là một việc làm cần thiết.

Mơ hình dữ liệu và CSDL truyền thống không đáp ứng đây đủ cho các

ứng dụng thời gian thực. Bởi vì, nó khơng được thiết kế để cung cấp cho

yêu cầu ứng dụng giao dịch thời gian thực. Do đó, trong hệ thống CSDL

thời gian thực chúng ta phải xử lý một số yêu cầu về thời gian, khác với điều

kiện thông thường.

Để phát triển hệ thống thời gian thực, đặc biệt là hệ CSDL thời gian thực,

</div>Trang 8<div class="page_container" data-page="8">

trong đó các thuật toán lập lịch và điều khiển tương tranh là một vấn đề

chính trong nghiên cứu hệ thống CSDL thời gian thực. Trong một thập kỷ

qua, một số giao thức điều khiển tương tranh thời gian thực đã được đề xuất

[32. 33, 34, 42] để giải quyết xung đột dữ liệu giữa các giao tác. Các giao

thức này phải đảm bảo khơng chỉ duy trì tính nhất qn của dữ liệu trong

môi trường nhiều người sử dụng như trong cơ sở dữ liệu truyền thống mà

cịn duy trì tính nhất quán thời gian của dữ liệu và tất cả các giao tác phải

hoàn thành thực hiện trước điểm hạn của chúng. Do đó, điều khiển tương

tranh trong CSDL thời gian thực phức tạp hơn điều khiển tương tranh trong

CSDL truyền thống.

Cùng với sự phát triển của máy tính, hệ thống thời gian thực (hệ CSDL

thời gian thực) đã có những sự thay đổi rất lớn. Sự phát triển này làm tăng

sự phức tạp của hệ thống máy tính, tạo ra sự cần thiết phải cải tiến các kỹ

thuật đặc tả và kiểm chứng hình thức. Các phương pháp hình thức liên quan

tới nhiều kỹ thuật và mơ hình tốn học và có thể được áp dụng cho thiết kế

hệ thống thời gian thực, ví dụ [23, 26, 28, 37, 46]. Trong đó, việc sử dụng

các logic hình thức trong đặc tả, thiết kế, kiểm chứng và xây dựng hệ thống

thời gian thực ngày càng được quan tâm. Mục đích chính của việc sử dụngphương pháp hình thức là chìa khố giải quyết việc xây dựng điều kiện đúng,để đặc tả chính xác bài tốn đặt ra và có thể kiểm chứng được bằng toán

học nhờ sự trợ giúp của các cơng cụ.

Một trong những phương pháp hình thức đang tồn tai, được áp dung trongviệc đặc tả hình thức cho hệ thống thời gian thực là logic thời gian thực [37].

Các phương pháp đặc tả hình thức có thể được thiết kế để phân tích và

kiểm chứng chất lượng thuộc tính thời gian nhằm giảm thiểu số lỗi và tăng

khả năng thực thi của hệ thống. Tuy nhiên, với các yêu cầu thời gian thực,

chất lượng đặc tả và phân tích thì khơng đây đủ, ví dụ như phương pháp sử

dụng logic thời gian chỉ đặc tả được thứ tự thời gian, chứ không đặc tả được

các ràng buộc thời gian và tính chất của dữ liệu. Hiện nay các nhà nghiên

cứu đã và đang cố gắng nghiên cứu mở rộng các phương pháp đặc tả hình

thức đang tồn tại cho phép thể hiện thuộc tính thời gian như: Real TimeLogic [8], Time CSP [40], Metric Temporal Logic [30], Timed Transition

10

</div>Trang 9<div class="page_container" data-page="9">

System [22], Timed Automata [9],... Trong số đó, Logic tính tốn khoảng

(Duration Calculus) (DC) [15] là một hệ thống hình thức cho đặc tả và thiết

kế hệ thống thời gian thực đặc biệt an toàn. DC bat đầu được phát triển

trong các dự án ProCoS (ESPRIT BRA 3104 và 7071) năm 1990 và được đề

xuất bởi Zhou Chaochen, CA.R.Hoare, và A.P. Ravn [15]. Sau đó DC được

tập trung nghiên cứu và phát triển mở rộng bởi các nhà nghiên cứu trong dựán Design Technique for Real- Time Systems của Viện công nghệ phần mềm

Quốc tế (UNU/IIST) từ năm 1993. DC là một logic đơn giản, phù hợp để

biểu diễn và xử lý khoảng thời gian, một khái niệm chính trong lập lịch, và

DC đã sử dụng hiệu quả trong nhiều cơng trình nghiên cứu về các hệ thống

thời gian thực, ví dụ [16, 20, 29, 38, 39, 47].

Việc áp dụng các phương pháp hình thức trong các lĩnh vực nghiên cứu

CSDL nói chung và CSDL thời gian thực nói riêng là một lính vực nghiên

cứu mới, và còn nhiều vấn đề cần được phát triển.

Trong lĩnh vực nghiên cứu này đã có một số cố gắng đưa ra các logic

khác nhau cho hệ thống CSDL, hệ thống CSDL thời gian và thời gian thực,

các logic này đưa ra định nghĩa rất tốt để khai báo về mặt ngữ nghĩa chochúng.

Trong [11], Michael Benedikt, Timothy Griffin và Leonid Libkin đã xây

dựng mơ hình để kiểm chứng các thuộc tính của các giao tác trong CSDL.Cu thể, các tác giả nghiên cứu các thuộc tính tiền điều kiện cho một số giao

tác và các ngôn ngữ đặc tả, liên quan tới các ràng buộc toàn vẹn CSDL.

Trong [19], Marcelo Finger sử dụng logic thời gian để nghiên cứu và xây

dựng mơ hình CSDL thời gian. Cơ sở dữ liệu thời gian liên quan tới việc

lưu trữ, truy vấn và thao tác kết hợp với thời gian. Tác giả đã đề xuất hai

mơ hình thời gian. Mơ hình thứ nhất đề cập tới khía cạnh tĩnh của dữ liệu

thời gian như truy vấn và thể hiện dữ liệu. Mô hình hai mở rộng để mơ tả

các thuộc tính động khi cập nhật dữ liệu. Kết quả của hai mô hình được sử

dụng để hình thức hố các đặc trưng khác nhau về tính hợp lệ thời gian của

dữ liệu và giao tác, va đưa ra mơ hình hình thức cho CSDL thời gian.

Trong [38], Ekaterina Pavlova va Dang Van Hung đã xây dựng một đặc

tả hình thức giao thức điều khiển tương tranh trong CSDL thời gian thực,

lãi

</div>Trang 10<div class="page_container" data-page="10">

nhưng các tác giả không tập trung nghiên cứu sự tích hợp giữa điều khiển

tương tranh với lập lịch.

Đặc biệt, trong [6, tr. 93] Hồ Văn Hương và Đặng Văn Hưng đã đề xuất

mơ hình hình thức cho CSDL thời gian thực, tập trung nghiên cứu tích hợpđiều khiển tương tranh với lập lịch, đưa ra điều kiện đúng cho thực hiện song

song của hệ thống giao tác, và kiểm chứng một số điều kiện cho việc duy

trì tính nhất quán của dữ liệu.

Những lý do trên đây là cơ sở cho việc chọn đề tài nghiên cứu của luận

" Đặc tả, kiểm chứng hình thức và ứng dụng trong cơ sở dữ liệu thời

gian thực ".

Luận án tập trung nghiên cứu và phát triển một mơ hình toán học cho các

hệ thống CSDL thời gian thực. Đặc biệt, luận án tập trung đặc tả và kiểmchứng hình thức các thuật toán lập lịch và điều khiển tương tranh trong hệ

thống CSDL thời gian thực.

Dựa vào mơ hình hình thức đã được đề xuất, luận án đưa ra các đặc tảhình thức điều kiện đúng cho thực hiện song song của hệ thống các giao tác,đặc tả và kiểm chứng hình thức một số điều kiện để duy trì tính nhất qnthời gian của dữ liệu, phát triển một phương pháp luận để đặc tả và kiểm

chứng hình thức các giao thức điều khiển tương tranh trong cơ sở đữ liệu

thời gian thực.

Mơ hình hình thức được chọn là logic tính tốn khoảng, một logic thời

gian thực như là một nền tảng cho tiếp cận của luận án.

Trên cơ sở kết quả nghiên cứu chỉ tiết về đặc tả và kiểm chứng hình thức

các giao thức điều khiển tương tranh. Chúng tôi nhận thấy rằng số đảo ngượcmức ưu tiên của một số giao thức trong môi trường đa bộ xử lý có thể nhiều

hơn một lần. Sau đó chúng tơi đã đề xuất cải tiến một số giao thức cho môi

trường đa bộ xử lý.

Luận án cũng tập trung nghiên cứu ứng dụng cơ sở dữ liệu thời gian thực

trong hệ thống điều khiển giao thông hàng khơng như mơ hình hệ thống, dữ

liệu, giao tác, nhất quán thời gian và điều khiển tương tranh, nghiên cứu hệ

12

</div>Trang 11<div class="page_container" data-page="11">

thống đặc ta và kiểm chứng hình thức PVS (Prototype Verification System)

và cơng cụ kiểm chứng của logic tính tốn khoảng PC/DC (Proof Checker

for Duration Calculus). Chúng tơi xây dựng đặc tả và kiểm chứng hình thức

tự động trong một số ứng dụng thời gian thực.

Những kết quả chính của luận án:

e Xây dựng mơ hình hình thức CSDL thời gian thực với khả nang cho mơhình hố hệ thống giao tác có chu kỳ.

e Chúng ta thấy rằng, xử lý hệ thống giao tác chu kỳ với điểm hạn khôngphải là một công việc dễ dàng. Một khó khăn là làm thế nào để hình

thức hố tính khả tuần tự của hệ thống giao tác có chu kỳ, nghĩa là mộtgiao tác được lặp cho một số vô hạn của thời gian.

e Đề xuất và chứng minh định lý về tính khả tuần tự của việc thực hiện

các giao tác có chu kỳ trong hệ thống CSDL thời gian thực.

e Xây dung một đặc tả hình thức điều kiện đúng của giao thức điều khiển

tương tranh trong hệ thống CSDL thời gian thực như khả tuần tự, nhất

quán thời gian và các ràng buộc thời gian.

e« Phát triển đặc tả và kiểm chứng hình thức các điều kiện duy trì tính

nhất qn thời gian cho mỗi loại giao tác.

e Luận án phát triển phương pháp luận để đặc tả và kiểm chứng hình thức

các giao thức điều khiển tương tranh.

e Cải tiến một số giao thức điều khiển tương tranh và những phát hiện

mới về vấn đề nghẽn của các giao thức thực hiện trong môi trường đabộ xử lý.

e Nghiên cứu ứng dụng CSDL thời gian thực trong hệ thống điều khiển

giao thông hàng không.

e Nghiên cứu hệ thống đặc tả và kiểm chứng hình thức PVS và cơng cụ

kiểm chứng của logic tính toán khoảng PC/DC. Đề xuất một đặc tả vàkiểm chứng hình thức tự động trong một số ứng dụng thời gian thực.

13

</div>Trang 12<div class="page_container" data-page="12">

Luận án được tổ chức như sau:

Chương 1 trình bày các khái niệm cơ bản trong CSDL, CSDL thời gian

thực, như điều khiển tương tranh, điều kiện đúng và tính khả tuần tự, mơ

hình CSDL thời gian thực, các đặc điểm dif liệu va giao tác, điều khiển tương

tranh thời gian thực, đảo ngược mức ưu tiên, kế thừa mức ưu tiên, và một

số giao thức điều khiển tương tranh tiêu biểu như giao thức doc/ ghi mức ưu

tiên cao nhất (R/WPCP), giao thức huỷ bỏ cơ sở (BAP), giao thức mức ưutiên cao nhất với điều chỉnh động của thứ tự khả tuần tự (PCP-DA).

Chương 2 trình bày tóm lược về cú pháp, ngữ nghĩa, hệ thống chứng minhcủa logic khoảng, và logic tính toán khoảng. Chứng minh một số định lý,

làm cơ sở cho việc xây dựng và phát triển mơ hình hình thức cũng như đặc

tả và kiểm chứng hình thức trong CSDL thời gian thực.

Chương 3 xây dựng mơ hình hình thức của hệ thống CSDL thời gian thực

trong logic tính toán khoảng. Xây dựng các biến trạng thái DC để mơ hình

hố hệ thống CSDL thời gian thực được đặc trưng bởi dữ liệu và các giao

tác, viết các công thức DC trên các biến trạng thái để mô tả các thuộc tính

của hệ thống CSDL thời gian thực. Sau đó đưa ra một đặc tả điều kiện đúng

cho thực hiện song song của hệ thống giao tác trong CSDL thời gian thực.

Đặc tả và kiểm chứng một số điều kiện để duy trì tính nhất qn thời gian

trong hệ thống CSDL thời gian thực.

Chương 4 phát triển phương pháp luận để đặc tả và kiểm chứng hình thức

giao thức điều khiển tương tranh trong CSDL thời gian thực. Sử dung mơhình hình thức của CSDL thời gian thực được dé xuất trong chương 3 để đặc

tả và kiểm chứng hình thức một lớp các giao thức điều khiển tương tranh như

R/WPCP, BAP, PCP-DA. Thông qua việc đặc tả và kiểm chứng hình thức,

chúng tơi đã nhận thấy rằng số đảo ngược mức ưu tiên của một số giao thứctrong mơi trường đa bộ xử lý có thể nhiều hon mot lần. Chúng tôi đã cải tiến

một số giao thức cho môi trường đa bộ xử lý. Kết quả nghiên cứu này có thểáp dụng và mở rộng cho nhiều giao thức khác nhau trong CSDL thời gian

thực, khi thực hiện trong mơi trường đa bộ xử lý. Sau đó, chúng tôi nghiên

cứu ứng dụng hệ thống CSDL thời gian thực trong hệ thống điều khiển giao

thông hàng không như mơ hình hệ thống, dữ liệu, giao tác, nhất qn thời

14

</div>Trang 13<div class="page_container" data-page="13">

gian và điều khiển tương tranh. Từ các kết quả nghiên cứu chi tiết về đặc tả

và kiểm chứng hình thức các giao thức điều khiển tương tranh, chúng tơi đãứng dụng các giao thức đó vào trong hệ thống điều khiển giao thông hàng

Cuối cùng là phần kết luận, tóm tắt các kết quả trong nghiên cứu và trình

bày hướng nghiên cứu phát triển trong tương lai của chúng tôi.

iS

</div>Trang 14<div class="page_container" data-page="14">

CHUONG 1

CO SO DU LIEU THOI GIAN THUC

Chương nay trình bay một số khái niệm chính của hệ thống CSDL, hệ thống

CSDL thời gian thực và giao thức điều khiển tương tranh trong CSDL thời

gian thực.

1.1 Cơ sở dữ liệu

Cơ sở dữ liệu là một hệ thống tích hợp các quan hệ dữ liệu về các tổ chức

được lưu trữ trên máy tính. Thực tế dữ liệu được lưu giữ trong CSDL thểhiện trạng thái của CSDL tại một thời điểm nhất định. Bởi vì nội dung của

CSDL thay đổi khi thơng tin dữ liệu được cập nhật hoặc bị xoá từ CSDL,

chúng ta có thể định nghĩa một CSDL với một tập các đối tượng đữ liệu, mỗi

tập dữ liệu là một biến thay đổi theo thời gian và một trạng thái của CSDLtại một thời điểm / là một giá trị của các biến cho các đối tượng dữ liệu tai

thời điểm ¡. Mỗi CSDL thường kết hợp với một tập các ràng buộc toàn vẹn

mà dữ liệu đúng trong CSDL phải thoả mãn. Các giá trị của dữ liệu được

phép lưu trữ trong CSDL chỉ khi chúng không vi phạm các ràng buộc toàn

vẹn tương ứng. Các ràng buộc đữ liệu đó thường được thể hiện như các cơng

thức logic trên các đối tượng dữ liệu.

ló

</div>Trang 15<div class="page_container" data-page="15">

1.2 Điều khiến tương tranh trong CSDL

Một trong các mục đích chính của các hệ thống CSDL là cho phép nhiều

người sử dụng để truy cập chia sẻ dữ liệu đồng thời [12]. Truy cập song

song là dễ nếu tất cả mọi người sử dụng, chỉ đọc dữ liệu. Khi đó việc đọc

dữ liệu của người này sẽ khơng ảnh hưởng tới những người khác. Tuy nhiên,

khi hai hoặc nhiều người sử dụng cùng truy cập CSDL song song và ít nhất

một trong số họ muốn ghi dữ liệu, khi đó tác động ghi dữ liệu có thể ảnh

hưởng tới việc đọc dữ liệu, đọc trước và sau khi ghi là khác nhau. Điều nay

có thể gây ra vấn đề khơng nhất qn dữ liệu [12].

Vì nhiều người sử dụng có thể truy cập dữ liệu vào CSDL tai cùng thời

điểm, nên cần đảm bảo rằng các thao tác thực hiện song song ln ln duytrì tính nhất qn dữ liệu trong CSDL. Truy cập của người sử dụng được thực

hiện bởi các giao tác. Một giao tác là một dãy logic của các thao tác được

đặc trưng bởi các thuộc tính sau:

e Nguyên tử: hoặc là tất cả hoặc khơng có một thao tác nào của giao tác

được thực hiện.

e Nhất quán: một giao tác, khi thực hiện độc lập sẽ chuyển CSDL từ

một trạng thái nhất quán tới một trạng thái nhất quán khác,

e Độc lập: thực hiện của giao tác nay không ảnh hưởng tới các giao tác

e Bén vững: khi một giao tác đã uỷ thác, hệ thống phải đảm bảo tínhbền vững của nó khơng phụ thuộc vào hỏng hóc sau đó.

Chú ý rằng bất cứ thao tác nào trong CSDL cũng được xem xét như là

một phần của một giao tác. Trong một hệ thống giao tác, khi chúng thực

hiện song song có thể ảnh hưởng đến tính nhất quán của dữ liệu trong CSDL

vì sự ảnh hưởng giữa các giao tác. Dé các giao tác thực hiện không ảnh

hưởng tới các giao tác khác, thực hiện của chúng phải được điều khiển bằng

các giao thức điều khiển tương tranh. Giao thức điều khiển tương tranh được

biết đến nhiều nhất trong hệ thống quản trị CSDL là giao thức khoá hai pha

</div>Trang 16<div class="page_container" data-page="16">

[12]. Trong giao thức khoá hai pha (2PL), mỗi đối tượng dữ liệu có hai loại

khố: các khố doc (read locks) và các khoá ghi ( write locks). Một giao táccó thể đọc hoặc ghi trên một đối tượng dữ liệu + khi và chỉ khi nó có một

khố đọc hoặc ghi trên z tương ứng. Hai khố nói là bị xung đột khi và chỉ

khi chúng thao tác trên cùng một đơn vị dữ liệu và một trong chúng là khố

ghi. Các giao tác chỉ có thể chia sẻ các khố khơng bị xung đột. Trong 2PL,

mọi giao tác đều thực hiện theo hai pha. Pha đầu được gọi là pha nhận, các

khoá trên các đối tượng di liệu cần xử lý bởi các giao tác và không có khố

nào được giải phóng, trong khi pha thứ hai thì giải phóng khố và khơng thể

nhận một khố mới.

Một giao thức điều khiển tương tranh được xem là đúng khi và chỉ khi

bất cứ thực hiện nào của các giao tác được điều khiển bởi nó cũng thoả mãn

điều kiện đúng, đó là tính khả tuần tự.

Điều kiện đúng và tính khả tuần tự

Hiển nhiên là một thực hiện tuần tự của các giao tác sẽ đưa CSDL từ một

trạng thái nhất quán tới một trạng thái nhất quán khác, và do đó nó được

xem như là đúng. Do vậy, điều kiện đúng để thực hiện song song của các

giao tác trong hệ thống quản trị CSDL là khả tuần tự, nghĩa là thực hiện song

song các giao tác đó cho những kết quả như chúng thực hiện tuần tự.

Tính khả tuần tự có thể được định nghĩa tương đương như sau.

Định nghĩa 1 Mot thực hiện song song của các giao tác gọi là khả tuần tự

khi và chỉ khi tồn tại một thứ tự toàn bộ trên tập các giao tác sao cho khi

một giao tác T trước một giao tác 1' theo thứ tự này, thì bất cứ thao tác O

nào cua † phải thực hiện trước các thao tác O' của 1" trong đó O' xung đột

với O khi thực hiện song song [12].

Trong hầu hết các giao thức điều khiển tương tranh, tính khả tuần tự là

dựa trên khái niệm của các thao tác xung đột và được gọi là khả tuần tự

xung đội.

Trong đó, hai thao tác được gọi là xung đột nếu chúng thao tác trên cùngmột đơn vị dữ liệu và ít nhất một trong chúng là thao tác ghi.

18

</div>Trang 17<div class="page_container" data-page="17">

1.3 Cac đặc điểm dữ liệu và giao tác của CSDL thời gian thực

Tất cả các khái niệm đã đề cập ở trên cho hệ thống CSDL cũng được áp

dụng cho CSDL thời gian thực. Các đặc trưng mới cho CSDL thời gian thực

là các đặc tính thời gian.

Một hệ thống CSDL thời gian thực bao gồm hệ thống quản trị CSDL

truyền thống và hệ thống thời gian thực [13]. Trong CSDL thời gian thực,

các giao tác không chỉ thoả mãn điểm tới hạn, mà chúng còn phải sử dụng

dữ liệu hợp lệ trong khi thực hiện. Trong hệ thống CSDL thời gian thực, các

đối tượng di liệu được chia thành các đối tượng dữ liệu liên tục va các đối

tượng dif liệu rời rac. Mơ hình hệ thống CSDL được mơ tả trong Hình 1.1.

h ĩ : |

Giao tác sengor

>| Thiết bị vật lý

Đối tượng dữ liệu Đối tượng dữ liệu

liên tục roi rac

7 Bo diéu RATER [pethcewcecsrnaswnncacsmmniemensens

Hình 1.1: Mơ hình CSDL thời gian thực

Một giá trị của đối tượng dữ liệu liên tục phản ánh trạng thái của đối

tượng này trong thế giới thực. Mỗi giá trị của đối tượng liên tục có thểkhơng hợp lệ trong khoảng thời gian trôi qua. Các đối tượng dữ liệu rời rạclà tinh và giá trị của nó không phụ thuộc vào thời gian. Các đối tượng dữ

liệu liên tục có thể chia thành các đối tượng dữ liệu cơ sở và các đối tượngdữ liệu suy diễn. Giá trị của một đối tượng dữ liệu cơ sở có thể được nhận

trực tiếp từ sensor, trong khi giá trị của đối tượng dữ liệu suy diễn được tính

tốn từ một tập giá trị các đối tượng cơ sở.

Ví dụ: CSDL điều khiển giao thông hàng không chứa các đối tượng dữ

19

</div>Trang 18<div class="page_container" data-page="18">

liệu cơ sở thể hiện chuyến bay trong một vùng bay xác định. Các thuộc tính

của đối tượng cơ sở bao gồm vị trí kinh độ và vĩ độ của các chuyến bay.

Các giá trị của các thuộc tính đó được cập nhật có chu kỳ trên các giá triđo của kinh độ và vĩ độ được cung cấp bởi hệ thống radar, (nếu bỏ qua cập

nhật này, kinh độ và vĩ độ của chuyến bay đã được cất trong CSDL sẽ sai

lệch so với kinh độ và vĩ độ của máy bay thực tế).

Trong CSDL thời gian thực các giao tác cũng phải thực hiện trước điểmtới hạn của chúng. Điểm hạn của một giao tác có thể là điểm hạn cứng,

điểm hạn vững chắc hay điểm hạn mềm, độc lập với yêu cầu các chức năng

của nó.

Việc hồn thành thực hiện của một giao tác thời gian thực có thể tạo ra

một giá trị cho hệ thống. Quan hệ giữa giá trị của một giao tác thời gianthực với thời gian hoàn thành thực hiện của chúng có thể xem như là một

hàm giá trị của thời gian [34]. Đồ thị thể hiện hàm giá trị của các kiểu loại

khác nhau đối với các giao tác được giới thiệu trong Hình 1.2.

Hàm giá trị Hàm giá trị \ Hàm giá trị

† - a — | > " ———— —————>

| ale

‘am han Thời gian ; Thời gian Thời gian

Điểm han lu ớu Diem han 7 Diém han “HẠNG

Giao tác điểm hạn mém Giao tác điểm hạn vững chắc Giao tác điểm hạn cứng

Hình 1.2: Các hàm giá trị của các kiểu giao tác thời gian thực

e Một giao tác có điểm hạn cứng bị vi phạm, khi đó sự cố có thể xảy

ra. Nghĩa là sẽ có giá trị âm trong hệ thống nếu điểm hạn cứng bị vi

phạm. Đây là đặc trưng cho hệ thống đặc biệt an tồn. Ví dụ: CSDL

thời gian thực trong hệ thống điều khiển giao thông hàng không thường

yêu cầu các giao tác phải thoả mãn điểm hạn cứng.

ø Một giao tác vi phạm điểm hạn mềm, giá trị của nó có thể giảm với

thời gian và bằng không tại một thời điểm sau điểm hạn.

20

</div>Trang 19<div class="page_container" data-page="19">

e Một giao tác có điểm han vững chắc sẽ khơng cịn giá trị sau khi kết

thúc điểm hạn. Điểm hạn mềm và vững chắc của các giao tác thường

xuất hiện trong các ứng dụng thời gian thực có u cầu về mức độ an

tồn thấp như hệ thống chuyển mạch điện thoại và hệ thống chương

trình chứng khốn...

Trong hệ thống CSDL thời gian thực, ngồi tính nhất quán logic như CSDL

truyền thống, dữ liệu phải thoả mãn tính nhất qn thời gian.

Có hai thể hiện khác nhau của các đối tượng dữ liệu: Thể hiện ngoài

(trong thế giới thực) và thể hiện trong (bên trong CSDL). Hai thể hiện này

có quan hệ thời gian với nhau và quan hệ này gọi là nhất quán thời gian. Có

hai kiểu nhất quán thời gian của dữ liệu: Nhất quán tuyệt đối và nhất quán

tương đối. Đồ thi thể hiện nhất quán tuyệt đối và tương đối của di liệu được

mơ tả như trong Hình 1.3.

Thể hiện ngồi(x) Thể hiện ngoai(y)

Nhất quán tuyệt đốiNhất quán tuyệt đối

Thể hiện trong(x) Thể hiện trong(y)Nhất quán tương đối

Hình 1.3: Nhất quán thời gian của dữ liệu

Nhất quán tuyệt đối: thể hiện bên trong của dữ liệu gan nhau hơn so vớithể hiện bên ngoài của dữ liệu tại mọi thời điểm của thời gian.

Nhất quán tương đối: một giá trị của tập các đối tượng dữ liệu có thể

được sử dụng với nhau chỉ khi chúng được sinh ra đủ gần nhau.

Chúng ta định nghĩa hình thức nhất quán thời gian của dữ liệu như sau:

Định nghĩa 2 Một đơn vị dữ liệu trong CSDL thời gian thực được ky hiệu là:

d: (value, avi, timestamp). Trong đó dyaine là giá trị hiện tại của d, lap là

thời điểm quan sát khi tạo ra d. d,,, là khoảng hợp lệ tuyệt đối của d.

zi

</div>Trang 20<div class="page_container" data-page="20">

Ký hiệu R là một tập nhất quán tương đối, nghĩa là một tập các đối tượng

dữ liệu nhận được từ một don vị dữ liệu mới. Môi tập h kết hợp với một

khoảng hợp lệ tương đối ký hiệu là h,... Giả thiết d © h. d có trạng thái

đúng khi và chỉ khi.

1. diane La nhất quán logic và thoả mãn tất cả các ràng buộc toàn vẹn.2. d là nhất quán thời gian:

e Nhất quán tuyệt đối: (dl, urrenllime ~~ Qisnenane) SS ae

e Nhất quán tương doi: Vd! © R.\diimestamp — Uimestamp! < Revi

Trong đó deurrentiime là thời điểm quan sát hiện tại cua 4.

Ví dụ: Gia thiết tcmperalurc,,=5, prcssurc,,=10, R={nhiét độ

(temper-ature), áp xuất (pressure)}, và ",„=2. Nếu thời điểm hiện tại (current

time )=100, thì trường hợp sau:

(a) nhiệt độ=(347, 5, 95) và áp xuất=(50, 10, 97) là nhất quán thời gian.

Nhưng trường hợp sau:

(b) nhiệt độ=(347, 5, 95) và áp xuất =(50, 10, 92) là khơng nhất qn

thời gian. Thậm chí theo trường hợp (b) thì thoả mãn tính nhất qn tuyệtđối, nhưng tính nhất qn tương đối khơng thoả mãn. Một ví dụ khác: Cột

Các ứng dụng Kíchthước lhờigian Thờigian Nhất quán Nhât quán Thời gian

trungbình muộn nhất tuyệt đối tương đối duy trìAir traffic control 20,000 0.05 ms 5.00 ms 1.50 sec 3.00 sec 12 hours

Aircraft mission 3,000 0.05 ms 1.00 ms 0.05 sec 0.20 sec 4 hoursSpacecraft control 5,000 0.05 ms 1.00 ms 0.20 sec 1.00 sec 25 years

Command control 50,000 0.50 ms 5.00 sec 0.05 sec 0.10 sec 1 hour

Bang 1.1: Cac yêu cầu đặc trưng của CSDL thời gian thực

nhãn “nhất quán tuyệt đối” và “nhất quán tương đối” trong Bảng 1.1 mô tả

đặc trưng của các giá trị định nghĩa cho nhất quán tuyệt đối và nhất quán

tương đối trong các ứng dụng khác nhau [34]. Trong đó ứng dụng “ Aircraftmission” được mơ tả trong bảng chỉ ra mỗi loại của CSDL được sử dụng đểcung cấp các nhiệm vụ của máy bay chiến đấu. Một máy bay chiến đấu

22

</div>Trang 21<div class="page_container" data-page="21">

chuyển động với tốc độ siêu cao. Do vậy, thông tin ở đó phải nhỏ hơn 0.05

giây (yêu cầu nhất quán tuyệt đối). Ngồi ra, hệ thống điều khiển giao thơng

hàng khơng với các máy bay thương mại vận tốc nhỏ hơn (yêu cầu nhất quán

tuyệt đối nhỏ hơn 1.5 giây). Điều này đã giải thích tại sao nhất quán tuyệt

đối cho điều khiển giao thông hàng không phải lớn hơn nhất quán tuyệt đối

trong ứng dụng của các máy bay chiến đấu.

1.4 Diéu khiển tương tranh thời gian thực

Các giao thức điều khiển tương tranh trong hệ thống CSDL thời gian thực,

ngồi việc phải đảm bảo tính khả tuần tự của các giao tác, có thể kèm theomột chính sách ưu tiên nào đó, để đảm bảo tính nhất qn thời gian, mặtkhác chúng còn phải thoả mãn điểm hạn của chúng. Do vậy, các giao thứcđiều khiển tương tranh trong hệ thống CSDL thời gian thực phức tạp hơn các

giao thức điều khiển tương tranh trong các CSDL truyền thống và phức tạp

hơn các bộ lập lịch thời gian thực.

Đã có nhiều cơng trình tập trung nghiên cứu việc tích hợp các giao thức

điều khiển tương tranh trong hệ thống CSDL với lập lịch ưu tiên để đạt đượcmột giao thức điều khiển tương tranh trong hệ thống CSDL thời gian thực

[13, 34, 42]. Hầu hết các ứng dụng đó đưa ra yêu cầu phải thoả mãn các

ràng buộc thời gian, nghĩa là điểm hạn phải được thoả mãn. Để thoả mãn

được các điểm hạn cứng của các giao tác, các giao thức điều khiển tương

tranh trong CSDL thời gian thực phải kèm theo một thuật toán lập lịch. Các

giao thức này thông thường sử dụng các giao tác nghẽn để giải quyết xung

đột dữ liệu giữa các giao tác nhằm duy trì tính nhất qn dữ liệu [12].

Các giao tác khố truyền thống, như 2PL khơng thoả mãn cho hệ thống

CSDL thời gian thực. Hai vấn đề chính gặp phải là khả năng đảo ngược mứcưu tiên và giải quyết bế tắc (deadlock).

Đảo ngược mức ưu tiên tăng khi một giao tác 7, có mức ưu tiên cao hơn

bị nghẽn bởi một giao tác 7; có mức ưu tiên thấp hon. Bởi vì 7), yêu cầu

một đối tượng dữ liệu mà nó đã bị giữ bởi giao tác 7). 7;, sẽ bị nghẽn đếntận khi 7, hoàn thành thực hiện của nó. Rất tiếc, khoảng đảo ngược mức ưu

23

</div>Trang 22<div class="page_container" data-page="22">

tiên này có thể bị kéo đài bởi vì một số giao tác có mức ưu tiên thấp hơn 7,có thể nhận được mức ưu tiên của 7, [41]. Bởi vậy, rất khó thoả mãn yêu

cầu điểm hạn cứng của các giao tác khi xảy ra đảo ngược mức ưu tiên và bế

tac [41]. Trường hợp này có thể xảy ra khi các giao thức điều khiển tương

tranh được tích hợp với lịch điều khiển mức ưu tiên.

Kỹ thuật kế thừa mức ưu tiên được ứng dụng để giải quyết vấn đề đảo

ngược mức ưu tiên. Kỹ thuật này thực hiện như sau: Khi một giao tác có

mức ưu tiên thấp 7, làm nghẽn một giao tác có mức ưu tiên cao 7„„, 7, kếthừa và thực hiện tại mức ưu tiên của 7;,. 7, sẽ trả lại mức ưu tiên ban đầu

của chúng khi chúng giải phóng tất cả các khố của nó trên các tài nguyên.

Tuy nhiên, các giao thức kế thừa mức ưu tiên khơng giải quyết được vấn đề

bế tắc [41]. Ngồi ra, một giao tác với mức ưu tiên cao hơn có thể bị nghẽn

bởi nhiều giao tác có mức ưu tiên thấp hơn. Sự nghẽn này có thể tạo nên

việc phân tích nghẽn trong trường hợp xấu nhất của một giao tác với mức

ưu tiên cao hơn.

Hiện tai đã có mot lớp các giao thức [41] được nghiên cứu đưa ra ký hiệu

mức ưu tiên cao nhất vào trong giao thức kế thừa mức ưu tiên. Lớp giao thức

này được gọi là các giao thức mức uu tiên cao nhất.

Mức ưu tiên cao nhất được định nghĩa cho mỗi tài nguyên. Mức ưu tiên

cao nhất của mot tài nguyên là mức ưu tiên của giao tác có mức ưu tiên cao

nhất mà có thể truy cập tài nguyên. Các giao thức đó là các giao thức cơ

sở nhằm duy trì sự đồng bộ của các giao tác trên sự sở hữu quyền truy cập

để chia sẻ tài nguyên trong hệ thống thời gian thực. Các giao thức đó có

thể tránh được bế tắc và đảm bảo số lần nghẽn do đảo ngược mức ưu tiên

nhiều nhất một lần. Tuy nhiên, các giao thức mức ưu tiên cao nhất không

thể trực tiếp được áp dụng vào trong hệ thống CSDL thời gian thực, bởi vì

chúng khơng thể đảm bảo để thực hiện khả tuần tự của các giao tác thời gian

thực. Vì vậy, có rất nhiều tác giả đã tập trung nghiên cứu và mở rộng giao

thức này cho CSDL thời gian thực. Để hiểu chi tiết hơn về các giao thức

điều khiển tương tranh chúng ta sẽ trình bày sâu hơn trong phần tiếp theo

của luận án.

24

</div>Trang 23<div class="page_container" data-page="23">

1.4.1 7 Giao thức R/WPCP

Một số tác giả đã nghiên cứu [13, 34, 42] để mở rộng giao thức có mức ưu

tiên cao nhất [41] thành bộ lập lịch cho các giao tác trong hệ thống CSDL

thời gian thực. Read/Write Priority Ceiling Protocol (R/WPCP) [42] là sự mở

rộng của Priority Ceiling Protocol (PCP) [41] trong điều khiển tương tranh

thời gian thực, trên cơ sở sử dụng khoá hai pha trong việc duy trì tính khả

tuần tự cho thực hiện của các giao tác. R/WPCP đã được đề xuất cho điều

khiển tương tranh của các giao tác thời gian thực cứng có chu kỳ.

R/WPCP sử dụng ngữ nghĩa đọc ghi để cải thiện thực hiện của PCP. Trong

khi PCP chỉ cho phép các khoá độc chiếm trên đối tượng dữ liệu, R/WPCP

giới thiệu mức ưu tiên ghi cao nhất I1/L(z) và mức ưu tiên tuyệt đối cao

nhất .1/2(.:) cho mỗi đối tượng di liệu + trong hệ thống để chia sẻ và độc

chiếm các khoá tương ứng.

1. Mức ưu tiên ghi cao nhất I1/?/(z) của đối tượng dữ liệu + đặt bằng

mức ưu tiên cao nhất của những giao tác có thể ghi z.

2. Mức ưu tiên tuyệt đối cao nhất 1/?1(+) của đối tượng di liệu + đặt

bằng mức ưu tiên cao nhất của các giao tác có thể đọc hoặc ghi +.

3. Mức ưu tiên đọc/ ghi cao nhất /I1/?/(.:) của đối tượng dữ liệu :, được

xác định tại thời điểm thực hiện và được định nghĩa như sau. Khi một giao

tác có khố đọc đối với dit liệu x, RWPL(a) sẽ đặt bằng I1 /(z) (để ngăn

can mọi giao tác khác ghi :). Khi một giao tác có khố ghi trên dữ liệu +,

RWPL(x) được đặt bằng .1/2/(z) (để ngăn cản moi giao tác khác truy cập

Vào +).

Một giao tác có thể giữ một đối tượng dữ liệu nếu mức ưu tiên của nó

cao hơn mức ưu tiên đọc/ ghi cao nhất RW PL(x) của các đối tượng dit liệu„ đang được các giao tác khác giữ. Dưới điều kiện khố này, khi một giaotác có khố ghi đối với dữ liệu +, thì các giao tác khác khơng thể đọc hoặc

ghi đối tượng dữ liệu +. Khi một giao tác có khố đọc đối tượng dữ liệu -›,chỉ các giao tác có mức ưu tiên cao hơn I1'//(z) có thể giữ khố đọc đối

tượng dữ liệu z.

Một giao tác 7, sử dụng mức ưu tiên đã được xác định, trừ khi chúng giữ

25

</div>Trang 24<div class="page_container" data-page="24">

một số đối tượng dữ liệu và làm nghẽn một số giao tác có mức ưu tiên cao

hơn. Khi một giao tác làm nghẽn một giao tác có mức ưu tiên cao hơn, nókế thừa mức ưu tiên cao nhất của các giao tác bị nghẽn bởi 7; (mức ưu tiênkế thừa). Khi một giao tác giải phóng khố của một đối tượng dữ liệu, nó

thực hiện lại mức ưu tiên mà nó đã có tại thời điểm nhận khố trên đối tượng

dữ liệu. Mức ưu tiên kế thừa là sự chuyển dịch.

R/WPCP được thiết kế để lập lịch giao tác với điểm hạn cứng trong môi

trường một bộ xử lý, trong đó tập các giao tác và các đối tượng dữ liệu là

xác định. R/WPCP đảm bảo tránh bế tắc và nghẽn nhiều nhất một lần cho

mọi giao tác. Các giao tác có các mức ưu tiên cố định và được lập lịch bởi

thuật toán RM (rate monotonic) [35].

Un R_lock(x1)A R_lock(x1)

Ị W loek(xl) R_lock(x2) Un R loekx2) Un_W_lock(x1)

Hình 1.4: Thực hiện của các giao tác dưới R/WPCP

Chúng ta xét Hình 1.4 mô tả hành vi thực hiện của các giao tác trong

R/WPCP như sau: Giả sử rằng có ba giao tác 7), 7›, và 7; với các mức ưu

tiên là 1, 2, 3, tương ứng, ở đây 1 là cao nhất và 3 là thấp nhất. Giả sử rằng

x, có thể được đọc bởi 7; và được ghi bởi 7›, va x. có thể được đọc bởi 7› và

được ghi bởi 7;. Mức ưu tiên ghi cao nhất I1 /L(z¡) và mức ưu tiên tuyệt đốicao nhất .1/2/(z;) là 2 và 1, tương ứng. Mức ưu tiên ghi cao nhất II /?/(:;)

và mức ưu tiên tuyệt đối cao nhất .1/2/(z;) là 3 và 2, tương ứng.

Tại thời điểm ‘=0, 7; bat đầu thực hiện. Tại thời điểm ‘= 2, 7; có khốghi đối tượng dữ liệu :; thành cơng, và đặt /II/(z,) bằng .1/2/(z;) = 2.

Tại thời điểm /=4, 7, bắt đầu thực hiện và được ưu tiên hơn 7;. Khoá ghiyêu cầu của 7; trên z; tại thời điểm ‘=6 bị nghẽn bởi vi mức ưu tiên của 7;

không cao hơn /11/2L(z;) = 2. Như vậy, 7; bị nghẽn bởi 7›;. 7; bây giờ kế

26

</div>Trang 25<div class="page_container" data-page="25">

thừa mức ưu tiên của giao tác 7› và tiếp tục thực hiện.

Tại thời điểm /=9, 7; giải phóng khố trên đối tượng dữ liệu ›: và 7, ghi

thành công đối tượng dữ liệu z;, và đặt /I1/2L(z,) bằng APL(x,) = 1. Tại

thời điểm ‘=11, 7; bat đầu thực hiện và nhận được quyền ưu tiên hon 7).

Khoá đọc yêu cầu của 7; trên 1, bị nghẽn tại thời điểm ¿=13. Bởi vì mức

ưu tiên của 7; là khơng cao hơn /II/L(z,) = 1, ở đây x, là đối tượng dữliệu dang bị giữ bởi một giao tác. Nhu vậy, 7; bị nghẽn bởi 7). 7, bây giờ

kế thừa mức ưu tiên của giao tác 7; và tiếp tục thực hiện tại thời điểm /=13

và khoá đọc trên đối tượng dữ liệu +; thành cơng bởi vì khơng có bất ky

một giao tác nào đang chiếm một đối tượng dữ liệu và đặt /I1/?L(z;) bằng

I/L(z;) =3. 7, sau đó giải phóng khố trên đối tượng dữ liệu +; và +; tại

thời điểm /=18 và /=20, tương ứng. Tại thời điểm /=20, 7› tiếp tục thực hiện,

khoá đọc trên đối tượng +; thành công và đặt RW //(z¡) bằng IV PL(z¡) =2.

1, giải phóng khố trên đối tượng dif liệu z; tại thời điểm /=22 và uỷ thác

tại thời điểm ‘=23. 7› tiếp tục thực hiện tại thời điểm ¡ =23 và uỷ thác tạithời điểm /=25. 7; sau đó tiếp tục thực hiện tại thời điểm /=25 va uỷ thác

tại thời điểm /=27.

1.4.2. Giao thức BAP

Mặc dù R/WPCP hạn chế số lần nghẽn của các giao tác trong trường hợp

xấu nhất, nhưng chúng thường không thể tránh khỏi thời gian nghẽn dài của

giao tác trong nhiều hệ thống. Huỷ bỏ giao tác được đề xuất bởi nhiều tác

giả nghiên cứu để giải quyết vấn đề thời gian nghẽn dai và xung đột dữ liệu

giữa các giao tác [13, 34]. Dac biệt, Tei-Wei Kuo, Ming-Chung Liang, va

LihChyun Shu trong [32] đã đề xuất giao thức huỷ bỏ cơ sở (Basic Aborting

Protocol (BAP)). BAP là sự tích hợp của 2PL, PCP, và một thuật toán huỷ bỏđơn giản.

Cơ sở của giao thức này, khi một giao tác 7, cố gắng nhận một khoá trên

đối tượng dữ liệu +, khoá yêu cầu sẽ nhận được nếu mức ưu tiên của 7; caohơn mức ưu tiên cao nhất của tất cả các đối tượng dữ liệu hiện tại được giữ

bởi các giao tác khác 7;, ngược lại một thủ tục kiểm tra lại cho yêu cầu nhận

khoá được thực hiện như sau: nếu tất cả các giao tác khác 7, mà đang giữ

27

</div>Trang 26<div class="page_container" data-page="26">

các đối tượng dữ liệu với mức ưu tiên cao nhất cao hon mức ưu tiên của 7,

và các giao tác này có thể huỷ bỏ thì 7; có thể huỷ bỏ tất cả các giao tác

đang giữ khoá các đối tượng dữ liệu và nhận một khố mới. Ngồi ra, 7, sẽ

bị nghén.

Vì BAP bao gồm 2PL, PCP, và một thuật tốn huỷ bỏ, BAP duy trì nhiều

thuộc tính quan trọng của 2PL và PCP như khả tuần tự, đảm bảo không bế

tắc và nghẽn nhiều nhất một lần với mỗi giao tác. Lịch thực hiện của BAP

được mô tả trong Hình 1.5.

Lock(x1) Un_lock(x1) Lock{x1) Un_lock(x1)

1;

Lock(x2) Huỷ bỏ và khởi tạo lại Tiếp tục thực hiện Lãi

\ |

0 2 4 6 8 10 12 14 16 18 20 22 2A 26 28 30

Hình I.5: Thực hiện của các giao tác dưới BAP

Chúng ta giả sử như trong ví dụ của R/WPCP. Ngồi ra, đặt 7), 7; và 7;có các u cầu thời gian tính tốn là 5, 5, và 7, tương ứng, và có chu kỳ

tương ứng là 16, 22, và 26. Giả thiết giao tác 7; có thể huỷ bỏ và giao tác 7;và 7› là không thể huỷ bỏ. Trong giao thức BAP, đối tượng đữ liệu +; và ›;

có mức ưu tiên cao nhất bằng mức ưu tiên của các giao tấc 7; va 7›, tương

Thực hiện của BAP như sau: Tại thời điểm /=2, giao tác 7; nhận khoá

đối tượng dữ liệu +; và thực hiện với mức ưu tiên đã được xác định. Tại thờiđiểm (=4, 7; nhận được quyền ưu tiên hon 7;. Đến thời điểm /=6, 7; nhận

khoá trên đối tượng z;. Kết quả khoá yêu cầu bị huỷ bỏ và khởi tạo lại giao

tác 7;. Bởi vi 7; giữ đối tượng dữ liệu z; với mức ưu tiên cao nhất khơng

thấp hơn mức ưu tiên của 7; và 7; có thể huỷ bỏ. Vì vậy, u cầu khố trên

đối tượng dữ liệu z; nhận được, 7, tiếp tục thực hiện, nhưng nó sẽ bị nhườngquyền ưu tiên cho giao tác 7; tại thời điểm ‘= 8. Tại thời điểm /=10, yêucầu khoá trên đối tượng dit liệu +, được nhường cho 7; bởi vì mức ưu tiên

28

</div>Trang 27<div class="page_container" data-page="27">

của 7, cao hơn mức ưu tiên cao nhất của đối tượng dữ liệu z›, điều này đang

được giữ bởi giao tác 7› tại cùng thời điểm. Tại thời điểm ¡=14, 7; uỷ thác

và giải phóng khố của nó trên đối tượng dữ liệu z; và 7› tiếp tục thực hiện.

Tại thời điểm ‘= 17, 7) uỷ thác và 7) tiếp tục thực hiện như một giao tác

mới. Tuy nhiên, giao tác 7; và 7› lại đến tại thời điểm ‘= 20 và /= 24, tương

ứng. 7, chỉ nhận bốn đơn vị thời gian tính tốn trước khi điểm hạn của nó

đến tại thời điểm ‘= 26, nhưng 7; cần bay đơn vị thời gian tinh tốn. Vì vậy,

7; bị vi phạm điểm hạn tại thời điểm ‘=26. So sánh với Hình 1.4 thực hiện

của các giao tác trong R/WPCP, nhận thấy rằng, nghén của 7› tại thời điểm

(= 6, bởi vì mức ưu tiên cao nhất của đối tượng dữ liệu :: không thấp hon

mức ưu tiên của 7›, kết quả 7) vi phạm điểm han.

Từ ví dụ trên chúng ta thấy rằng trong thiết kế của BAP, một giao tác có

mức ưu tiên cao hơn có thể huỷ bỏ giao tác có mức ưu tiên thấp hơn để thoả

mãn yêu cầu ràng buộc thời gian, và cải thiện khả năng lập lịch của giao tác

có mức ưu tiên cao hơn.

1.4.3 Giao thức PCP-DA

Một cách tiếp cận khác để hạn chế thời gian nghẽn của các giao tác trong

giao thức R/WPCP đã được một số tác giả dé xuất trong giao thức mức ưu

tiên cao nhất với điều chỉnh động của thứ tự khả tuần tự (Priority Ceiling

Protocol with Dynamic Adjustment of Serialization Order (PCP-DA) [33]).

PCP-DA chi ra rang một giao tác có mức ưu tiên cao hơn có thé nhận được

quyền ưu tiên từ giao tác có mức ưu tiên thấp hơn trên dữ liệu xung đột vớiviệc sử dụng định nghĩa điều chỉnh động của thứ tự khả tuần tự để giảm thời

gian nghẽn của các giao tác. Giao thức này cho phép các giao tác có mức

ưu tiên cao hơn truy cập các dữ liệu để chúng có thể hồn thành thực hiện

ngay sau khi có thể, giảm bớt các giao tác bị nghẽn, và ngăn cản các giaotác có mức ưu tiên thấp phải khởi tạo lại, điều kiện khả năng lập lịch tốt hơn

cho tập các giao tác.

Trong PCP-DA, mức ưu tiên ghi cao nhất của các đối tượng dữ liệu và

mức ưu tiên cao nhất của hệ thống, về ngữ nghĩa chúng khác với R/WPCP.

Giống như R/WPCP, mỗi đối tượng dữ liệu z được xác định một mức ưu tiên

29

</div>Trang 28<div class="page_container" data-page="28">

ghi cao nhất, I1/'L(z) là mức ưu tiên của giao tác có mức ưu tiên cao nhất

có thể ghi x». I1/?2L(z) sẽ ảnh hưởng khi đối tượng dữ liệu › có một khố đọc

bởi một giao tác. Sysceil; ký hiệu cho WPL(x) cao nhất trong số tất cả các

đối tượng dữ liệu có khố đọc bởi các giao tác khác 7,. Mỗi giao tác 7; có

một mức ưu tiên là p;.

Các ký hiệu:

7\... !1„ tập các giao tác có mức ưu tiên giảm dần, với 7; có mức ưu tiêncao nhất.

T,.Rlock(v) ký hiệu 7, yêu cầu một khoá đọc z.

T,IV!ock(z) ký hiệu 7, yêu cầu khoá ghi +.

T,.Lock(x) ký hiệu một thao tác khóa của 7, trên đối tượng + sao cho

T;.Lock(+)= Tì.Rlock(x) hoặc T;.Lock(2)=T,.Wlock(x).

No— Rlock(x) ký hiệu đối tượng dit liệu x khơng bị khố đọc bởi các giao

tác khác 7; khi 7; yêu cầu khoá trên x.

WPL(x) ký hiệu cho các giao tác có mức ưu tiên cao nhất có thể ghi +.

7" ký hiệu giao tác đang giữ khoá đọc trên đối tượng di liệu › khi mức

ưu tiên ghi cao nhất bằng Syscetl;.

T*.WO ký hiệu cho tập ghi của 7”.

Các điều kiện khoá của PCP-DA được định nghĩa như sau. Một giao tác

7, được phép đọc hoặc ghi một đối tượng z nếu một trong những điều kiện

khoá sau đây là đúng.

Các điều kiện khoá:

LCI: 7, u cầu một khố ghi trên z và z khơng bị một khoá đọc bởi

các giao tác khác, nghĩa là 7;.1ock(+)=1;.Wlock(+) và No — Rlock(.).

LC2: 7, yêu cầu một khoá đọc trên + và mức ưu tiên của 7, cao hơn mức

ưu tiên ghi cao nhất của các đối tượng dữ liệu bị đọc bởi các giao tác khác,

nghĩa là ?;.Lock(+)=1;.Nlock(r) va p; > Sysceil;.

LC3: 7, yêu cầu một khoá đọc trên + và mức ưu tiên 7, cao hon mức

ưu tiên cao nhất của giao tác có thể ghi z và + không trong tập ghi của 7",

nghĩa là 7;.Lock(x)=T;. Rlock() va pi > WPL(z) va r ý T*.WO.

30

</div>Trang 29<div class="page_container" data-page="29">

LC4: 7; yêu cầu một khoá đọc trên + và mức ưu tiên của 7: bằng mức ưu

tiên cao nhất của giao tác có thể ghi + và z không trong tập ghi của 7*, nghĩa

là 7;.Lock(x)=T;. Rlock(x) Va p= W PL{(z) va No— Rlock(z) Và x ¢ T".WO.

Cũng như R/WPCP, PCP-DA là không bế tắc, và nghẽn nhiều nhất một

lần trong mọi giao tác. Hơn nữa tất cả thực hiện được tạo ra bởi PCP-DA là

khả tuần tự.

Sau đây chúng ta xét sự thực hiện của các giao tác trong PCP-DA được

Hình 1.6: Thực hiện của các giao tác dưới PCP-DA

Chúng ta giả sử như trong ví dụ của R/WPCP. Ngồi ra chúng ta giả sửmức ưu tiên của hệ thống ban đầu được thiết lập nhỏ hơn tất cả các giao tác

trong hệ thống. Tại thời điểm /=0, 7; bat đầu thực hiện. Tai thời điểm = 2,

7; u cầu khố ghi :;. Vì khơng có giao tác nào đang giữ một khố doc

trên z;, LCI là đúng. 7; được phép ghi z;. Tai thời điểm /=4, 7; bat đầu

thực hiện. Tại thời điểm /= 6, 7, u cầu khố ghi z;. Vì +, khơng bị một

khoá đọc bởi các giao tác khác, LCI đúng. Vì vậy, 7; được phép ghi 1, và

ưu tiên hơn 7›.

Tại thời điểm /= 8, 7; yêu cầu khoá đọc trên +; thành cơng vi LC2 đúng

(vì mức ưu tiên của giao tấc 7, cao hơn mức ưu tiên cao nhất của hệ thống).

Tại thời điểm ‘= 10, 7; kết thúc thực hiện và giải phóng khố. 7; tiếp tụcthực hiện. Tại thời điểm ‘= 14, 7; yêu cầu ghi +; thành công. Vi LCI đúng.

Tại thời điểm /= 16, 7, bat đầu thực hiện. 7, có thể đọc cả z; và x» tạithời điểm ‘= 18 và ‘= 20 tương ứng bởi vì LC2 đúng. Tại thời điểm /= 22,

7, hồn thành thực hiện và giải phóng khố. 7; tiếp tục thực hiện và hoàn

31

</div>Trang 30<div class="page_container" data-page="30">

thành tại t= 26. So sánh với thực hiện của các giao tác dưới R/WPCP trong

Hình 1.4. Chúng ta có thể dễ dàng thấy rằng dưới R/WPCP, thời gian nghẽn

tôi nhất của 7; bởi 7; là 5 đơn vi. 7, bị nghẽn bởi 7; từ thời điểm ¡=4 tới

thời điểm ‘= 9. Với PCP-DA, thời gian nghẽn của 7› được loại bỏ bởi vì 7)

được phép truy cập +; mặc dù +; đang bị ghi bởi 7;. Điều kiện lập lich của

PCP-DA tốt hơn R/WPCP.

1.5 Kết luận

Chương này chúng tôi đã trình bày mọt số khái niệm cơ bản trong hệ thống

CSDL, hệ thống CSDL thời gian thực như điều khiển tương tranh, điều kiệnđúng và tính khả tuần tự, mơ hình CSDL thời gian thực, các đặc điểm dữ liệu

và giao tác, điều khiển tương tranh thời gian thực, đảo ngược mức ưu tiên,kế thừa mức ưu tiên. Chúng tôi cũng trình bày và so sánh một số giao thức

điều khiển tương tranh tiêu biểu như giao thức R/WPCP, giao thức BAP, giao

thức PCP-DA. Các kết quả nghiên cứu này sẽ rất cần thiết cho việc nghiên

cứu xây dựng mô hình hình thức của hệ thống CSDL thời gian thực, đặc tả

các điều kiện đúng thực hiện song song của các giao tác, đặc tả và kiểm

chứng hình thức các điều kiện duy trì tính nhất qn thời gian cho mỗi loại

giao tác, phát triển phương pháp luận để đặc tả và kiểm chứng hình thức các

giao thức điều khiển tương tranh, cải tiến một số giao thức điều khiển tương

tranh, cũng như việc nghiên cứu ứng dụng CSDL thời gian thực trong những

chương sau.

32

</div>Trang 31<div class="page_container" data-page="31">

CHUONG 2

LOGIC TÍNH TỐN KHOANG

Chương này trình bày về logic tính tốn khoảng, một cách tiếp cận logic để

thiết kế hình thức các hệ thống thời gian thực. Trong DC, thời gian là liên

tục và sử dụng hàm giá trị logic trên thời gian để mơ hình các trạng thái và

các sự kiện của hệ thống thời gian thực. Thời khoảng của một trạng thái trên

một khoảng thời gian là thời gian tích luỹ được của trạng thái trên khoảng

đó và được xem như là độ đo đặc biệt hành vi trong hệ thống thời gian thực.

DC mở rộng logic khoảng với một số phép tốn để đặc tả các thuộc tính của

khoảng trạng thái.

2.1 Logic khoảng

Để tiện lợi cho việc nghiên cứu các tính chất cha mơ hình CSDL thời gian

thực ở các chương sau, chúng ta giới thiệu tóm tắt lại cú pháp, ngữ nghĩa và

hệ thống chứng minh cho logic khoảng.

2.1.1 Cú pháp

Các công thức của logic khoảng được xây dựng từ tập các ký hiệu sau:

GVar: Tập vô hạn các biến tổng thể z.¿.:..., không phụ thuộc vào thoi

Tuar: Tap vô hạn các biến thời gian ‹.:›.:;..., ý nghĩa của một biến thời

gian là một hàm khoảng giá trị thực. Chúng ta giả thiết rằng tôn tại

33

</div>Trang 32<div class="page_container" data-page="32">

biến thời gian đặc biệt / c Tvar. /: Hàm khoảng ký hiệu cho độ dài

PLetter: Tap vô hạn các ký hiệu mệnh dé thời gian YV. Y.... Mỗi biến mệnh

đề thời gian là một hàm khoảng giá trị logic.

Tập các hạng thức, ký hiệu 0, được định nghĩa như sau:

¿. Vi dụ, khoảng {b.c| thoả mãn ¿^ ¿, khi và chỉ khi, tồn tại im (b < in < c)

sao cho |b.z| thoả mãn ø và |m,e| thoả mãn ¿:

Các liên kết logic, các lượng từ và các thể thức được định nghĩa như sau:

</div>Trang 33<div class="page_container" data-page="33">

trong một số khoảng con của khoảng đó. 5¿ có giá tri True khi và chỉ khi

ó đúng trong mọi khoảng con của khoảng đó.

2.1.2 Ngữ nghĩa

Trước tiên chúng ta xét một số định nghĩa cơ bản.

Time và khoảng: Mơ hình cho thời gian là các số thực R. Khoảng thời

gian được ký hiệu bởi các khoảng số thực từ điểm bát đầu tới điểm kết thúc.

Intv ~ {\b.c| | be ER và b< c}

Ham va cac quan hé

Một hàm tổng thể / là một hàm trên các số thực không phụ thuộc vào

thời gian:

Một quan hệ tổng thể (¿ là một hàm giá trị logic trên các số thực không

phụ thuộc vào thời gian:

G:R" — {tt,ff}

Các ky hiệu hàm, như +, -, *, / và các ký hiệu quan hệ như <. .>. /,...

mang nghĩa thông thường. Đặc biệt tt và ff mang ý nghĩa của True và False,

</div>Trang 34<div class="page_container" data-page="34">

Các biến thời gian và các ký hiệu mệnh đề được thể hiện như sau:

/Z(.Y)(b.cl) c {tt,ff}. với mọi Y € PLetters

Ký hiệu _ được sử dụng để viết gop hai hàm trong một thể hiện. Nghĩa là

một sự kết hợp giữa một hàm khoảng giá trị thực với mỗi biến thời gian và

một hàm khoảng giá trị logic với mỗi ký hiệu mệnh đề thời gian. Chúng ta

và được định nghĩa quy nạp trên cấu trúc của các công thức như sau:

1. Z|X|(@.Ib.c|) - tt khi và chỉ khi V;(.e|) - tt.

2. Z|G(0:...9„)|(V.|b.e|) - tt khi và chỉ khi G(‹¡...c„) — tt

Trong đó ‹, - /7{6,|(Y. lb.e|) VỚI ¿ - 1...n.

3. Z[¬¿|(. |b,c|) - tt khi và chỉ khi 7|ø|(V. |b.e|) - ff.

4. 7|óvu|(V. |b.e|) — tt khi và chỉ khi 7 |ó|(V. |b. e|) tt hoặc 7 [u|(V. |b. e|)

36

</div>Trang 35<div class="page_container" data-page="35">

5. /|3+z.ø|(.|b.e|) - tt khi và chỉ khi /7|ø|(Y“, |b.e|) — tt với một số 3 mà

tương đương + với V nghĩa là V(y) - Y'(„) với mọi biến tổng thể y (/ z).

6. Zlø^]|(V, Íb.e]) = tt khi và chỉ khi 7[¢](V, [b, m]) — tt và Z[W](V. lm. eÌ)

tt với một số € |b, «|.

Cơng thức thoả được & Hang đúng

⁄Z.Y.lb.c' |„ ở. với mọi thể hiện 7, giá tri gán V và khoảng I.‹|.

Một công thức ø là thoả được, được viết là /7.V,|b.c| |v @, khi và chỉ

khi Zlø|(V.|b.el) - ó với một số thể hiện 7, giá tri gin V và khoảng |b. «|.

2.1.3 Hé thống chứng minh

Để thiết lập các tiên đề và các luật suy dẫn, chúng ta cần xét một số định

Một hạng thức (cơng thức) được gọi là mềm nếu nó chứa một biến thời

gian, ký hiệu độ dài / hoặc một ký hiệu mệnh dé thời gian.

Một hạng thức (công thức) không phải là mềm được gọi là cứng.

Các tiên đề của logic khoảng [20]:

ow) > wv nếu ¿ là một công thức cứng.

=v.o~v) => 3z(o^u) nếu x không là biến tự do trong ¿.

3z.¿) > 3z(ó¿^) nếu x khơng là biến tự do trong ó.

37

</div>Trang 36<div class="page_container" data-page="36">

Các luật suy dẫn của logic khoảng:

MP: nếu ¿ và (¿ => ¿) thì ¿.G: nếu ¢ thi (V.r)¢.

Một chứng minh của ¿ là một dãy hữu hạn các công thức s; - - -¿„, trong

đó ó„ là ¿ và mỗi ó¿, hoặc là các tiên đề ở trên hoặc nhận được bởi áp dụng

một trong các luật suy diễn tới các thành viên trước đó trong dãy. Chúng ta

viết - ø để thể hiện rằng có tồn tại một chứng minh của ø trong IL va chúng

=> (wy

Một suy dan của © trong IL từ một tập các công thức |’ là một dãy cáccơng thức o;, ---ø„, trong đó ø„ là ¿ và mỗi ø, hoặc là một thành viên của |’

hoặc là một tiên đề ở trên hoặc nhận được bởi áp dụng một trong các luật

suy diễn tới các thành viên trước đó trong dãy. Chúng ta viết | + ¿ để thể

hiện rằng có tồn tại một suy dẫn ø từ I' trong IL và chúng ta viết I'.¿ó - ¿

với (I`U {ó}) 0.

2.2 Logic tính tốn khoảng

Phần này, trình bày cú pháp, ngữ nghĩa và hệ thống chứng minh cho logictính tốn khoảng. Sau đó trình bày các định lý và các luật của DC, điều này

rất hữu ích khi xây dựng các chứng minh ở các phần sau.

2.2.1 Cú pháp

DC mở rộng logic khoảng, với các biến thời gian v c 7V'ar có cấu trúc như

Trong đó S gọi là một biểu thức trạng thái va được tạo ra từ một tập các

biến trạng thái SVar: P.Q.h...., và được định nghĩa như sau:

te | 1| P| Sy |] Se V Se

38

</div>Trang 37<div class="page_container" data-page="37">

Chúng ta ký hiệu:

II = £-0

[Ss] = j§-? vn s0

Một cơng thức |S] thoả mãn trong khoảng |). «| khi va chỉ khi b < ¢ va

S bằng 1 hầu khắp trong |b. c|. Thực tế, 5 có thể thay đổi với hữu han trạng

thái, 5 có thể bằng 0 nhiều nhất một số hữu hạn các điểm trong |b. |.

e Z(P): Time — {0,1}, với mọi biến trạng thái 7. 7(/) có nhiều nhất một

số hữu hạn các điểm khơng liên tục trong mọi khoảng |b.c|. Bởi vậy,T(P) có thể tích phân được trong mọi khoảng.

e 7(/): Intv — R và 7(/)|b.e| — e — b, va

e 7(YV) : Intv — {tt,ff}, với mọi ký hiệu mệnh đề Y.

Ngữ nghĩa của một biểu thức trạng thái 5 trong thể hiện 7 là một hàm

7[S| : Time — {0,1}

được định nghĩa quy nap trên cấu trúc của biểu thức trang thái như sau:

7|0|() 0T|1|\(t)

</div>Trang 38<div class="page_container" data-page="38">

Chúng ta sẽ sử dung ký hiệu 5; thay cho 7| S|

Các biến thời gian (thời khoảng trạng thái) là một hàm

Công thức trong thể hiện 7 với giá trị gan V và khoảng |). c| là một ham:

7lol : Valx Intv — {tt,ff}.

</div>Trang 39<div class="page_container" data-page="39">

DC hoặc nhận được bởi áp dụng một trong các luật suy diễn của DC tới các

thành viên trước đó trong dãy. Chúng ta viết | » thể hiện có tồn tại một

chứng minh của ø¿ trong DC va chúng ta gọi ø là một dinh lý trong DC.

Suy dẫn trong DC được định nghĩa như suy dẫn trong IL và chúng ta viếtI'- » để thể hiện rằng có tồn tại một suy dẫn của « trong DC từ |.

2.2.4 Định lý cua DC

Sử dung hệ thống chứng minh của DC, chúng ta có thể chứng minh các định

lý sau:

DC] {S84 §=(

Chứng minh: Sau đây là một chứng minh cua DCI:

Ll. {8 + [¬ể#= j(GẤ¬¬ð)+ f(S VAS) DCA4

Chứng minh: Dé chứng minh DC3, chúng ta nhận thấy rằng $, <= (5; v (aS) ^ S¡

(=z+z)A[S]J) & ((Œ= z)^ [SI)^(Œ = y) A [ST))

Chứng minh: Chứng minh chiều = có thể dé dàng được chứng minh bởi

sử dụng DCA5 và L2. Để chứng minh chiều ngược lại, sử dụng L2 chúng

ta có thể chia khoảng như sau ( +)^( „). Giả thiết các giá trị (s trên

4]

</div>Trang 40<div class="page_container" data-page="40">

hai khoảng con,

Chứng minh: Chiêu = là trường hợp đặc biệt của DC6. Chiều = có thể

được chứng minh như sau:

Chương này giới thiệu tóm tắt về logic khoảng và logic tính tốn khoảng với

cú pháp, ngữ nghĩa và một hệ thống chứng minh đây đủ, sau đó là các chứng

minh một số định lý của DC. Đặc biệt các định lý trên cũng đã được chúng

tôi chứng minh một cách tự động thông qua sự trợ giúp của cơng cụ kiểm

chứng PC/DC [2].

Dua vào logic tính tốn khoảng, chúng tơi sẽ phát triển một mơ hình tốn

học cho các hệ thống CSDL thời gian thực. Đưa ra một đặc tả điều kiện

42

</div>