Luận văn thạc sĩ về tối ưu hóa cơ sở dữ liệu phân tán trong công nghệ thông tin

Nghiên cứu chuyên sâu Tối ưu hóa cơ sở dữ liệu phân tán trong luận văn thạc sĩ công nghệ thông tin, phương pháp luận hiện đại, kết quả ứng dụng thực

• Người hướng dẫn: PGS. Hồ Thuần
• Trường học: Đại học Quốc gia Hà Nội
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Tối ưu hóa cơ sở dữ liệu phân tán
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2006
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI NÓI ĐẦU
• 1. CHƯƠNG 1: KHÁI QUÁT VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN
• 1.1. Cơ sở dữ liệu quan hệ
• 1.2. Ngôn ngữ dữ liệu quan hệ
• 1.3. Hệ cơ sở dữ liệu phân tán
• 1.3.1. Các khái niệm về CSDL PT
• 1.3.2. Các mục tiêu của hệ quản trị CSDL PT
• 1.3.3. Kiến trúc hệ quản trị CSDL PT
• 1.3.4. Phân mảnh, nhân bản và cấp phát dữ liệu
• 2. CHƯƠNG 2: MỘT SỐ NGUYÊN LÝ CHUNG CỦA TỐI ƯU HÓA TRUY VẤN
• 2.1. Mục tiêu của bài toán xử lý truy vấn
• 2.2. Độ phức tạp của các phép toán đại số quan hệ
• 2.3. Mô tả bộ xử lý truy vấn
• 2.4. Phân rã truy vấn và định vị dữ liệu
• 2.4.1. Phân rã truy vấn
• 2.4.2. Định vị dữ liệu
• 2.5. Tối ưu hóa truy vấn phân tán
• 2.5.1. Tối ưu hóa truy vấn
• 2.5.2. Tối ưu hóa truy vấn trong môi trường tập trung
• 2.5.3. Các thuật toán tối ưu hóa truy vấn trong môi trường phân tán
• 3. CHƯƠNG 3: MỘT SỐ ĐỀ XUẤT KHÁC VỀ XỬ LÝ PHÉP NỐI TRONG CÁC HỆ CSDL
• 3.1. Ứng dụng lý thuyết đồ thị trong tối ưu hóa truy xuất CSDL để thực hiện phép nối
• 3.1.1. Sử dụng chỉ mục để thực hiện phép nối
• 3.1.2. Mô hình đồ thị kết nối trang
• 3.1.3. Xác định cận trên của kích thước bộ nhớ đệm
• 3.1.4. Các Heuristic để làm giảm lượng bộ nhớ đệm cần thiết
• 3.1.5. Lược đồ bộ nhớ đệm dựa trên cơ sở lưu trữ toàn bộ trang
• 3.1.6. Xác định kích thước bộ nhớ đệm để thực hiện một truy xuất cho mỗi trang
• 3.2. Một số phương án tiếp cận xử lý nối phân tán khác
• 3.2.1. Sử dụng thông tin phụ thuộc vị trí (placement dependency) để thực hiện nối
• 3.2.2. Thuật toán phân mảnh và nhân bản
• 3.2.3. Thuật toán qui hoạch băm
• 3.2.4. Xử lý truy vấn chuỗi
• 3.2.5. Tăng tốc xử lý truy vấn nhờ AHYPERF
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tối ưu hóa cơ sở dữ liệu phân tán

Tối ưu hóa cơ sở dữ liệu phân tán là một lĩnh vực quan trọng trong công nghệ thông tin, đặc biệt trong bối cảnh các hệ thống ngày càng trở nên phức tạp. Cơ sở dữ liệu phân tán cho phép lưu trữ và quản lý dữ liệu trên nhiều nút khác nhau, giúp tăng cường khả năng truy cập và xử lý dữ liệu. Tuy nhiên, việc tối ưu hóa truy vấn trong môi trường này là một thách thức lớn. Các yếu tố như quản lý cơ sở dữ liệu, hệ thống phân tán, và tối ưu hóa hiệu suất cần được xem xét kỹ lưỡng. Mục tiêu chính là giảm thiểu chi phí truy vấn và tăng tốc độ xử lý dữ liệu. Theo nghiên cứu, việc áp dụng các thuật toán tối ưu hóa có thể cải thiện đáng kể hiệu suất của hệ thống.

