TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN VÀ PHÂN MẢNH
Những nét chung nhất về cơ sở dữ liệu phân tán
Cơ sở dữ liệu phân tán (CSDL) là tập hợp dữ liệu có mối quan hệ logic, được lưu trữ trên các trạm khác nhau trong một mạng máy tính Hệ thống CSDL phân tán giúp tăng cường khả năng truy cập vào các cơ sở dữ liệu lớn trên mạng, với mỗi máy tính quản lý một CSDL thành phần, được gọi là node hoặc site.
Hệ quản trị cơ sở dữ liệu phân tán (DBMS) là phần mềm quản lý cơ sở dữ liệu, cung cấp tính tự trị cho từng cơ sở dữ liệu thành phần, cho phép quản trị độc lập và riêng biệt Định nghĩa này nhấn mạnh hai khía cạnh quan trọng của cơ sở dữ liệu phân tán.
1- Tính phân tán: thực tế dữ liệu không cư trú ở cùng một trạm, vì vậy chúngta có thể phân biệt một CSDL phân tán với CSDL tập trung
2- Sự tương quan logic: Các dữ liệu có một số tính chất ràng buộc lẫn nhauvà như vậy có thể phân biệt CSDL phân tán với tập các CSDL địa phương hoặc với các tệp ở các trạm khác nhau trên mạng
3 - Các đặc trưng trong suốt của CSDL phân tán thể hiện ở chỗ:
Trong suốt phân tán cho phép xử lý dữ liệu trên hệ CSDL phân tán giống như CSDL tập trung, giúp người sử dụng không cần quan tâm đến việc dữ liệu đã được phân mảnh hay lưu trữ ở đâu Điều này mang lại sự tiện lợi và hiệu quả trong việc truy cập và quản lý dữ liệu.
Tính trong suốt địa điểm cho phép người sử dụng truy cập cơ sở dữ liệu từ bất kỳ nút nào trên mạng mà không cần biết vị trí lưu trữ vật lý của dữ liệu Khi thực hiện truy vấn, người dùng chỉ cần chỉ định tên dữ liệu mà không cần quan tâm đến vị trí cụ thể Hệ thống tự động xử lý các thao tác lấy hoặc cập nhật dữ liệu từ xa theo yêu cầu Điều này giúp người dùng bỏ qua các bản sao dữ liệu hiện có tại mỗi vị trí, cho phép di chuyển hoặc tạo mới các bản sao dữ liệu mà không ảnh hưởng đến các ứng dụng đang chạy.
+ Trong suốt tên: Khi một đối tượng đã được đặt tên thì có thể truy nhập chính xác không cần đặc tả thêm;
Trong suốt bản sao, sự nhân bản là quá trình sao chép và duy trì dữ liệu trong hệ CSDL phân tán, cho phép cùng một dữ liệu được sử dụng tại nhiều vị trí khác nhau Việc lưu trữ các bản sao trên nhiều nút không chỉ tăng cường hiệu suất và độ tin cậy mà còn nâng cao tính sẵn sàng của hệ thống Các ứng dụng có thể truy cập dữ liệu tại các nút mà không cần truy cập từ xa, giảm tải trên mạng lớn Hệ thống vẫn hoạt động liên tục ngay cả khi các nút từ xa gặp sự cố, và người sử dụng không nhận biết rằng đó là các bản sao, nhờ vào việc dữ liệu luôn được cập nhật và đồng bộ với dữ liệu gốc.
Trong suốt phân mảnh trong cơ sở dữ liệu phân tán cho phép tách các quan hệ thành các bộ dữ liệu hoặc quan hệ con, lưu trữ trên nhiều nút khác nhau Người sử dụng không cần quan tâm đến sự phân mảnh này, vì các truy vấn dữ liệu vẫn được thực hiện giống như trong cơ sở dữ liệu tập trung.
- Trong suốt giao dịch: CSDL phân tán cho phép một giao dịch có thể cập nhật, sửa đổi dữ liệu trên các nút khác nhau
Trong suốt thất bại, hệ thống cần đảm bảo hoạt động bình thường ngay cả khi một nút bị hỏng Điều này có thể đạt được thông qua cơ chế tạo bản sao hoặc bằng cách tiếp tục hoạt động trên các nút không gặp sự cố.
Trong suốt quá trình thao tác, người dùng có thể thực hiện các câu lệnh để truy cập dữ liệu đơn giản từ cơ sở dữ liệu tại nút cục bộ hoặc từ xa Các thao tác xử lý dữ liệu từ xa được thiết kế không phức tạp, đảm bảo tính nhất quán và tương tự như khi thao tác trên hệ thống cơ sở dữ liệu không phân tán.
- Trong suốt về tính không thuần nhất: Cho phép hỗn hợp nhiều hệ quản trị
CSDL khác nhau với các khả năng trao đổi dữ liệu, xử lý cập nhật dữ liệu, xử lý giao tác phân tán trên toàn hệ thống
4- Đối với CSDL tập trung, tính dư thừa hạn chế được càng nhiều càng tốt Trong khi đó, CSDL phân tán có tính dư thừa dữ liệu vì:
- Tính cục bộ của chương trình ứng dụng sẽ tăng nếu dữ liệu đặt ở nhiều nơi mà chương trình ứng dụng cần
Hệ thống có khả năng sẵn sàng cao, vì khi xảy ra lỗi ở bất kỳ phần nào trong hệ thống, hoạt động của chương trình ứng dụng vẫn không bị ảnh hưởng.
5 Trong CSDL phân tán, dữ liệu được chia ra thành nhiều phần nhỏ và chỉ có một bản sao logic tổng thể duy nhất để tiện cho việc truy xuất dữ liệu; cấu trúc truy xuất phức tạp không phải là công cụ chính để truy xuất hiệu quả (hiệu quả theo nghĩa là thời gian tìm kiếm và chuyển dữ liệu nhỏ nhất, chi phí truyền thông thấp nhất) Mỗi cách thức truy xuất CSDL phân tán được người lập trình viết hoặc tạo ra bởi một bộ tối ưu Cách viết và truy cập CSDL phân tán cũng giống như viết chương trình duyệt trong CSDL tập trung Công việc mà chương trình duyệt này làm là xác định xem có thể truy cập đến được bao nhiêu CSDL con
6 Trong CSDL phân tán, vấn đề điều khiển giao tác tự trị có ý nghĩa quan trọng Giao tác tự trị là phương tiện đạt được sự toàn vẹn trong CSDL; Mặt khác, vấn đề an toàn CSDL cũng phức tạp hơn vì còn liên quan đến mạng truyền thông
CSDL phân tán có một số ưu và nhược điểm sau:
CSDL phân tán có tính hữu dụng cơ bản là tích hợp dữ liệu từ các CSDL vật lý riêng biệt thành một hệ thống logic, cho phép người sử dụng trên mạng truy cập dễ dàng.
Hệ quản trị cơ sở dữ liệu phân tán cho phép quản lý dữ liệu với nhiều mức độ trong suốt, giúp che giấu các đặc tính phân tán khỏi người sử dụng.
CSDL phân tán tăng cường độ tin cậy và khả năng sẵn sàng so với CSDL tập trung, vì khi một nút gặp sự cố, các nút khác vẫn có thể hoạt động bình thường Điều này giúp hệ thống không bị ngừng hoạt động và đảm bảo rằng dữ liệu vẫn có thể truy cập được Để nâng cao độ tin cậy và tính sẵn sàng, việc áp dụng cơ chế tạo bản sao trên nhiều nút là cần thiết, giúp bảo vệ dữ liệu và ứng dụng khỏi sự cố tại các nút riêng lẻ.
- Cải thiện hiệu năng, do dữ liệu của CSDL phân tán được đặt gần nơi xử lý nên hiệu năng được cải thiện đáng kể
- Cho phép thêm CSDL mới, tăng kích cỡ CSDL, thêm bộ xử lý, thêm các CSDL thành phần trong CSDL phân tán
- Độ phức tạp thiết kế và cài đặt hệ thống tăng: Hệ quản trị CSDL phân tán phải bổ sung thêm các chức năng như:
+ Theo dõi dấu vết dữ liệu;
+ Xử lý các truy vấn phân tán;
+ Quản lý giao dịch phân tán;
+ Phục hồi CSDL phân tán;
+ Quản lý các bản sao;
+ Quản lý thư mục - catalog phân tán
- Khó điều khiển tính nhất quán về dữ liệu;
- Các phần mềm hệ thống đảm bảo quản trị, duy trì kết nối, trao đổi dữ liệu trên mạng là rất khó khăn;
- Bảo mật khó khăn Ở mức vật lý, những đặc trưng phân tán được thể hiện rõ:
- Có nhiều máy tính được gọi là các nút/trạm;
Vấn đề phân mảnh trong cơ sở dữ liệu phân tán
Trong quá trình thiết kế, các quan hệ được phân mảnh thành các quan hệ nhỏ hơn Các câu hỏi có tương hỗ lẫn nhau được quan tâm gồm:
1 Tại sao lại cần phân mảnh?
2 Chúng ta nên phân mảnh như thế nào?
3 Chúng ta nên phân thành bao nhiêu mảnh?
4 Có cách nào để kiểm tra tính chính xác của sự phân mảnh?
5 Chúng ta nên cấp phát các mảnh như thế nào cho các nút?
6 Thông tin cần thiết cho phân mảnh và cấp phát là gì?
Theo quan điểm phân tán dữ liệu, việc không phân mảnh giá trị dữ liệu là rất quan trọng Trong các hệ thống tệp phân tán, dữ liệu được phân tán dựa trên toàn bộ các tập tin Để phân mảnh hiệu quả, cần xác định đơn vị phân tán phù hợp; một quan hệ không phải là đơn vị thích hợp vì việc truy cập ứng dụng chỉ diễn ra trên các tập con của nó Hơn nữa, nếu các ứng dụng có khung nhìn xác định trên một quan hệ ở các nút khác nhau, việc phân mảnh sẽ giúp giảm thiểu việc truy cập dữ liệu từ xa, hạn chế rắc rối trong cập nhật và giải quyết vấn đề giới hạn lưu trữ Cuối cùng, phân mảnh cũng cho phép khả năng truy vấn song song, từ đó nâng cao mức độ xử lý đồng thời.
Mặc dù việc phân mảnh mang lại lợi ích, nhưng nó cũng gây ra nhiều thách thức Các ứng dụng với yêu cầu mâu thuẫn có thể gặp khó khăn trong việc tách quan hệ thành các quan hệ con riêng biệt, dẫn đến giảm hiệu suất khi quan điểm được xác định trên nhiều quan hệ con Việc lấy dữ liệu từ hai mảnh và kết nối chúng trở nên phức tạp, trong khi việc tối thiểu hóa các liên kết đã phân tán là một bài toán cốt lõi trong quá trình phân mảnh.
Vấn đề kiểm soát ngữ nghĩa dữ liệu, đặc biệt trong việc kiểm tra tính toàn vẹn, trở nên phức tạp do sự phân mảnh, khi các thuộc tính có thể được phân bổ ở các quan hệ con khác nhau tại các nút khác nhau.
Mô hình quan hệ được thể hiện dưới dạng bảng, và nhiệm vụ chính là tìm ra các phương pháp chia bảng thành những bảng nhỏ hơn Có hai lựa chọn rõ ràng: chia bảng theo chiều ngang hoặc theo chiều dọc.
Quyết định mức độ phân mảnh cơ sở dữ liệu (CSDL) là yếu tố quan trọng ảnh hưởng đến hiệu suất truy vấn Các vấn đề liên quan đến lý do phân mảnh là một phần trong câu trả lời cho câu hỏi mà chúng ta đang giải quyết Mức độ phân mảnh có thể thay đổi từ không phân mảnh cho đến phân mảnh tối đa, bao gồm phân mảnh ngang với từng bộ và phân mảnh dọc với từng thuộc tính.
Sự phân mảnh có thể được lồng ghép theo nhiều kiểu, tạo ra phân mảnh hỗn hợp Mặc dù không coi phân mảnh hỗn hợp là một chiến lược nguyên thủy, nhiều phân vùng thực tế lại mang tính chất hỗn hợp.
Để xác định mức độ phân mảnh phù hợp cho các ứng dụng trên CSDL, cần tìm ra sự thỏa hiệp giữa các đơn vị phân mảnh quá lớn và quá nhỏ Mỗi ứng dụng cần được đặc trưng bằng một số tham số, từ đó xác định các mảnh riêng lẻ dựa trên giá trị của các tham số này Trong phần tiếp theo, chúng tôi sẽ mô tả cách thực hiện các đặc tính này cho các kiểu phân mảnh đã được lựa chọn.
1.2 4 Các quy tắc phân mảnh
Trong quá trình phân mảnh, chúng ta sẽ áp dụng ba quy tắc đồng thời nhằm đảm bảo rằng cơ sở dữ liệu (CSDL) không bị thay đổi ngữ nghĩa.
1 Tính đầy đủ (completeness) Nếu một quan hệ R bị phân mảnh thành n quan hệ con FR = {R1, R2, , Rn}, mỗi thuộc tính trong R cũng có thể được tìm thấy trong một hoặc nhiều hơn các Ri Đặc tính này bảo đảm rằng các dữ liệu trong một quan hệ toàn cục được ánh xạ thành các quan hệ con mà không bị tổn thất Lưu ý rằng trong trường hợp phân mảnh ngang, người ta thường nhắm đến một “bộ”, trong khi trong trường hợp phân mảnh theo chiều dọc, nhắm đến một “thuộc tính”
2 Tính tái thiết (reconstruction) Nếu một quan hệ R được phân mảnh thành n mảnh FR = {R1, R2, , Rn}, thì có thể xác định một toán tử quan hệ
sao cho: R =Ri, Ri FR
Toán tử có sự khác biệt giữa các dạng phân mảnh ngang và dọc, nhưng điều quan trọng là nó có thể được xác định rõ ràng Khả năng tái cấu trúc mối quan hệ từ các mảnh dữ liệu đảm bảo rằng các ràng buộc xác định trên dữ liệu sẽ được duy trì.
3 Tính tách rời (disjointness) Nếu một quan hệ R được phân mảnh theo chiều ngang thành n mảnh FR = {R1, R2, , Rn} và bộ dữ liệu (bản ghi) tj nằm trong Rj thì nó không nằm trong bất kỳ quan hệ con Rk khác (k ≠ j) để bảo đảm các mảnh ngang là rời nhau Nếu quan hệ R được phân mảnh theo chiều dọc, thì các khóa chính của nó phải lặp lại trong tất cả các mảnh của nó (để tái thiết)
Do đó, trong trường hợp phân mảnh dọc, sự tách rời chỉ được xác định trên các thuộc tính không phải là khóa chính của quan hệ
1.2.5 Các chiến lược phân mảnh
Có hai chiến lược phân mảnh cơ bản: ngang và dọc Từ đó, có thể mở rộng thành chiến lược tích hợp phân mảnh kiểu lai ghép (hybrid) [5]
Phân mảnh ngang là quá trình cắt một quan hệ thành nhiều khúc, mỗi khúc chứa tập con giá trị của các bộ trong quan hệ đó Kết quả của quá trình này là các quan hệ con, số lượng phụ thuộc vào điều kiện ràng buộc của các thuộc tính Các bộ trong các quan hệ con là tách biệt nhau, và phân mảnh ngang thực chất là phép chọn quan hệ thỏa mãn một biểu thức điều kiện đã được xác định.
Có hai kỹ thuật phân mảnh ngang: nguyên thủy và dẫn xuất Phân mảnh ngang nguyên thủy thực hiện thông qua các vị từ được định nghĩa trên chính quan hệ, trong khi phân mảnh ngang dẫn xuất dựa vào các vị từ được định nghĩa trên quan hệ khác.
Phân mảnh dọc (Vertical Fragmentation) là quá trình chia một quan hệ R thành các mảnh con R1, R2, , Rr, mỗi mảnh chứa một tập hợp các thuộc tính của R cùng với khóa chính Mục tiêu của phân mảnh dọc là tối ưu hóa việc xử lý dữ liệu bằng cách tạo ra các quan hệ nhỏ hơn, cho phép nhiều ứng dụng hoạt động trên từng mảnh riêng lẻ Lược đồ phân mảnh "tối ưu" được thiết kế nhằm giảm thiểu thời gian thực hiện cho các ứng dụng chạy trên các mảnh này.
Phân mảnh dọc cho phép các truy vấn với quan hệ nhỏ hơn, do đó dẫn đến một số lượng nhỏ các truy cập đến nút.
CÁC ĐẶC TÍNH CỦA PHÂN MẢNH DỌC
Định hướng heuristic để phân mảnh dọc
Phân mảnh dọc của một quan hệ R (với R có các thuộc tính) tạo ra các mảnh r1, r2, , rk, mỗi mảnh chứa một tập con thuộc tính của R cùng với khóa của r Mục tiêu chính của việc phân mảnh dọc là chia nhỏ quan hệ thành các quan hệ nhỏ hơn, giúp nhiều ứng dụng có thể hoạt động độc lập trên từng mảnh Trong bối cảnh này, một phân mảnh được coi là “tối ưu” khi nó tạo ra một lược đồ phân mảnh giúp giảm thiểu thời gian thực thi của các ứng dụng chạy trên các mảnh đó.
Phân mảnh dọc đã được nghiên cứu trong các hệ cơ sở dữ liệu tập trung và phân tán, với mục đích chính là sử dụng nó như một công cụ thiết kế để giảm số lượng truy xuất và tiết kiệm bộ nhớ So với phân mảnh ngang, phân mảnh dọc phức tạp hơn do có nhiều lựa chọn cho việc phân hoạch Việc tìm kiếm lời giải tối ưu cho bài toán phân mảnh dọc là rất khó khăn, dẫn đến việc phát triển hai loại heuristic cho phân mảnh dọc một quan hệ.
Kỹ thuật nhóm thuộc tính, được Hammer và Niamir giới thiệu lần đầu tiên, bắt đầu bằng việc gán mỗi thuộc tính cho một mảnh Tại mỗi bước, một số mảnh sẽ được nối lại cho đến khi đạt được một tiêu chuẩn nhất định.
1979 cho các CSDL tập trung và về sau được Sacca và Wiederhold dùng năm
1985 cho các CSDL phân tán
Tách mảnh là quá trình bắt đầu từ một quan hệ và quyết định cách phân mảnh có lợi dựa trên hành vi truy xuất của các ứng dụng trên các thuộc tính Kỹ thuật này lần đầu tiên được Hoffer và Severance thảo luận cho thiết kế cơ sở dữ liệu tập trung vào năm 1975, và sau đó đã được Navathe cùng các đồng tác giả mở rộng cho môi trường phân tán vào năm 1984.
Chú ý rằng, phương pháp tách mảnh chỉ đề cập đến các thuộc tính không tham gia vào khóa chính.
Đặc tính có nối không mất thông tin
2.2.1 Khái niệm có nối không mất thông tin
Phân mảnhdọc một lược đồ quan hệ W(R), với R={A 1 ,A 2 ,…,A n }, là thay nó bằng một tập ={R 1 , R 2 , ,R k } trong đó R i là cáctập con của R sao cho R =
R 1 R 2 R k Các tập R i không nhất thiết phải tách biệt mà các R i có thể chứa các thuộc tính khóa [8]
Trong phần này, chúng ta sẽ minh họa các lược đồ quan hệ về nhà cung cấp hàng cho siêu thị, ví dụ như SUPPLIERS (SNAME, ITEM, PRICE, ADDR) chứa thông tin về tên, hàng hóa, giá và địa chỉ của nhà cung cấp Để đơn giản, chúng ta sử dụng các chữ viết tắt cho các thuộc tính: S(SNAME), I(ITEM), P(PRICE), A(ADDR) Trước khi thực hiện các thuật toán phân mảnh, cần lưu ý rằng lược đồ trên không tối ưu do dữ liệu dư thừa; mỗi khi nhập thêm mặt hàng mới, chúng ta phải nhập lại địa chỉ của nhà cung cấp, mặc dù điều này chỉ cần thực hiện một lần Nếu chia lược đồ thành hai lược đồ SUP1(S,A) và SUP2(S,I,P), chúng ta sẽ có một cơ sở dữ liệu tốt hơn, loại bỏ các nhược điểm trên Chúng ta cũng dễ dàng chứng minh rằng SUP1 và SUP2 là các quan hệ thuộc dạng chuẩn BCNF.
Vậy có những phân mảnh quan hệ thành các dạng chuẩn sẽ tối ưu cho phần thiết kế CSDL tập trung và cả phân tán
Trong lược đồ SUP (S, A, I, P) với các phụ thuộc hàm S → A và SI → P, việc thay thế sơ đồ SUP bằng hai lược đồ SUP1 và SUP2 giúp loại bỏ một số vấn đề như dư thừa dữ liệu Tuy nhiên, câu hỏi đặt ra là liệu việc phân mảnh SUP thành SUP1 và SUP2 có đảm bảo khả năng tái thiết SUP hay không và quá trình này có làm mất thông tin hay không?
Giả sử r là một quan hệ trên tập thuộc tính {S, A, I, P} Khi CSDL sử dụng SUP1 và SUP2 thay cho SUP (S,A, I, P), quan hệ r được tách thành hai sơ đồ {S, A} và {S, I, P}, tương ứng với r.SA và r.SIP Vấn đề đặt ra là liệu quan hệ r có thể được tái thiết từ r.SA và r.SIP thông qua phép nối tự nhiên hay không.
Trong bài viết này, chúng ta sẽ thảo luận về khẳng định rằng r = r.SA |>
W2 = ; Wcl =
W4 = khi đó = (R1,…… Rk) có nối không mất thông tin ứng với F
Kiểm tra tính nối không mất bằng thuật toán Chase: Để cho tiện trong các bảng kiểm tra ta thêm cột các R
Bảng khởi đầu (các ô rỗng chứa các bịj)
Bảng sau khi sửa cho phù hợp với các phụ thuộc hàm
Bảng có một dòng toàn a nên phân mảnh có nối không mất thông tin
Chú ý [8]: với một sơ đồ quan hệ W = , có thể có nhiều cách phân mảnh
R thành các lược đồ con có nối không mất thông tin ứng với F.
Đặc tính bảo toàn phụ thuộc
2.3.1 Định nghĩa phân mảnh dọc bảo toàn phụ thuộc
Một phân mảnh cần có đặc tính không mất để có thể khôi phục lại quan hệ gốc, thông qua việc nối các phụ thuộc của nó.
Phân mảnh R (R1, R2, , Rk) của lược đồ quan hệ R không chỉ ảnh hưởng đến tập phụ thuộc hàm F mà còn cho phép suy ra tập phụ thuộc F từ những hình chiếu của F trên R1 Điều này cho thấy tầm quan trọng của việc phân tích các phụ thuộc hàm trong bối cảnh phân mảnh cơ sở dữ liệu.
Về trực quan hình chiếu của F trên tập các thuộc tính Z ký hiệu là z (F) hoặc FZ) là tập các phụ thuộc X Y thuộc F + sao cho XY Z (chú ý rằng X
Y không nhất thiết thuộc F; chỉ cần thuộc F + )
Ta nói phân mảnh dọc = (R 1 , R 2 , R k ) của lược đồ R có bảo toàn phụ thuộc (bảo toàn phụ thuộc hàm F) nếu hợp của tất cả phụ thuộc trong đó
Ri (F) với i =1,2,….,k xác định được tất cả các phụ thuộc hàm trong F
Cần bảo toàn tập F vì các phụ thuộc trong F là các ràng buộc toàn vẹn cho lược đồ quan hệ R Tập F đóng vai trò quan trọng trong sơ đồ quan hệ Nếu các phụ thuộc hình chiếu không suy ra được, việc biểu diễn R bằng = (R1, R2, Rk) có thể dẫn đến việc giá trị hiện hành của Ri không thỏa mãn F, mặc dù có nối không mất ứng với F Do đó, mỗi thao tác cập nhật trên các R sẽ cần kiểm tra lại các ràng buộc và tính toàn vẹn ngữ nghĩa.
Chúng ta xét lược đồ R có các thuộc tính là C, S và Z Giả sử có các phụ thuộc là CS Z và Z C Phân mảnh của lược đồ quan hệ R(C, S, Z) thành
R1(S, Z) và R2(C, Z) có nối không mất thông tin, bởi vì:
Tuy nhiên, chiếu của F = { CS Z, Z C} lên R1 là rỗng và lên R2 là
Hợp của các chiếu của F lên các R1 không dẫn đến CS Z, do đó phân mảnh này không bảo toàn các phụ thuộc, mặc dù nó vẫn có khả năng nối mà không mất thông tin.
2.3.2 Thuật toán kiểm tra tính phụ thuộc
Về nguyên tắc, có thể kiểm tra xem một phân mảnh = (R1,R2, ,Rk) có bảo toàn phụ thuộc F hay không Chúng ta chỉ cần tính F + rồi chiếu nó lên các
Ri Sau đó lấy hợp của các tập phụ thuộc kết quả kiểm tra xem tập này có tương đương với F hay không
Nhắc lại hai tập phụ thuộc F và G xác định trên cùng lược đồ R được gọi là tương đương nếu và chỉ nếu F + = G +
Chúng ta dễ dàng thấy rằng F tương đương với G nếu và chỉ nếu
Việc tính trực tiếp F + rất khó khăn, nhưng có một phương pháp kiểm tra tính bảo toàn mà không cần tính F + Thuật toán dưới đây sẽ giúp thực hiện điều này.
Thuật toán 2.3 (Kiểm tra tính bảo toàn các phụ thuộc):
Input: Một phân mảnh = (R1, R2, ,Rk) và tập các phụ thuộc F,
G = Ri (F) Output: Một khẳng định là có bảo toàn F hay không
G được định nghĩa là hợp của các phụ thuộc hàm Ri (F) Để xác định xem G có tương đương với F hay không, ta cần kiểm tra điều kiện G F + và F G + Điều này có nghĩa là mỗi phụ thuộc X Y trong F phải thuộc G + để khẳng định sự tương đương giữa hai tập hợp này.
Theo các tính chất của phụ hàm, nếu X Y thuộc G + thì Y phải là tập con của X + G Để xác định điều này, cần kiểm tra xem X + G có chứa Y hay không Nếu tất cả các phụ thuộc hàm X Y trong F đều được X + G chứa Y, thì F là tập con của G + và phân mảnh sẽ bảo toàn phụ thuộc Ngược lại, nếu không thỏa mãn điều kiện này, phân mảnh sẽ không bảo toàn phụ thuộc.
Xét tập các thuộc tính ABCD với ba tập phân mảnh {AB, BC, CD} và tập phụ thuộc F = {A → B, B → C, C → D, D → A} Trong tập phụ thuộc F, mỗi thuộc tính đều xác định tất cả các thuộc tính còn lại Mặc dù có thể ban đầu chúng ta nghĩ rằng khi chiếu F lên các tập AB, BC và CD sẽ không nhận được phụ thuộc D → A, nhưng thực tế điều này không đúng Khi thực hiện chiếu F, chúng ta thực sự đã nhận được phụ thuộc này.
F + trên các lược đồ con vì thế chiếu F trên AB chúng ta không chỉ thu được A
B mà cả B A Vậy AB (F) = {A B, B A} Tương tự ta có BC (F) = {B
C, C B}, CD (F) = {C D, D C} và rõ ràng G + = AB (F) BC (F) CD (F) = {A B, B A, B C, C B, C D, D C} = F +
Vậy chúng ta kết luận rằng phân mảnh này bảo toàn tập phụ thuộc F
2.3.3 Thuật toán phân mảnh dọc bảo toàn phụ thuộc
Thuật toán 2.4(Phân mảnh W thành các Wi có bảo toàn phụ thuộc):
Output: W1, W2 … có bảo toàn phụ thuộc;
Giả sử F = {X Y} Khi đó ta đặt vào mỗi Wi =
Nếu có tập các thuộc tính không xuất hiện trong F ta đặt một sơ đồ chứa các thuộc tính đó với tập phụ thuộc rỗng
Hiển nhiên phép phân mảnh theo thuật toán bảo toàn phụ thuộc vì tập các phụ thuộc F bảo toàn trong các Wi và R = R1 R2 R3… Rk
Xét W = Khi đó ta có phân mảnh W thành các Wi con:
W6 = Rõ ràng phân mảnh bảo toàn phụ thuộc vì Ri (F) = F
Chú ý [8]: có nhiều cách phân mảnh có bảo toàn phụ thuộc của một sơ đồ quan hệ
-Phân mảnh có bảo toàn phụ thuộc là không duy nhất;
- Với mọi sơ đồ quan hệ W = luôn tồn tại phân mảnh có bảo toàn phụ thuộc
2.3.4 Thuật toán kiểm tra phân mảnh dọc có nối không mất thông tin và bảo toàn phụ thuộc
Thuật toán 2.5(Kiểm tra phân mảnh W có bảo toàn phụ thuộc và có nối không mất thông tin):
= (R1, R2, Rk) là một phân mảnh của R;
Output: Khẳng định có nối không mất thông tin và bảo toàn phụ thuộc
Lần lượt kiểm tra từng tính chất của phân mảnh
Tính nối không mất kiểm tra bằng thuật toán Chase Tính bảo toàn phụ thuộc kiểm tra bằng thuật toán 2.3
Chú ý: Có nhiều cách đểphân mảnh một sơ đồ quan hệ thành các sơ đồ con có nối không mất thông tin và bảo toàn phụ thuộc
Ví dụ hai phép phân mảnh lược đồ R = {A, B, C, D} thành 1= (AB,
BC, CD) và 1 = (ABC, CD) của sơ đồ quan hệ trong thí dụ 2.5 đều có nối không mất thông tin và bảo toàn phụ thuộc
Với mỗi W có thể có nhiều phân mảnh khác nhau bảo toàn phụ thuộc và có nối không mất thông tin của W
2.3.5 T huật toán phân mảnh dọc có nối không mất và bảo toàn phụ thuộc
Thuật toán 2.6 (Phân mảnh W thành các Wi bảo toàn phụ thuộc và có nối không mất thông tin):
Output: W1,W2,…,Wk có nối không mất thông tin và bảo toàn phụ thuộc;
Chú ý: Nên tránh phân mảnh lược đồ đạt BCNF
Để đảm bảo tính bảo toàn phụ thuộc, chúng ta cần lấy tất cả các phụ thuộc hàm của tập F: {X → Y} và đưa vào các sơ đồ con Wi = Do đó, ta có Ri = XY.
Nếu có các thuộc tính không thuộc F, chúng ta cần lập sơ đồ con chỉ bao gồm các thuộc tính đó với tập phụ thuộc rỗng Để đảm bảo tính nối không bị mất, việc đưa vào phân mảnh một sơ đồ con là cần thiết.
với tập thuộc tính là khóa K, tập phụ thuộc là chiếu của F lên K
Người tađã chứng minh rằng phân mảnh như thế có nối không mất thông tin [8]
Xét W = Khóa của W là K ={A, H, M, N}
Khi đó ta có phân mảnh W thành các Wi con bảo toàn phụ thuộc:
Để đảm bảo tính nối không mất thông tin, chúng ta bổ sung W6 = vào W5 = Việc kiểm tra tính bảo toàn phụ thuộc hiển nhiên và tính nối không mất thông tin sẽ được thực hiện thông qua thuật toán Chase.
Bảng sau khi sửa cho hợp với các phụ thuộc hàm trong F
Bảng có một hàng (hàng chứa các thuộc tính khóa) toàn a nên phân mảnh có nối không mất thông tin.
Phân mảnh dọc thành các BCNF, bảo toàn phụ thuộc, nối không mất thông tin
Trong các phần trên chúng ta đã có các thuật toán và các phép kiểm tra tương ứng cho các phân mảnh W thành;
(1) Nối không mất thông tin;
(3) Bảo toàn phụ thuộc và nối không mất thông tin
Chúng ta sẽ xem xét các phân mảnh W và chuyển đổi chúng thành các sơ đồ con BCNF, đảm bảo các tính chất (1) và (2) hoặc (3) Như đã đề cập trước đó, mọi lược đồ quan hệ đều có thể được phân mảnh thành các lược đồ con theo chuẩn Boyce - Codd (BCNF) mà không làm mất thông tin Bất kỳ lược đồ nào cũng có khả năng phân mảnh thành dạng BCNF mà vẫn bảo toàn các phụ thuộc.
Một vấn đề quan trọng là liệu có thể phân mảnh W thành các dạng BCNF mà không làm mất thông tin và vẫn bảo toàn các phụ thuộc hay không.
2.4.1 Một số mệnh đề bổ trợ
Mỗi sơ đồ W = với R có hai thuộc tính đều có dạng BCNF Nếu R không đạt dạng BCNF, sẽ tồn tại hai thuộc tính A và B sao cho (R - AB) → A.
Nếu chúng ta có một tập phụ thuộc F trên R và chúng ta chiếu các phụ thuộc trên R1 R để được F1 rồi lại chiếu F1 trên R2 R1 để được F2 thì F2 2
Nghĩa là ta có thể giả sử rằng F là tập phụ thuộc của R1, dù rằng F có thể có những thuộc tính không có R1
Trong mọi sơ đồ quan hệ W =, luôn tồn tại sơ đồ quan hệ W = sao cho F tương đương với F’ và F’ chỉ chứa những phụ thuộc hàm mà phía bên phải chỉ có một thuộc tính.
Trong các thuật toán phân mảnh sau đây ta chỉ xét những sơ đồ quan hệ
W mà bên phải các phụ thuộc hàm F chỉ gồm một thuộc tính
2.4.2 Thuật toán phân mảnh lược đồ quan hệ thành các BCNF, có nối không mất thông tin
Chúng ta có thể áp dụng các bổ đề để phát triển thuật toán phân mảnh một sơ đồ quan hệ W = thành các sơ đồ con W1 = đạt chuẩn BCNF mà không làm mất thông tin Ý tưởng cốt lõi của thuật toán này là
Bắt đầu từ một lược đồ W có vi phạm BCNF, giả sử là X → A, chúng ta tiến hành phân mảnh R thành hai lược đồ XA và R-A Cả hai lược đồ này đều nhỏ hơn R, vì nếu XA bằng R thì X + = R, dẫn đến việc X → A không còn vi phạm BCNF Theo định lý 2.1, việc phân mảnh này tạo ra R1 = XA và R2 = R-A với sự nối không mất thông tin, do R1 ∩ R2 = X, R1 - R2 = A và X → A Chúng ta xác định các chiếu F1, F2 tương ứng của các phụ thuộc F trên XA và R2, với W1 = = và W2 = W1 là BCNF, và chúng ta tiếp tục kiểm tra W2 để tìm vi phạm cho bước phân mảnh tiếp theo Quá trình này lặp lại cho đến khi không còn khả năng phân mảnh, tức là khi sơ đồ quan hệ cuối cùng có ít hơn hai thuộc tính, tập thuộc tính rỗng hoặc là một sơ đồ BCNF Cuối cùng, thêm lược đồ BCNF vào phân mảnh để đảm bảo tất cả các sơ đồ đều có dạng BCNF và đạt được phân mảnh không mất thông tin.
Thuật toán 2 8: Phân mảnh W thành các BCNF có nối không mất thông tin
Output: Một phân mảnh R có nối không mất thông tin, sao cho mỗi sơ đồ quan hệ con Wi = có dạng BCNF
Thuật toán tập trung vào việc phân mảnh lược đồ quan hệ R thành hai lược đồ riêng biệt Mỗi lược đồ sẽ chứa một tập các thuộc tính XA, và sơ đồ quan hệ W= sẽ đạt chuẩn BCNF Lược đồ thứ hai được xác định là R-A, do đó, việc nối giữa R và A sẽ được thực hiện.
XA là phương pháp nối không làm mất thông tin Quá trình này thực hiện đệ quy để phân mảnh, với R-A giữ vai trò là R, cho đến khi đạt được kết quả như mong muốn.
Z := R (* Bất kỳ lúc nào Z cũng là lược đồ phân mảnh mà có thể W không có dạng BCNF*)
If X A vi phạm BCNF trong W= then
Rk = XA; Fk = X A, Wk = ; F:= F-Fk và loại khỏi F những phụ thuộc hàm có chứa A; Z:= Z- A;
{Phan rã W thành Wi và Wk trong đó Wk có dạng PCNF}
End; k:=k+1; until không thể phân mảnh Z tiếp; thêm Z vào phân mảnh
Ví dụ 2.8 (Phân mảnh W thành các BCNF, nối không mất thông tin):
Xét lược đồ quan hệ R(C, T, H, P, S, G) với C – course (lớp, khóa học);
Trong bài toán này, chúng ta có các yếu tố chính như T - giảng viên, H - giờ học, P - phòng học, S - sinh viên, và G - điểm số Các phụ thuộc hàm F được xác định dựa trên ngữ nghĩa của bài toán mà chúng ta đang xem xét.
C T Mỗi khóa học có một giảng viên
HP C Tại một giờ học, một phòng chỉ có một lớp
HT P Tại môt giờ học, một giảng viên chỉ có mặt trong một phòng học
CS G Mỗi sinh viên có một điểm số cho mỗi khóa học
HS P Tại một giờ học, một sinh viên chỉ có mặt tại một phòng học; Vậy chúng ta có W =; với R = {C, T, H, P, S, G} và tập phụ thuộc hàm
Trong sơ đồ quan hệ F = {C T, HP C, HT P, CS G, HS P}, thuộc tính C T vi phạm chuẩn BCNF Do đó, chúng ta tạo phân mảnh W1 = Sau khi loại bỏ thuộc tính T và các phụ thuộc hàm liên quan, các phân mảnh còn lại sẽ tiếp tục được phân tích.
W = Tiếp tục có
W3 được xác định là và W là Đặt W4 là Các sơ đồ W1, W2, W3, W4 đều tuân theo dạng BCNF và phân mảnh = (R1, R2, R3, R4) = (CT, HPS, HSG, HPS), đảm bảo rằng việc nối các R không làm mất thông tin.
Trong phép phân mảnh này phụ thuộc hàm (HS G) F mà thuộc F +
Cần lưu ý rằng trong thực hành có thể thực hiện nhanh hơn bằng cách sau mỗi lần tách được một Wi = ta loại bỏ khỏi W phụ thuộc X
A và những phụ thuộc có chứa A Và loại a ra khỏi tập thuộc tính Quay lại ví dụ trên ta thực hiện như sau:
W3 = ; W = và W4 =
Phép phân mảnh không bảo toàn phụ thuộc do mất đi các thuộc tính cần thiết Tuy nhiên, có thể tạo ra các sơ đồ quan hệ W được phân mảnh thành các sơ đồ con theo dạng BCNF mà vẫn đảm bảo nối không mất thông tin và bảo toàn phụ thuộc.
Ví dụ xét SDQH W và phép phân mảnh sau:
Tính bảo toàn phụ thuộc và BCNF của phân mảnh là điều hiển nhiên Dựa vào định lý 2.1 và bổ đề 2.1, chúng ta có thể kết luận rằng phân mảnh đảm bảo tính nối không mất thông tin.
Tuy nhiên chúng ta có thể kiểm tra lại phép phân mảnh có nối không mất bằng thuật toán Chase:
Bảng sau khi sửa cho thỏa A B, C D và E H
Bảng có một hàng toàn a có thể phân mảnh mà không mất thông tin Một vấn đề quan trọng cần xem xét là liệu mọi sơ đồ quan hệ W có thể được phân mảnh thành các sơ đồ con BCNF mà vẫn đảm bảo nối không mất thông tin hay không?
Nếu W vi phạm quy tắc BCNF, thuật toán sẽ phân mảnh W thành các phần tử BCNF mà không làm mất thông tin Ngược lại, nếu W đã thỏa mãn quy tắc BCNF, ta giữ nguyên W với W1 = W và W2 = W.
Từ các phân tích trên suy ra kết luận:
- Mọi sơ đồ quan hệ W đều có thể phân mảnh thành các BCNF không mất thông tin
- Việc phân mảnh W thành các sơ đồ quan hệ con BCNF, có nối không mất thông tin, là không duy nhất
2.4.3 Thuật toán phân mảnh thành các BCNF, có bảo toàn phụ thuộc
ỨNG DỤNG THIẾT KẾ CSDL VỀ THÔNG TIN CÁC
Bài toán quản lý thông tin các cung đường bộ trên địa bàn TP Lạng Sơn
3.1.1 Giới thiệu Thành phố Lạng Sơn
Thành phố Lạng Sơn, được thành lập vào năm 1925, là trung tâm kinh tế, chính trị và văn hóa - xã hội của tỉnh Lạng Sơn Nơi đây nổi bật với nhiều hang động và di tích lịch sử nổi tiếng, bao gồm quần thể hang động Nhất, Nhị, Tam Thanh và Nàng.
Tô Thị, Thành Nhà Mạc, Chùa Tiên và Giếng Tiên là những địa điểm nổi bật cùng với các lễ hội truyền thống giàu bản sắc dân tộc, thu hút khách du lịch từ xa xưa Sự kết hợp hoàn hảo giữa địa lý, thiên nhiên, lịch sử và con người đã giúp Thành phố Lạng Sơn phát triển mạnh mẽ, trở thành trung tâm chính trị, kinh tế và văn hóa của Lạng Sơn cũng như vùng Đông Bắc Tổ quốc.
TP Lạng Sơn là một đô thị thương mại cổ, hình thành theo phương thức "Thị" trước "đô" Nơi đây nổi tiếng với nhiều địa danh đã đi vào ca dao, dân ca Việt Nam, mang đậm âm hưởng văn hóa và tình cảm của người dân.
"Đồng Đăng có phố Kỳ Lừa
Có nàng Tô Thị, có chùa Tam Thanh
Ai lên xứ Lạng cùng anh
Bõ công bác mẹ sinh thành ra em Tay cầm bầu rượu nắm nem Mảng vui quên hết lời em dặn dò"
Ngày nay, TP Lạng Sơn là một thành phố trẻ và đang phát triển mạnh mẽ, đóng vai trò là cửa khẩu thương mại quan trọng, kết nối kinh tế - văn hóa giữa Việt Nam, Trung Quốc và các nước Đông Âu Thành phố này có vị trí chiến lược, gắn liền với tam giác kinh tế trọng điểm miền Bắc gồm Hà Nội, Hải Phòng và Quảng Ninh Năm 2000, Lạng Sơn được công nhận là đô thị loại III, đánh dấu bước tiến quan trọng trong quá trình phát triển đô thị của thành phố.
Năm 2002, Thị xã đã nhận được hơn 450 tỷ đồng để đầu tư vào xây dựng cơ sở hạ tầng và phát triển đô thị Sự đầu tư này đã cải thiện đáng kể hệ thống hạ tầng, góp phần thay đổi diện mạo của Thị xã Vào tháng 10/2002, Chính phủ đã ban hành Nghị định thành lập TP Lạng Sơn.
3.1.2 Hiện trạng quản lý thông tin các cung đường bộ trên địa bàn TP Lạng Sơn
Thông tin giao thông tại TP Lạng Sơn (LS) đang được thu thập, lưu trữ và xử lý ngày càng nhiều Việc tổ chức và khai thác thông tin giao thông một cách khoa học là cần thiết để giúp các nhà quản lý có cái nhìn chính xác về thực trạng giao thông, từ đó đưa ra quyết định đúng đắn và kịp thời.
LS được chia thành 8 đơn vị hành chính: 05 phường (Phường Chi Lăng, Vĩnh Trại, Tam Thanh, Hoàng Văn Thụ, Đông Kinh), 03 xã (xã Quảng Lạc, Mai Pha, Hoàng Đồng)
Hệ thống giao thông của LS đã được mở rộng với 21,7km đường mới và nâng cấp 26,15km mặt đường bê tông, nâng tổng chiều dài lên 125,5km, trong đó có 48,4km đường cao tốc Quốc lộ 1A đã được cải tạo thành đường cao tốc 3 làn xe, tạo điều kiện thuận lợi cho phát triển thương mại, du lịch và giao lưu hàng hóa giữa LS và các địa phương khác Những cải thiện này đã giúp nâng cao diện mạo đô thị và thu hút đầu tư, khai thác hiệu quả tiềm năng phát triển kinh tế thương mại - du lịch - dịch vụ của LS.
Toàn LS hiện có 13 tuyến đường chiều dài 95.489 km, trong đó có 2 tuyến đường đô thị (phường) chiều dài 9.100 km, 11 tuyến đường xã dài 86.389 km
Trong chương 3 của luận văn, học viên tập trung vào việc quản lý và khai thác thông tin về các cung đường bộ tại TP Lạng Sơn Nội dung chính là ứng dụng lý thuyết để thiết kế cơ sở dữ liệu (CSDL) cho thông tin đường bộ Thay vì sử dụng các phương pháp thiết kế CSDL truyền thống như kiểu “từ điển” hay “mô hình”, chúng ta sẽ áp dụng lý thuyết CSDL phân tán, sử dụng thuật toán phân mảnh một sơ đồ quan hệ thành BCNF, bảo toàn phụ thuộc và đảm bảo không mất thông tin Ngoài ra, có thể tiếp tục phát triển thành CSDL phân tán cho bài toán này.
Thuật toán sử dụng và xác định dữ liệu đầu vào
Thuật toán 2.10 được áp dụng để phân mảnh một sơ đồ quan hệ thành BCNF, đảm bảo bảo toàn phụ thuộc và thực hiện nối không mất thông tin, như đã trình bày trong chương 2 (trang 38).
3.2.2 Dữ liệu đầu vào Để xác định dữ liệu đầu vào,trước hết, chúng ta sẽ mô tả chi tiết các thông tin cần thiết về các cung đường
Thông tin về đường bao gồm tên đường, phường/xã, chiều dài, loại mặt đường, kiểu đường, tình trạng chiếu sáng, tổ chức giao thông, mức độ hư hỏng, giao cắt đường sắt, hệ thống tín hiệu, mật độ lưu thông, mã thông tin bảo trì, đơn vị bảo trì, loại bảo trì, nội dung bảo trì, giá trị bảo trì, thời gian bắt đầu và kết thúc đợt bảo trì.
Mặt đường bao gồm nhiều loại vật liệu như bê tông nhựa, bê tông xi măng (BTXM), đá dăm trộn nhựa, thấm nhập nhựa, và láng nhựa 2, 3 lớp Ngoài ra, còn có đá dăm tiêu chuẩn, cấp phối đá dăm, cùng với cấp phối thiên nhiên, tạo nên sự đa dạng và tính ứng dụng cao trong xây dựng hạ tầng giao thông.
KieuDuong:gồmĐường liên phường/huyện, Đường nội phường/huyện
Tình trạng Chieu Sang: xác định đường có hệ thống chiếu sáng hay không
Cách thức tổ chức giao thông đóng vai trò quan trọng trong việc xác định cấu trúc và lưu thông trên đường Các phương án tổ chức giao thông bao gồm đường một chiều, đường hai chiều có giải phân cách cứng và đường hai chiều không có giải phân cách Việc lựa chọn phương án phù hợp giúp cải thiện an toàn giao thông và tối ưu hóa lưu lượng phương tiện.
Mức độ hư hỏng: Xác định mức độ hư hỏng của đường:
Xếp loại 1 và 2 cho thấy mặt đường ít hoặc không có vết nứt, biến dạng, và tình trạng tốt, không cần sửa chữa ngay lập tức Trong khi đó, xếp loại 3 và 4 có nứt nhưng ít biến dạng, tình trạng mặt đường kém và cần tiến hành sửa chữa mà không cần nghiên cứu thêm.
Xếp loại 5, 6, 7: nứt và biến dạng trên diện rộng; tình trạng lớp mặt đường rất xấu và tồi tệ cần sửa chữa lớn hoặc tiến hành trải thảm
Giao cắt đường sắt (ĐS): xác định đường có giao cắt với đường sắt hay không
Hệ thống tín hiệu: xác định đường có hệ thống tín hiệu đèn giao thông hay không
Mật độ lưu thông: xác định mật độ xe lưu thông
Loại bảo trì: Xác định loại bảo trì (Sửa chữa thường xuyên, sửa chữa định kỳ, sửa chữa đột xuất)
Đơn vị bảo trì: Xác định đơn vị bảo trì như tên, địa chỉ, email, điện thoại,…
Thông tin bảo trì đường bộ bao gồm tên cung đường được bảo trì, loại hình bảo trì, nội dung các công việc trong đợt bảo trì, đơn vị thực hiện bảo trì, tổng giá trị của đợt bảo trì, thời gian bắt đầu và thời gian kết thúc bảo trì.
Tiếp theo, chúng ta sẽ xác định mối quan hệ giữa chúng
1-Mã đường Tên đường, Mã phường/xã, Mã Kiểu đường , Mã Tổ chức GT,
Mã Loại mặt đường, Mã Mức độ hư hỏng, Chiều dài, Tình trạng chiếu sáng, Giao cắt ĐS, Hệ thống tín hiệu, Mật độ lưu thông
2-Mã phường/xã Tên phường/xã
3-Mã Kiểu đường Kiểu đường
4-Mã Tổ chức GT Tổ chức GT
5- Mã Loại mặt đường Loại mặt đường
6-Mã Mức độ hư hỏng Mức độ hư hỏng
7- Mã đơn vị bảo trì Tên đơn vị bảo trì, Địa chỉ, Điện thoại, Email
8-Mã Loại bảo trì Loại bảo trì
Mã thông tin bảo trì bao gồm các yếu tố quan trọng như mã đơn vị bảo trì, mã đường, mã loại bảo trì, nội dung bảo trì, tổng giá trị, thời gian bắt đầu và thời gian kết thúc.
Cuối cùng, chúng ta xác định sơ đồ quan hệ W=, trong đó W là tên sơ đồ quan hệ tổng thể, R là tập hợp các thuộc tính, và F là tập hợp các phụ thuộc hàm đã được xác định.
Môi trường thử nghiệm
- Phần cứng: Pentium IV 2Gb MHz trở lên Tối thiểu 1GB RAM Ổ cứng 10GB
+ Hệ điều hành: Windows 7 hoặc Windows 2010
+ Phần mềm tiện ích NET Framework 4.5
+ Bộ font Unicode và bộ gõ tiếng việt Unicode
- Đường truyền mạng Internet (nếu dùng thiết kế cho CSDL phân tán)
Chương trình được viết bằng ngôn ngữ lập trình C#.
Nội dung và kết quả thử nghiệm
3.4.1 Nội dung thiết kế cơ sở dữ liệu các cung đường TP Lạng Sơn
Bước 1 : Xác định W= và khóa k của W
1-Xác định sơ đồ quan hệ tổng thể
Danh sách các thuộc tính trong sơ đồ tổng thể:
R bao gồm các thông tin quan trọng như tên đường, tên phường/xã, kiểu đường, tổ chức giao thông, loại mặt đường, mức độ hư hỏng, chiều dài, tình trạng chiếu sáng, loại giao cắt, hệ thống tín hiệu, mật độ lưu thông, mã thông tin bảo trì, tên đơn vị bảo trì, địa chỉ, điện thoại, email, loại bảo trì, nội dung bảo trì, tổng giá trị, thời gian bắt đầu và thời gian kết thúc.
2-Xác định Tập phụ thuộc hàm (F):
+Bổ sung các thuộc tính định danh cho W:
Bài viết này trình bày một danh sách các thông tin quan trọng liên quan đến quản lý đường phố, bao gồm mã và tên đường, mã và tên phường/xã, kiểu đường và tổ chức giao thông Ngoài ra, nó cũng đề cập đến loại mặt đường, mức độ hư hỏng, chiều dài, tình trạng chiếu sáng, giao cắt đường sắt, hệ thống tín hiệu và mật độ lưu thông Thông tin về đơn vị bảo trì, bao gồm mã, tên, địa chỉ, điện thoại và email, cùng với mã và loại bảo trì, nội dung bảo trì, tổng giá trị, thời gian bắt đầu và kết thúc cũng được nêu rõ.
+Xác định tập phụ thuộc hàm F:
1-Mã đường Tên đường, Mã phường/xã, Mã Kiểu đường, Mã Tổ chức GT,
Mã Loại mặt đường, Mã Mức độ hư hỏng, Chiều dài, Tình trạng chiếu sáng, Giao cắt ĐS, Hệ thống tín hiệu, Mật độ lưu thông
2-Mã phường/xã Tên phường/xã
3-Mã Kiểu đường Kiểu đường
4-Mã Tổ chức GT Tổ chức GT
5- Mã Loại mặt đường Loại mặt đường
6-Mã Mức độ hư hỏng Mức độ hư hỏng
7- Mã đơn vị bảo trì Tên đơn vị bảo trì, Địa chỉ, Điện thoại, Email
8-Mã Loại bảo trì Loại bảo trì
Mã thông tin bảo trì bao gồm mã đơn vị bảo trì, mã đường, mã loại bảo trì, nội dung bảo trì, tổng giá trị, thời gian bắt đầu và thời gian kết thúc.
-Mã hóa tập thuộc tính R:
R= {01-Mã đường,a02-Tên đường, a03-Mã phường/xã ,a04-Tên phường/xã, a05-Mã Kiểu đường, a06-Kiểu đường, a07-Mã Tổ chức GT, a08-
Tổ chức GT cung cấp thông tin chi tiết về mã loại mặt đường, loại mặt đường, mã và mức độ hư hỏng, chiều dài, hệ thống chiếu sáng, giao cắt đường sắt, hệ thống tín hiệu, mật độ lưu thông, cũng như mã và tên đơn vị bảo trì, địa chỉ, điện thoại và email của đơn vị bảo trì.
Mã thông tin bảo trì, a24-Mã Loại bảo trì, a25-Loại bảo trì, a26-Nội dung bảo trì, a27-Tổng giá trị, a28-Thời gian bắt đầu, a29-Thời gian kết thúc}
Tương ứng chúng ta có tập phụ thuộc hàm F: a01 a02, a03, a05, a07, a09, a11, a13, a14, a15, a16, a17 a03 a04 a05 a06 a07 a08 a09 a10 a11 a12 a18 a19, a20, a21, a22 a24 a25 a23 a18, a01, a24, a26, a27, a28, a29
Như vậy, chúng ta đã xác định được W=
-Xác định khóa của W: Để xác định khóa của W, chúng ta áp dụng thuật toán Tìm khoá tối tiểu cho một sơ đồ quan hệ như sau
Input: sơ đồ quan hệ s = trong đó: F là tập các phụ thuộc hàm
R ={a1, , an}là tập các thuộc tính
Output: K là tối tiểu của s
Tính liên tiếp các tập thuộc tính K0, K1, , Kn như sau:
K = Kn là khoá tối tiểu
Ta có thể dùng công thức tương đương:
Dùng thuật toán trên để tính khóa cho một lược đồ quan hệ ta có: k(khóa)={ mã thông tin bảo trì }={a23}
Bước 2 : Thiết kế CSDL mức logic dựa vào lý thuyết CSDL phân tán i 1 i i 1 i
K i-1 { a i } nếu ngược lại nếu {K i-1 a i } + = R nếu ngược lại
Dựa vào định lý và thuật toán phân mảnh, một sơ đồ quan hệ có thể được chuyển đổi thành dạng BCNF, đồng thời bảo toàn các phụ thuộc và đảm bảo việc nối không mất thông tin, như đã được trình bày trong chương.
2, chúng ta lần lượt thực hiện các công việc sau:
-Xác định các thuộc tính không thuộc tập F để nhóm các thuộc tính đó thành một sơ đồ con với tập phụ thuộc rỗng
-Xác định các lược đồ con dạng Wi = với mọi phụ thuộc thứ i của F
-Xác định lược đồ con dạng Wk =, k là khóa của W, k (F) là chiếu của F lên k
Kết quả cuối cùng, chúng ta xác định được:
- Hệ lược đồ quan hệ đạt chuẩn 3NF:
R1-ĐƯỜNG (Mã đường, Tên đường, Mã phường/xã, Mã Kiểu đường,
Mã tổ chức GT, mã loại mặt đường, mã mức độ hư hỏng, chiều dài, tình trạng chiếu sáng, giao cắt đường sắt, hệ thống tín hiệu và mật độ lưu thông là những yếu tố quan trọng trong việc đánh giá và quản lý hạ tầng giao thông Những thông tin này giúp xác định tình trạng và hiệu quả của các tuyến đường, từ đó cải thiện an toàn và lưu thông cho người dân.
R2-PHƯỜNG/XÃ (Mã phường/xã, Tên phường/xã ) R3-KIỂUĐƯỜNG (Mã Kiểu đường, Kiểu đường)
R4-TỔCHỨCGIAOTHÔNG (Mã Tổ chức GT, Tổ chức GT)
R5-LOẠI MẶT ĐƯỜNG (Mã Loại mặt đường, Loại mặt đường)
R6-MỨCĐỘHƯHỎNG (Mã Mức độ hư hỏng, Mức độ hư hỏng)
R7-ĐƠNVỊBẢOTRÌ (Mã đơn vị bảo trì,Tên đơn vị bảo trì, Địa chỉ, Điện thoại, Email)
R8-LOẠIBẢOTRÌ (Mã Loại bảo trì, Loại bảo trì)
R9-BẢOTRÌ bao gồm các thông tin quan trọng như mã thông tin bảo trì, mã đơn vị bảo trì, mã đường, mã loại bảo trì, nội dung bảo trì, tổng giá trị, thời gian bắt đầu và thời gian kết thúc.
- Mô hình Thực thể - Mối quan hệ (Mô hình E_R)
Hình 3.1.Mô hình Thực thể- Mối quan hệ (Mô hình E_R): ĐƯỜNG
Mã Mức độ hư hỏng
Chiều dài Tình trạng chiếu sáng Giao cắt ĐS
Hệ thống tín hiệu Mật độ lưu thông
Tên tổ chức GT ĐƠN VỊ BAOTRI
Mã đơn vị Tên đơn vị Địa chỉ Điện thoại E-mail
Mã mức độ hư hỏng Tên mức độ hư hỏng
Mã loại mặt đường Tên loại mặtđường
Mã Loại bảotrì Loại bảo trì
Mã thông tin bảo trìMã đơn vị
Nội dung bảo trì Tổng giá trị Thời gian bắt đầu Thời gian kết thúc
3.4.2 Phương án đề xuất phân mảnh dữ liệu(nếu có yêu cầu xây dựng CSDL phân tán)
Dựa vào tần suất sử dụng, khoảng cách địa lý và hoạt động của hệ thống, chúng tôi đề xuất phương án phân mảnh dữ liệu bằng cách sử dụng phân mảnh ngang nguyên thủy và phân mảnh ngang dẫn xuất Phân chia quan hệ tổng thể thành 8 mảnh tại 5 phường và 3 xã dựa trên khoảng cách địa lý Quan hệ tổng DUONG được chọn làm tiêu chí phân mảnh, dẫn đến việc tạo ra các mảnh tại các vị trí phường và xã Các mảnh quan hệ DUONG được phân thành các mảnh ngang cụ thể như DUONG_LS (Lạng Sơn), DUONG_CL (Chi Lăng), DUONG_VT (Vĩnh Trại), DUONG_TT (Tam Thanh), DUONG_HVT (Hoàng Văn Thụ), DUONG_ĐK (Đông Kinh), DUONG_QL (Quảng Lạc), DUONG_MP (Mai Pha) và DUONG_HĐ (Hoàng Đồng).
DUONG_LS: cung đường thuộc thành phố Lạng Sơn
DUONG_LS = б Tenhuyen = “Lạng Sơn” (DUONG > < HUYEN)
DUONG_ CL: cung đường thuộc phường ChiLăng
DUONG_CL =б Tenhuyen = “ ChiLăng ” (DUONG > < HUYEN)
DUONG_VT: cung đường thuộc phường Vĩnh Trại
DUONG_VT =б Tenhuyen = “ Vĩnh Trại ” (DUONG > < HUYEN)
DUONG_TT: cung đường thuộc phường Tam Thanh
DUONG_TT =б Tenhuyen = “ Tam Thanh ” (DUONG > < HUYEN)
DUONG_HVT: cung đường thuộc phường Hoàng Văn Thụ
DUONG_ HVT =б Tenhuyen = “ Hoàng Văn Thụ ” (DUONG > < HUYEN)
DUONG_ĐK: cung đường thuộc huyện phường Đông Kinh
DUONG_ĐK =б Tenhuyen = “ Đông Kinh ” (DUONG > < HUYEN)
DUONG_QL: cung đường thuộc xã Quảng Lạc
DUONG_QL =б Tenhuyen =“ Quảng Lạc ” (DUONG > < HUYEN)
DUONG_MP: cung đường thuộc xã Mai Pha
DUONG_MP =б Tenhuyen =“ Mai Pha ” (DUONG > < HUYEN)
DUONG_HĐ: cung đường thuộc xã Hoàng Đồng
DUONG_HĐ = б Tenhuyen =“ Hoàng Đồng ” (DUONG > < HUYEN)
Phân mảnh quan hệ THONGTINBAOTRI thành các mảnh ngang như sau:
Thông tin bảo trì của các cung đường thuộc thành phố Lạng Sơn: THONGTINBAOTRI_LS = THONGTINBAOTRI > < DUONG_LS
Thông tin bảo trì của các cung đường thuộc Phường Chi Lăng: THONGTINBAOTRI_CL = THONGTINBAOTRI > < DUONG_CL
Thông tin bảo trì của các cung đường thuộc phường Vĩnh Trại: THONGTINBAOTRI_VT = THONGTINBAOTRI > < DUONG_VT
Thông tin bảo trì của các cung đường thuộc phường Tam Thanh: THONGTINBAOTRI_TT= THONGTINBAOTRI > < DUONG_TT
Thông tin bảo trì của các cung đường thuộc phường Hoàng văn Thụ: THONGTINBAOTRI_HVT = THONGTINBAOTRI > < DUONG_HVT
Thông tin bảo trì của các cung đường thuộc phường Đông kinh: THONGTINBAOTRI_ĐK = THONGTINBAOTRI > < DUONG_ĐK
Thông tin bảo trì của các cung đường thuộc xã Quảng Lạc: THONGTINBAOTRI_QL = THONGTINBAOTRI > < DUONG_QL
Thông tin bảo trì của các cung đường thuộc xã Mai Pha: THONGTINBAOTRI_MP = THONGTINBAOTRI > < DUONG_MP
Thông tin bảo trì của các cung đường thuộc xã Hoàng Đồng: THONGTINBAOTRI_HĐ = THONGTINBAOTRI > < DUONG_HĐ
Hình 3.2 Sơ đồ định vị của các mảnh tại các vị trí
Để hệ thống hoạt động hiệu quả trong môi trường phân tán, cần thiết kế sơ đồ ánh xạ địa phương và tạo bản sao các bảng dữ liệu tại những vị trí chiến lược.
R: Gồm các quan hệ tổng thể là DUONG, THONGTINBAOTRI Còn quan hệ tổng thể HUYEN, LOAIMATDUONG, KIEUDUONG, TOCHUCGIAOTHONG, MUCDOHUHONG, LOAIBAOTRI, DONVITHICONG dùng chung tại các vị trí nên ta chỉ thêm mới và cập nhật đồng bộ giữa các vị trí
CSDL tại các vị trí CSDL dùng chung
Hình 3.3 Các mảnh và hình ảnh vật lý của một quan hệ tổng thể
Quan hệ tổng thể Các đoạn Hình ảnh vật lý
Để triển khai hệ thống phân tán cho quản lý thông tin các cung đường, cần đầu tư hạ tầng mạng theo mô hình phân tán ngang hàng Mỗi huyện (phường/xã) sẽ đặt một Server trong hệ thống, có quyền cập nhật thông tin về các cung đường tại địa phương và báo cáo thống kê dữ liệu từ các huyện khác.
Mô hình hệ thống mạng được mô phỏng như sau:
Hình 3.4 Mô hình mạng của hệ thống quản lí các cung đường
3.4.3 Một số giao diện chính
Hình 3.5 Giao diện trang chủ
3.4.3.2 Giao diện form thiết kế CSDL
Hình 3.6.Giao diện nhập liệu
- Giao diện form tìm khóa tối tiểu:
Hình 3.7.Giao diện tìm khóa -Giao diện form thiết kế CSDL:
Hình 3.8 Giao diện phân mảnh thành hệ lược đồ đạt 3NF
3.4.4 H ướng dẫn sử dụng chương trình thử nghiệm
Chương trình phân rã sơ đồ quan hệ thành các sơ đồ con đạt chuẩn BCNF, bảo toàn phụ thuộc và đảm bảo không mất thông tin Được phát triển bằng ngôn ngữ lập trình C# và sử dụng bộ NET Framework 4.5, chương trình áp dụng các thuật toán xác định khóa và phân rã hiệu quả.
Dữ liệu đầu vào là file txt lưu sơ đồ quan hệ theo cấu trúc sau:
Dòng đầu tiên của tài liệu chứa danh sách các thuộc tính, với tên thuộc tính được viết liền và phân tách bằng dấu cách Từ dòng thứ hai trở đi, mỗi dòng sẽ trình bày một phụ thuộc hàm, với vế trái và vế phải được ngăn cách bởi dấu phẩy (,); các thuộc tính trong mỗi vế cũng được phân tách bằng dấu cách Chẳng hạn, phụ thuộc hàm AB=>CDE sẽ được thể hiện trên một dòng với thứ tự A B, C D E.
Việc thực hiện chương trình được tóm tắt theo trình tự sau:
Sau khi màn hình chính hiển thị, người dùng có thể truy cập vào hai menu chính là “Chương trình” và “Trợ giúp” để sử dụng các chức năng của phần mềm Để thực hiện xử lý thuật toán, người dùng chọn menu “Chương trình => Phân rã W”, sau đó giao diện cửa sổ làm việc sẽ được mở ra.
-Bước1: Nhấn nút “Tải lược đồ quan hệ” để chọn file chứa dữ liệu về lược đồ quan hệ Giao diện chọn file sẽ mở ra như hình sau:
Chọn tệp chứa dữ liệu sơ đồ quan hệ theo cấu trúc đã được mô tả trong phần đầu của tài liệu Lưu ý rằng nếu dữ liệu không đúng cấu trúc, chương trình sẽ không hoạt động hiệu quả.
Nếu file đúng định dạng, chương trình sẽ đọc file và hiển thị danh sách thuộc tính, danh sách phụ thuộc hàm ở vùng bên trái của giao diện chính
-Bước 2: Nhấn nút “Tìm khóa”, chương trình sẽ thực hiện lần lượt thuật toán tìm khóa tối thiểu để xác định khóa của CSDL
Nếu thực hiện tìm khóa khi chưa tải dữ liệu, chương trình sẽ hiển thị cảnh báo
Đánh giá chương trình thử nghiệm
1-Đánh giá Kết quả đạt được:
Kết quả của luận văn đạt được là xây dựng một hệ lược đồ quan hệ chuẩn hóa đến BCNF, đồng thời đạt 3NF và mô hình Thực thể - Mối quan hệ (Mô hình E_R) Phương pháp này không theo cách truyền thống mà thể hiện khả năng ứng dụng lý thuyết về CSDL phân tán Ưu điểm của ứng dụng này sẽ được phân tích và đánh giá chi tiết trong các phần sau.
2-Đánh giá quy trình thực hiện so với quy trình thiết kế CSDL tập trung:
Trong mô hình cơ sở dữ liệu tập trung, việc tuân thủ đầy đủ các bước theo trình tự công nghệ là rất quan trọng để đảm bảo thiết kế cơ sở dữ liệu đạt chất lượng tốt.
Hình 3.9.Các bước thiết kế CSDL mức logic trong mô hình CSDL tập trung
Bảng 3.1.Bảng so sánh nội dung các bước trong quy trình thiết kế CSDL mức logic
Quy trình thiết kế CSDL mức logic
A-trong mô hình CSDL phân tán B- trong mô hình CSDL tập trung
Thu thập các dữ liệu là những hồ sơ, đầu vào chứa tất cả dữ liệu cần thiết để xây dựng CSDL
Thu thập các dữ liệu là những hồ sơ, đầu vào chứa tất cả dữ liệu cần thiết để xây dựng CSDL
Mỗi hồ sơ gốc được coi là một thực thể, trong đó liệt kê tất cả các thông tin đặc trưng được xem như thuộc tính của thực thể đó.
Bước 4: Xây dựng Mô hình khái niệm dữ liệu Bước 2: Xác định các thực thể, danh sách thuộc tính
Bước 5: Chuyển Mô hình khái niệm dữ liệu sang Mô hình quan hệ
(Hệ lược đồ quan hệ) Bước 6: Chuẩn hoá các quan hệ đến 3NF và hợp nhấtchúng khi cần
Bước 7: Xây dựng Mô hình dữ liệu mức logic - Sơ đồ E_R
Bước 1: Chính xác hoá dữ liệu và thiết lập danh sách thuộc tính cần quản lý
Bước 3: Xác định các mối quan hệ, danh sách thuộc tính (nếu có)
Chính xác hoá thông tin là quá trình đảm bảo rằng các thuộc tính của các thực thể có cùng tên gọi trong toàn bộ từ điển phải mang cùng một nghĩa Nếu các thông tin này có nghĩa khác nhau, thì tên gọi của chúng cần phải được phân biệt rõ ràng.
Mã hoá các thông tin thu được để có thể tự động hóa
Chọn lọc và mã hoá các thông tin thu được theo nguyên tắc đã định
Xác định danh sách thuộc tính và mối quan hệ phụ thuộc hàm giữa chúng (các thành phần của sơ đồ quan hệ )
Xác định các thuộc tính lặp trong các thực thể nhận được (thuộc tính trong bảng)
Xác định khóa của sơ đồ quan hệ Xác định thuộc tính định danh của các thực thể (hồ sơ gốc) (đánh dấu bằng gạch dưới thuộc tính)
Phân mảnh dọc sơ đồ quan hệ theo quy tắc xác định
Tiến hành chuẩn hoá các thực thể đã mã hoá để thu được các quan hệ đạt chuẩn 3NF
Tiến hành tích hợp các quan hệ đã được chuẩn hóa, xác định các khoá chính, khoá ngoại của chúng
Kết quả thu về 1 hệ lược đồ quan hệ đã được chuẩn hoá đến BCNF (đương nhiên là đạt 3NF)
Kết quả đạt được là một hệ lược đồ quan hệ được chuẩn hóa đến dạng 3NF, đảm bảo rằng các lược đồ quan hệ này tạo thành một hệ Sperner Một hệ được gọi là Sperner nếu với mọi A, B thuộc hệ đó, không tồn tại A là tập con của B.
Vẽ sơ đồ E_R Vẽ sơ đồ E_R
Kịch bản 1 ( dành cho CSDL tập trung):
Thiết kế CSDL vật lý tập trung và cài đặt trong máy
Kịch bản 2 (dành cho CSDL phân tán):
Thiết kế CSDL vật lý tập trung và cài đặt trong máy
-Đề xuất phương án phân mảnh dữ liệu
- Thiết kế sơ đồ ánh xạ địa phương
-Thiết kế hệ thống mạng cho hệ thống
Nhận xét: phương án A có nhiều ưu điểm hơn so với phương án B:
- Giao diện đơn giản, gọn nhẹ hơn
- Nhất cử lưỡng tiện (cho cả thiết kế CSDL tập trung lẫn CSDL phân tán)
Chương trình đã đáp ứng cơ bản các yêu cầu, nhưng các chức năng còn đơn giản và giao diện chưa hấp dẫn Hơn nữa, dữ liệu đầu vào cần tuân theo định dạng cụ thể.
Do khả năng hạn hẹp và thời gian ngắn nên CSDL ở dạng phân tán mới được thiết kế nhưng chưa được triển khai lập trình
Trong thời gian tới, chương trình cần được cải tiến để đáp ứng các tiêu chuẩn thiết kế cao hơn, đồng thời nâng cao tính tiện lợi cho việc huấn luyện và sử dụng.
Luận văn đã tập trung nghiên cứu các đặc trưng của phân mảnh dọc trong cơ sở dữ liệu phân tán, từ đó đạt được những kết quả quan trọng.
Cơ sở dữ liệu phân tán (CSDL phân tán) mang lại nhiều lợi ích nổi bật như khả năng mở rộng, tính linh hoạt và khả năng phục hồi cao Tuy nhiên, nó cũng gặp phải một số hạn chế như độ phức tạp trong quản lý và khả năng đồng bộ hóa dữ liệu Bài viết này sẽ tổng hợp một cách đầy đủ và rõ ràng những vấn đề phân mảnh trong CSDL phân tán, giúp người đọc hiểu rõ hơn về các khía cạnh quan trọng của hệ thống này.
Luận văn tiến hành nghiên cứu sâu về các đặc tính của phân mảnh dọc, bao gồm tính có nối không mất thông tin, tính bảo toàn phụ thuộc và tính bảo toàn các chuẩn Mỗi đặc tính được trình bày rõ ràng với định nghĩa cụ thể, thuật toán kiểm tra và thuật toán thực hiện, nhằm cung cấp cái nhìn toàn diện và chi tiết về vấn đề này.
Luận văn đã thành công trong việc thiết kế cơ sở dữ liệu (CSDL) về thông tin các cung đường bộ tại Lạng Sơn, dựa trên khảo sát kỹ lưỡng và đầy đủ các thông tin hiện trạng Thuật toán áp dụng được trình bày rõ ràng, cùng với việc xác định dữ liệu đầu vào và môi trường thử nghiệm Các kết quả thử nghiệm được trình bày theo quy trình thiết kế, xác định sơ đồ quan hệ tổng thể và các phương án phân mảnh Giao diện của chương trình bao gồm trang chủ, form thiết kế CSDL và hướng dẫn sử dụng, đáp ứng yêu cầu cho cả CSDL tập trung và phân tán, với kết quả đánh giá đạt yêu cầu.
Mặc dù chương trình hiện tại chưa hoàn toàn đáp ứng đầy đủ các yêu cầu phức tạp trong thực tế, nhưng nó đã đáp ứng được các yêu cầu cơ bản cho bài toán đã đặt ra Điều này thể hiện nỗ lực lớn của tác giả và tạo nền tảng vững chắc cho việc phát triển hệ thống quản lý các cung đường bộ tại tỉnh Lạng Sơn trong tương lai.