1.1. Các nguyên lý tối ưu hóa

Các nguyên lý tối ưu hóa trong cơ sở dữ liệu phân tán bao gồm việc phân tích và tối ưu hóa các truy vấn. Việc sử dụng thuật toán tối ưu hóa giúp xác định cách thức thực hiện truy vấn một cách hiệu quả nhất. Các yếu tố như phân mảnh, nhân bản, và cấp phát dữ liệu cũng đóng vai trò quan trọng trong việc tối ưu hóa. Nghiên cứu cho thấy rằng việc áp dụng các phương pháp tối ưu hóa có thể giảm thiểu đáng kể thời gian truy vấn và chi phí xử lý. Điều này không chỉ giúp cải thiện hiệu suất mà còn nâng cao trải nghiệm người dùng trong việc truy cập dữ liệu.

1.2. Ứng dụng công nghệ thông tin

Công nghệ thông tin đóng vai trò quan trọng trong việc tối ưu hóa cơ sở dữ liệu phân tán. Việc áp dụng các công nghệ mới như hệ thống quản lý cơ sở dữ liệu và thuật toán tối ưu hóa giúp cải thiện khả năng xử lý và quản lý dữ liệu. Các ứng dụng thực tiễn cho thấy rằng việc tối ưu hóa không chỉ giúp tiết kiệm chi phí mà còn nâng cao hiệu suất làm việc của hệ thống. Các nghiên cứu đã chỉ ra rằng việc sử dụng các công nghệ tiên tiến có thể tạo ra những bước đột phá trong việc tối ưu hóa truy vấn và quản lý dữ liệu.

II. Phân tích và đánh giá giá trị thực tiễn

Việc tối ưu hóa cơ sở dữ liệu phân tán không chỉ mang lại lợi ích về mặt kỹ thuật mà còn có giá trị thực tiễn cao. Các hệ thống phân tán cho phép tổ chức quản lý dữ liệu một cách hiệu quả hơn, từ đó nâng cao khả năng ra quyết định. Quản lý cơ sở dữ liệu hiệu quả giúp giảm thiểu rủi ro và tăng cường tính bảo mật. Nghiên cứu cho thấy rằng việc tối ưu hóa truy vấn có thể giúp tổ chức tiết kiệm chi phí vận hành và nâng cao hiệu suất làm việc. Điều này đặc biệt quan trọng trong bối cảnh cạnh tranh ngày càng gia tăng trong lĩnh vực công nghệ thông tin.

2.1. Lợi ích kinh tế

Tối ưu hóa cơ sở dữ liệu phân tán mang lại nhiều lợi ích kinh tế cho tổ chức. Việc giảm thiểu chi phí truy vấn và tăng tốc độ xử lý dữ liệu giúp tổ chức tiết kiệm nguồn lực. Các nghiên cứu đã chỉ ra rằng việc áp dụng các phương pháp tối ưu hóa có thể giảm thiểu chi phí vận hành lên đến 30%. Điều này không chỉ giúp tổ chức tăng cường khả năng cạnh tranh mà còn tạo ra giá trị bền vững trong dài hạn.

2.2. Tác động đến hiệu suất

Tối ưu hóa cơ sở dữ liệu phân tán có tác động tích cực đến hiệu suất của hệ thống. Việc áp dụng các thuật toán tối ưu hóa giúp cải thiện tốc độ truy vấn và giảm thiểu thời gian chờ đợi của người dùng. Các nghiên cứu cho thấy rằng việc tối ưu hóa có thể cải thiện hiệu suất hệ thống lên đến 50%. Điều này không chỉ nâng cao trải nghiệm người dùng mà còn giúp tổ chức đạt được mục tiêu kinh doanh một cách hiệu quả hơn.

Nội dung chính

Tổng quan nghiên cứu

Cơ sở dữ liệu phân tán (CSDL PT) là một lĩnh vực quan trọng trong công nghệ thông tin, đặc biệt trong bối cảnh phát triển mạnh mẽ của mạng Internet và thương mại điện tử. Theo ước tính, các hệ CSDL phân tán ngày càng được ứng dụng rộng rãi nhằm đáp ứng nhu cầu quản lý dữ liệu phân tán trên nhiều nút mạng khác nhau. Vấn đề tối ưu hóa câu truy vấn trong CSDL phân tán trở thành thách thức lớn do tính phức tạp của việc truy xuất dữ liệu phân tán, chi phí truyền thông và xử lý cục bộ. Mục tiêu nghiên cứu của luận văn là phân tích, đánh giá các nguyên lý và thuật toán tối ưu hóa truy vấn trong môi trường CSDL phân tán, từ đó đề xuất các giải pháp nâng cao hiệu quả xử lý truy vấn. Phạm vi nghiên cứu tập trung vào các hệ CSDL phân tán quan hệ, với các kỹ thuật phân mảnh, nhân bản và cấp phát dữ liệu, áp dụng trong môi trường mạng máy tính tại Việt Nam giai đoạn 2000-2006. Ý nghĩa của nghiên cứu được thể hiện qua việc giảm thiểu chi phí truy vấn, tăng hiệu năng xử lý và nâng cao tính sẵn sàng của hệ thống, góp phần thúc đẩy ứng dụng CSDL phân tán trong các tổ chức và doanh nghiệp.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên mô hình dữ liệu quan hệ do E. Codd đề xuất, trong đó dữ liệu được tổ chức dưới dạng các quan hệ (bảng) với các thuộc tính và bộ (tuple). Các khái niệm chính bao gồm: lược đồ quan hệ, khóa, chuẩn hóa dữ liệu (1NF, 2NF, 3NF, BCNF), và các phép toán đại số quan hệ như chọn, chiếu, hợp, trừ, tích Descartes, nối θ, nối tự nhiên, nối nửa và phép chia. Hệ CSDL phân tán được định nghĩa là tập hợp các CSDL liên đới logic, phân bố trên nhiều nút mạng, với các đặc trưng như trong suốt phân tán, trong suốt phân mảnh, trong suốt nhân bản và tính tự trị của các trạm. Các kiến trúc hệ quản trị CSDL PT bao gồm các thành phần như bộ xử lý tiếp nhận người dùng, bộ tối ưu truy vấn toàn cục, bộ quản lý giao dịch phân tán, bộ tối ưu truy vấn cục bộ và bộ khôi phục cục bộ. Các kỹ thuật phân mảnh (ngang, dọc, hỗn hợp), nhân bản và cấp phát dữ liệu được sử dụng để tối ưu hóa truy vấn và nâng cao hiệu năng hệ thống. Ngoài ra, các thuật toán tối ưu hóa truy vấn như heuristic, thuật toán vét cạn, và các chiến lược ngẫu nhiên hóa cũng được áp dụng để giải quyết bài toán NP-hard trong tối ưu hóa truy vấn.

Phương pháp nghiên cứu

Nguồn dữ liệu nghiên cứu bao gồm các tài liệu học thuật, báo cáo ngành và các hệ thống CSDL phân tán thực tế. Phương pháp nghiên cứu chủ yếu là phân tích lý thuyết, mô hình hóa và đánh giá thuật toán tối ưu hóa truy vấn. Cỡ mẫu nghiên cứu là các câu truy vấn mẫu và các cấu hình phân mảnh, nhân bản trong môi trường phân tán giả định với khoảng 4-5 nút mạng. Phương pháp chọn mẫu dựa trên các trường hợp điển hình trong quản trị CSDL phân tán. Phân tích chi phí truy vấn được thực hiện dựa trên mô hình chi phí tổng hợp gồm chi phí xuất nhập, chi phí CPU và chi phí truyền dữ liệu. Timeline nghiên cứu kéo dài trong vòng 6 tháng, bao gồm các giai đoạn thu thập tài liệu, xây dựng mô hình, thử nghiệm thuật toán và đánh giá kết quả.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Tác động của phân mảnh và nhân bản đến chi phí truy vấn: Phân mảnh ngang và dọc giúp giảm chi phí truy xuất dữ liệu bằng cách chia nhỏ quan hệ thành các mảnh logic, từ đó giảm kích thước dữ liệu cần xử lý. Ví dụ, phân mảnh ngang quan hệ DUAN theo ngân sách dự án đã giúp giảm chi phí truy vấn đáng kể khi chỉ truy xuất các mảnh liên quan. Nhân bản từng phần làm tăng tính sẵn sàng và hiệu năng, nhưng cũng làm tăng chi phí cập nhật và quản lý bản sao.

2. Chi phí truyền dữ liệu chiếm tỷ trọng lớn trong môi trường phân tán: Qua mô hình chi phí, chi phí truyền dữ liệu có thể gấp 10 lần chi phí truy xuất cục bộ. Ví dụ, trong hai chiến lược thực thi truy vấn, phương án truyền dữ liệu ít hơn đã giảm tổng chi phí từ 23.000 xuống còn 460 đơn vị, tương đương giảm hơn 95%.

3. Hiệu quả của các thuật toán tối ưu hóa truy vấn: Việc áp dụng các heuristic như thực hiện phép chọn sớm, thay thế tích Descartes bằng phép nối, và nhóm các phép toán một ngôi giúp giảm đáng kể kích thước quan hệ trung gian và chi phí thực thi. Các thuật toán như Iteractive Improvement và Stimulated Annealing giúp tìm ra giải pháp gần tối ưu trong không gian tìm kiếm lớn.

4. Tối ưu hóa truy vấn phân tán phức tạp hơn môi trường tập trung: Do phải tính đến chi phí truyền thông và lựa chọn trạm xử lý, bài toán tối ưu hóa truy vấn trong CSDL PT thuộc lớp NP-hard. Việc sử dụng các chiến lược phân rã truy vấn, định vị dữ liệu và tối ưu hóa cục bộ là cần thiết để đạt hiệu quả.

Thảo luận kết quả

Nguyên nhân chính của chi phí truy vấn cao trong CSDL phân tán là do sự phân bố dữ liệu trên nhiều nút và chi phí truyền dữ liệu qua mạng. So với các nghiên cứu trước đây, kết quả này phù hợp với báo cáo của ngành về chi phí truyền thông trong mạng WAN. Việc phân mảnh và nhân bản dữ liệu không chỉ giúp giảm chi phí truy vấn mà còn tăng tính sẵn sàng và độ tin cậy của hệ thống, tuy nhiên cần cân nhắc kỹ lưỡng để tránh tăng chi phí cập nhật. Các thuật toán tối ưu hóa truy vấn được đánh giá là hiệu quả khi áp dụng các heuristic hợp lý, giúp giảm không gian tìm kiếm và chi phí tính toán. Kết quả nghiên cứu có thể được trình bày qua biểu đồ so sánh chi phí truy vấn giữa các chiến lược và bảng thống kê chi phí từng thành phần (truy xuất, CPU, truyền dữ liệu), giúp minh họa rõ ràng tác động của từng yếu tố.

Đề xuất và khuyến nghị

1. Áp dụng phân mảnh hỗn hợp và nhân bản từng phần: Để tối ưu hóa chi phí truy vấn và tăng tính sẵn sàng, các tổ chức nên triển khai phân mảnh hỗn hợp kết hợp với nhân bản từng phần, tập trung vào các mảnh dữ liệu có tần suất truy cập cao. Thời gian thực hiện trong vòng 6 tháng, do bộ phận quản trị CSDL chịu trách nhiệm.

2. Ưu tiên thực hiện phép chọn sớm trong truy vấn: Các hệ quản trị CSDL nên tích hợp các heuristic để thực hiện phép chọn ngay khi truy xuất dữ liệu, nhằm giảm kích thước quan hệ trung gian và chi phí xử lý. Giải pháp này có thể triển khai trong vòng 3 tháng bởi nhóm phát triển phần mềm.

3. Sử dụng thuật toán tối ưu hóa truy vấn hỗn hợp: Kết hợp phương pháp tĩnh và động trong tối ưu hóa truy vấn giúp cân bằng giữa chi phí tối ưu hóa và hiệu quả thực thi. Nên áp dụng trong các hệ thống có truy vấn phức tạp và tần suất cao, với thời gian triển khai khoảng 4 tháng.

4. Tăng cường cập nhật số liệu thống kê định kỳ: Để nâng cao độ chính xác của mô hình chi phí và hiệu quả tối ưu hóa, cần thiết lập cơ chế cập nhật số liệu thống kê về kích thước và phân bố dữ liệu theo định kỳ, tối thiểu mỗi quý một lần. Bộ phận quản trị dữ liệu chịu trách nhiệm thực hiện.

Đối tượng nên tham khảo luận văn

1. Nhà quản trị hệ thống CSDL phân tán: Giúp hiểu rõ các kỹ thuật phân mảnh, nhân bản và tối ưu hóa truy vấn để thiết kế hệ thống hiệu quả, giảm chi phí vận hành.

2. Nhà phát triển phần mềm CSDL: Áp dụng các thuật toán tối ưu hóa truy vấn và heuristic trong phát triển các hệ quản trị CSDL phân tán, nâng cao hiệu năng xử lý.

3. Nhà nghiên cứu công nghệ thông tin: Tham khảo các mô hình lý thuyết, thuật toán và phương pháp phân tích chi phí trong CSDL phân tán để phát triển nghiên cứu sâu hơn.

4. Doanh nghiệp triển khai hệ thống dữ liệu phân tán: Hiểu được các yếu tố ảnh hưởng đến chi phí và hiệu quả truy vấn, từ đó lựa chọn giải pháp phù hợp với nhu cầu kinh doanh và hạ tầng mạng.

Câu hỏi thường gặp

1. Tại sao tối ưu hóa truy vấn trong CSDL phân tán lại phức tạp hơn môi trường tập trung?
   Do dữ liệu phân bố trên nhiều nút mạng, chi phí truyền dữ liệu và lựa chọn trạm xử lý ảnh hưởng lớn đến hiệu năng, làm bài toán thuộc lớp NP-hard, đòi hỏi các thuật toán phức tạp hơn.

2. Phân mảnh dữ liệu có tác dụng gì trong tối ưu hóa truy vấn?
   Phân mảnh giúp chia nhỏ quan hệ thành các mảnh logic, giảm kích thước dữ liệu cần truy xuất và cho phép thực hiện truy vấn song song, từ đó giảm chi phí và thời gian xử lý.

3. Nhân bản dữ liệu có ưu và nhược điểm gì?
   Ưu điểm là tăng tính sẵn sàng và hiệu năng truy cập, nhược điểm là tăng chi phí cập nhật và quản lý bản sao, đòi hỏi cân nhắc kỹ lưỡng khi triển khai.

4. Heuristic trong tối ưu hóa truy vấn là gì?
   Là các quy tắc hoặc phương pháp giúp thu hẹp không gian tìm kiếm chiến lược thực thi truy vấn, nhằm tìm ra giải pháp gần tối ưu với chi phí tính toán thấp hơn.

5. Làm thế nào để đánh giá hiệu quả của một chiến lược tối ưu truy vấn?
   Thông qua mô hình chi phí tổng hợp gồm chi phí xuất nhập, CPU và truyền dữ liệu, hoặc thời gian đáp ứng thực tế, so sánh giữa các chiến lược để chọn phương án tốt nhất.

Kết luận

• Luận văn đã phân tích sâu về các nguyên lý, kỹ thuật phân mảnh, nhân bản và tối ưu hóa truy vấn trong CSDL phân tán, góp phần nâng cao hiệu quả xử lý dữ liệu phân tán.
• Kết quả nghiên cứu chỉ ra chi phí truyền dữ liệu là yếu tố chiếm tỷ trọng lớn trong tổng chi phí truy vấn, cần được ưu tiên tối ưu.
• Các thuật toán tối ưu hóa truy vấn dựa trên heuristic và chiến lược hỗn hợp giúp giảm đáng kể chi phí và thời gian thực thi.
• Đề xuất các giải pháp phân mảnh hỗn hợp, nhân bản từng phần, thực hiện phép chọn sớm và cập nhật số liệu thống kê định kỳ nhằm nâng cao hiệu năng hệ thống.
• Các bước tiếp theo bao gồm triển khai thử nghiệm các giải pháp đề xuất trong môi trường thực tế và phát triển các thuật toán tối ưu hóa truy vấn mới phù hợp với xu hướng công nghệ hiện đại.

Hành động ngay: Các nhà quản trị và phát triển hệ thống CSDL phân tán nên áp dụng các kiến thức và giải pháp trong luận văn để cải thiện hiệu quả quản lý và truy xuất dữ liệu, đồng thời tiếp tục nghiên cứu mở rộng lĩnh vực này.

Trích đoạn nội dung tài liệu

Chương 1 KHÁI QUÁT VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN Chương này trình bày một cách khái quát những kiến thức cơ sở về mô hình quan hệ (lược đồ quan hệ, ngôn ngữ dữ liệu quan hệ…), về hệ CSDL phân tán (các kiến trúc, đặc trưng, và các vấn đề của CSDL phân tán…)[4]. Chương này cung cấp những kiến thức cơ sở cho các chương sau.1 Cơ sở dữ liệu quan hệ Cơ sở dữ liệu (CSDL) là một tập hợp dữ liệu có cấu trúc, liên quan đến các hiện tượng thực tế mà chúng ta cố gắng mô hình hóa chúng. CSDL quan hệ là loại CSDL được cấu trúc theo dạng bảng (table). Về hình thức quan hệ (relation) là một tập con của tích Descartes của một hoặc nhiều miền trị (domain) xác định trên tập các thuộc tính (attributes).

Một quan hệ r xác định trên tập thuộc tính Ω = { A1 , A2 ,. An } , khi đó : r ⊆ Dom( A1 ) × Dom( A2 ) ×. × Dom( An ) Mỗi hàng của quan hệ được gọi là một bộ (tuple), như vậy quan hệ r là một tập hợp các n-bộ có dạng: r ⊆ {(a1 , a2 ,., an ) | ai ∈ Dom( Ai ), với i = 1,2,.n} Trong đó Dom( Ai ) là miền giá trị của thuộc tính Ai. Số thuộc tính của quan hệ gọi là bậc của quan hệ.

Quan hệ r có thể bị thay đổi theo thời gian do việc thực hiện các phép toán cập nhật trên r (thêm vào, loại bỏ, sửa đổi các bộ). Lược đồ quan hệ (relation scheme). Một lược đồ quan hệ R là một cặp có thứ tự R =< Ω, F > , trong đó Ω là tập hữu hạn các thuộc tính của quan hệ, F là tập các điều kiện giữa các thuộc tính (F còn gọi là tập các ràng buộc toàn vẹn). Một ràng buộc trên tập các thuộc tính { A1 , A2 ,., An } là một tính chất trên tập tất cả các quan hệ xác định trên tập thuộc tính này.

z 7 Còn khi nói đến một lược đồ quan hệ, trong đó chỉ tập trung vào khía cạnh mô tả cấu trúc của một quan hệ mà không quan tâm đến bộ cụ thể, ta sẽ dùng ký hiệu: R ( A1 , A2 ,., An ) Với R là tên của quan hệ, A1 , A2 ,., An là danh sách tên các thuộc tính. Thể hiện quan hệ. Với lược đồ quan hệ R, theo thời gian, nhiều quan hệ có cấu trúc và ràng buộc toàn vẹn được mô tả bởi lược đồ này. Mỗi quan hệ như vậy còn được gọi là một thể hiện của lược đồ R.

Lược đồ quan hệ mô tả cấu trúc của quan hệ. Tại mỗi thời điểm lược đồ quan hệ sẽ có một thể hiện quan hệ cụ thể. Khóa của một lược đồ quan hệ là một tập con các thuộc tính không rỗng nhỏ nhất sao cho giá trị của các thuộc tính trong khóa cho phép xác định duy nhất mỗi bộ của quan hệ. Các thuộc tính có mặt trong ít nhất một khóa gọi là các thuộc tính khóa.

Một tập có chứa khóa được gọi là siêu khóa (supperkey). Ta có thể định nghĩa một cách hình thức như sau: Cho lược đồ quan hệ R =< Ω, F > , K ⊆ Ω , K được gọi là khóa của lược đồ quan hệ R nếu thỏa mãn 2 điều kiện sau: i. Bất kỳ hai bộ khác nhau t1 , t 2 ∈ r , r là một thể hiện của R, luôn có t1[ K ] ≠ t 2 [ K ]. Không tồn tại K ' ⊂ K thỏa mãn điều kiện trên.

Tập K sẽ là siêu khóa nếu chỉ thỏa mãn điều kiện (i). Chuẩn hóa – là một quá trình từng bước thay thế một tập quan hệ đã cho bằng các tập quan hệ có cấu trúc ngày càng đơn giản và chuẩn tắc hơn [Tsichritzis and Lochovsky, 1977]. Mục đích của chuẩn hóa là loại bỏ những bất thường của một quan hệ. Quan hệ được chuẩn hóa là quan hệ trong đó mỗi miền của một thuộc tính chỉ chứa những giá trị nguyên tố (atomic), tức là không phân nhỏ được nữa và do đó mỗi giá trị trong quan hệ cũng là nguyên tố.

Theo lý thuyết ban đầu Codd đưa ra có 3 dạng chuẩn của quan hệ: z 8 Về sau Boyce và Codd đã định nghĩa một phiên bản sửa đổi của dạng 3NF, thường được gọi là dạng chuẩn Boyce-Codd (BCNF). Tiếp sau đó là các dạng chuẩn 4NF [Fagin, 1977] và chuẩn 5NF [Fagin, 1979] Yêu cầu của chuẩn hóa là không làm mất mát thông tin khi thay một quan hệ bằng các quan hệ khác. Nếu chúng ta có thể nối các quan hệ kết quả để tạo thành quan hệ ban đầu, thì quá trình phân rã đó được gọi là phân rã không mất thông tin. Một yêu cầu khác đối với quá trình chuẩn hóa là bảo toàn phụ thuộc (dependency preservation).

Phân rã được gọi là bảo toàn phụ thuộc nếu hợp của các phụ thuộc hàm của các quan hệ được phân rã tương đương với bao đóng (closure) của các phụ thuộc hàm trong quan hệ ban đầu. Định nghĩa dạng chuẩn 1NF. Một lược đồ quan hệ R được gọi là ở dạng chuẩn 1NF nếu và chỉ nếu toàn bộ các miền có mặt trong R đều chỉ chứa các giá trị nguyên tố [2]. Định nghĩa dạng chuẩn 2NF.

Lược đồ quan hệ R ở dạng chuẩn 2NF nếu nó ở dạng chuẩn 1NF và nếu mỗi thuộc tính không khóa của R phụ thuộc hàm đầy đủ vào mỗi một khóa [2]. Định nghĩa dạng chuẩn 3NF. Lược đồ quan hệ R ở dạng chuẩn 3NF nếu nó ở dạng chuẩn 1NF và nếu mỗi thuộc tính không khóa của R là không phụ thuộc hàm bắc cầu vào mỗi một khóa [2]. Định nghĩa dạng chuẩn BCNF.

Lược đồ quan hệ với tập các phụ thuộc hàm được gọi là ở dạng chuẩn BCNF nếu X → A thỏa trên R, A ∉ X thì X là một siêu khóa của R [2]. z 9 Định nghĩa phụ thuộc hàm đầy đủ. Cho lược đồ quan hệ R với tập thuộc tính Ω = { A1 , A2 ,. An } , X và Y là hai tập thuộc tính khác nhau X ⊆ Ω và Y ⊆ Ω.

Y là phụ thuộc hàm đầy đủ vào X nếu Y là phụ thuộc hàm vào X nhưng không phụ thuộc vào bất kỳ một tập con thực sự nào của X [2].3 Ngôn ngữ dữ liệu quan hệ [4]. Các ngôn ngữ thao tác dữ liệu (DML) được phát triển cho mô hình quan hệ (được gọi là ngôn ngữ truy vấn – query language) được chia thành hai nhóm cơ bản.: các ngôn ngữ dựa trên đại số quan hệ (relational algebra) và các ngôn ngữ dựa trên phép tính quan hệ. Khác biệt giữa chúng là cách thức người sử dụng đưa ra câu truy vấn. Đại số quan hệ thuộc loại thủ tục (procedural), trong đó người dùng cần phải đặc tả, nhờ một số toán tử, xem làm thế nào để thu được kết quả.

Ngược lại phép tính quan hệ thuộc loại phi thủ tục (nonpropcedural), người sử dụng chỉ cần đặc tả các mối liên hệ cần phải bảo đảm trong kết quả. Cả hai đều được Codd đưa ra và đều tương đương về khả năng diễn tả. Đại số quan hệ được sử dụng nhiều hơn trong các nghiên cứu về CSDL phân tán vì nó ở mức thấp hơn và tương ứng trực tiếp hơn với chương trình được trao đổi trên mạng. Về cơ bản thì phép tính quan hệ có thể được dịch thành đại số quan hệ.

Đại số quan hệ là cơ sở quan trọng trong việc tối ưu hóa truy vấn, sau đây sẽ trình bày một số các phép toán trên các quan hệ. Đại số quan hệ có một tập hợp các phép toán trên các quan hệ. Mỗi toán tử nhận một hoặc hai quan hệ làm toán hạng và cho ra một quan hệ mới (quan hệ kết quả), đến lượt nó lại có thể sử dụng làm toán hạng cho một toán tử khác. Các phép toán này cho phép vấn tin và cập nhật CSDL quan hệ.

Có năm phép toán cơ bản và năm phép khác có thể được định nghĩa theo năm phép toán cơ bản này. Đó là các phép chọn (selection), chiếu (projection), hợp (union), trừ (set difference), và tích Descartes. Hai phép toán đầu tiên thuộc loại một ngôi, ba phép toán sau thuộc loại hai ngôi. Các phép toán bổ sung có thể là: giao (intersection), nối θ ( θ -join), nối tự nhiên (natural join), nối nửa (semi join) và phép chia (division) [4].

Trong đó toán hạng của phép toán hai ngôi phải khả hợp z 10 (union compatible). Hai quan hệ được gọi là khả hợp nếu chúng có cùng bậc (có số thuộc tính bằng nhau) và thuộc tính thứ i của quan hệ này có miền xác định trùng với miền của thuộc tính thứ i của quan hệ kia. Phép chọn trên quan hệ R với vị từ p là tập tất cả các bộ t của R thỏa p σ p ( R) = {t ∈ R ∧ p(t )} Phép chiếu của quan hệ R trên tập các thuộc tính X của quan hệ R, là một quan hệ trên tập thuộc tính X, được xây dựng bằng cách loại đi trong quan hệ R những thuộc tính không nằm trong X. Vì thế bậc của quan hệ kết quả luôn nhỏ hơn bậc của quan hệ gốc ∏ X ( R ) = {t[ X ] | t ∈ R} Phép hợp.

Hợp của hai quan hệ R và S, là tập tất cả các bộ thuộc R hoặc thuộc S hoặc thuộc cả hai. Cần chú ý rằng R và S phải khả hợp. R ∪ S = {t | t ∈ R hoặc t ∈ S hoặc t ∈ R và S } Phép trừ. Hiệu của hai quan hệ R và S là tập tất cả các bộ của R không thuộc S.

R − S = {t | t ∈ R và t ∉ S } Tích Descartes. Tích Descartes của hai quan hệ R bậc n và S bậc m có kết quả là tập các (n+m)-bộ sao cho mỗi bộ này có n thành phần đầu thuộc R và m thành phần sau thuộc S.bm ) ∈ S } Phép giao. Giao của hai quan hệ R và S, là tập tất cả các bộ t thuộc về cả hai quan hệ R và S. Giao có thể biểu thị bằng các toán tử cơ bản như sau: R ∩ S = {t | t ∈ R, t ∈ S } = R − ( R − S ) Nối- θ.

Phép nối này là một dẫn xuất của tích Descartes. Có nhiều kiểu nối, và kiểu nối tổng quát nhất là nối- θ , hay đơn giản là nối. Với F là vị từ nối: R >< F S = σ F ( R × S ) Nối tự nhiên.