Nghiên cứu cây quyết định và ứng dụng để phân loại khách hàng vay vốn tại ngân hàng Vietinbank chi nhánh Kon Tum
1. Lý do chọn đề tài
Như chúng ta đã biết máy tính điện tử ra đời và phát triển đã trở thành công cụ có khả năng lưu trữ khổng lồ, tốc độ truy xuất và xử lí dữ liệu rất nhanh. Chính vì vậy cần phải tạo lập được các phương thức mô tả, các cấu trúc dữ liệu để có thể sử dụng máy tính trợ giúp đắt lực cho con người trong việc lưu trữ và khai tác thông tin. Cơ sở dữ liệu và hệ quản trị cơ sở dữ liệu ra đời và phát triển nhằm đáp ứng nhu cầu trên.
Những ứng dụng của hệ thống thông tin trong bài toán quản lý là những ứng dụng vô cùng quan trọng. Nó không những giải phóng công sức cho những người quản lý mà còn đem lại sự chính xác, nhanh gọn và kịp thời trong công việc quản lý. Khung nhìn thực (KNT) là một kĩ thuật đóng vai trò không nhỏ đối với hệ quản trị cơ sở dữ liệu nó có thể giúp tăng tốc nhiều lần các truy vấn phức tạp trên các CSDL với số lượng bản ghi rất lớn, cho phép thực thi các truy vấn phức tạp trên các CSDL dung lượng hàng terabytes trong vài giây hoặc phần nhỏ của giây. Thay vì phải đi tìm tất cả bảng gốc và xử lý rất phức tạp trên lượng lớn dữ liệu mà chúng ta chỉ cần ghi lại những kết quả truy vấn để sử dụng thì tốc độ thực thi truy vấn được tăng lên rất nhiều lần với lượng dữ liệu lớn như hiện nay. Khung nhìn thực là kết quả thực thi truy vấn được lưu lại trong cơ sở dữ liệu. Hệ quản trị cơ sở dữ liệu có thể sử dụng nó với số lượng bản ghi nhỏ chứa kết quả có sẵn để trả lời các truy vấn một cách nhanh chóng. Chính vì vậy bản thân đề xuất thực hiện đề tài: “NGHIÊN CỨU ỨNG DỤNG LÝ THUYẾT ĐỒ THỊ ĐỂ TÌM PHẦN CHUNG LỚN NHẤT GIỮA HAI TRUY VẤN” để làm luận văn thạc sĩ.
2. Lịch sử vấn đề nghiên cứu
Lý thuyết về HỆ QT cơ sở dữ liệu (CSDL
3. Mục tiêu nghiên cứu
– Nghiên cứu hỗ trợ khung nhìn thực trong hệ quản trị cơ sở dữ liệu PostgreSQL 13 nguồn mở. Nghiên cứu lý thuyết đồ thị (LTĐT) vào khung nhìn thực(KNT) của CSDL.
4. Đối tượng và phạm vi nghiên cứu
- Đối tượng
– Phương pháp mô hình hóa dữ liệu với lý thuyết đồ thị. Khung nhìn thực trong hệ quản trị cơ sở dữ liệu SQL.
- Phạm vi nghiên cứu
– Hệ quản trị CSDL SQL server/ PostgreSQL nguồn mở. KNT trong hệ quản trị cơ sở dữ liệu SQL server/ PostgreSQL 13 nguồn mở. Ngôn ngữ lập trình C++ như: Dev – C++/ CodeBlocks. Cách thức tổ chức dữ liệu và việc truy cập dữ liệu bằng LTĐT.
5. Phương pháp nghiên cứu
Nghiên cứu lý thuyết: Tìm hiểu các thuật toán, cách cải tiến thuật toán để áp dụng.
Nghiên cứu thực tiễn: Xây dựng một hệ thống ứng dụng cụ thể. Nghiên cứu ngôn ngữ lập trình, xây dựng giao diện chương trình.
6. Nhiệm vụ nghiên cứu
Nhiệm vụ chính chính của đề tài tìm hiểu hệ QT CSDL
- Đọc dữ liệu từ CSDL
- Xử lý dữ liệu.
- Lưu trữ dưới dạng bảng
- Đầu ra là kết quả yêu cầu truy vấn
7. Bố cục báo cáo
Nội dung báo cáo chia làm các chương sau:
Chương 1. Tổng quan về LTĐT và KNT
Chương 2. Thuật toán tìm phần chung lớn nhất giữa hai truy vấn
Chương 3. Kết quả DEMO chương trình ứng dụng
8. Ý nghĩa của đề tài
Tìm hiểu hệ thống lại những kiến thức liên quan đến cơ sở dữ liệu quan hệ, hiểu rõ hơn tầm quan trọng của khung nhìn thực, ứng dụng lý thuyết đồ thị để tìm phần chung của hai truy vấn.
Chương 1. TỔNG QUAN VỀ LÝ THUYẾT ĐỒ THỊ VÀ KHUNG NHÌN THỰC
- Cấu trúc dữ liệu đồ thị
- Cơ sở dữ liệu đồ thị là một tập hợp các nút (hoặc đỉnh) và các cạnh (hoặc các mối quan hệ). Một nút đại diện cho một thực thể (ví dụ: một người hoặc một tổ chức) và một cạnh đại diện cho mối quan hệ giữa hai nút mà nó kết nối (ví dụ: lượt thích hoặc bạn bè). Cả hai nút và cạnh có thể có các thuộc tính liên kết với chúng.
1.1.2. Những khái niệm cơ bản về LTĐT
Đồ thị là mô hình biểu diễn một tập các đối tượng và mối quan hệ hai ngôi giữa các đối tượng:
G = (V, E)
Có thể định nghĩa đồ thị G là một cặp (V, E): G = (V, E). Trong đó V là tập các đỉnh (vertices hoặc node) biễu biễn các đối tượng và E gọi là tập các cạnh (edges) biểu diễn mối quan hệ giữa các đối tượng.
Như trên định nghĩa đồ thị G = (V, E) là một cấu trúc rời rạc, tức là các tập V và E là tập không quá đếm được, vì vậy ta có thể đánh số thứ tự 1, 2, 3… cho các phần tử của tập V và E và đồng nhất các phần tử của tập V và E với số thứ tự của chúng. Hơn nữa, đứng trên phương diện người lập trình cho máy tính thì ta chỉ quan tâm đến các đồ thị hữu hạn (V và E là tập hữu hạn) mà thôi, chính vì vậy từ đây về sau, nếu không chú thích gì thêm thì khi nói tới đồ thị, ta hiểu rằng đó là đồ thị hữu hạn.
- Cạnh liên thuộc, đỉnh kề
Đối với đồ thị vô hướng G = (V, E). Xét một cạnh e E, nếu e = (u, v) thì ta nói hai đỉnh u và v là kề nhau (adjacent) và cạnh e này liên thuộc (incident) với đỉnh u và đỉnh v.
1.1.2.3. Biểu diễn đồ thị trên máy tính
Danh sách kề
• Biểu diễn danh sách kề bằng mảng
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | |
| adj: | 2 | 3 | 1 | 3 | 4 | 5 | 1 | 2 | 5 | 2 | 5 | 2 | 3 | 4 |
1
2
3
4
5
| 1 | 2 | 3 | 4 | 5 | 6 | |
| head: | 0 | 2 | 6 | 9 | 11 | 14 |
Vấn đề sử dụng các KNT để trả lời các truy vấn nhận được sự quan tâm đáng kể dưới dạng ứng dụng chúng trong nhiều ứng dụng quản trị dữ liệu, chẳng hạn như trong liên kết dữ liệu, trong các kho dữ liệu, trong thiết kế web, trong tối ưu hoá truy vấn và thậm chí KNT được ứng dụng trong bài toán cập nhật các KNT. Khi ứng dụng KNT, hệ quản trị CSDL phải giải quyết bài toán được định dạng như sau: cho một truy vấn trên một lược đồ CSDL và tập hợp các KNT trên chính lược đồ CSDL đó, có thể sử dụng các truy vấn đến các KNT để trả lời truy vấn đó hay không.
1.2.2. Các loại truy vấn cần quan tâm
KNT là kết quả truy vấn được giữ lại trong CSDL dưới dạng bảng. Nếu truy vấn người dùng nhập vào có thể viết lại hướng qua truy vấn tạo KNT, thì có thể lấy kết quả từ KNT, thay vì lấy dữ liệu từ các bảng gốc và xử lý. Để hiểu về KNT ta xét một số mẫu truy vấn. Ký hiệu truy vấn tạo KNT là 𝑄𝑀 (materialized view query) và truy vấn do người dùng gửi đến HQT CSDL là 𝑄𝑈 (user query). Truy vấn viết lại để sử dụng KNT được ký hiệu là 𝑄𝑅 (rewritten query).
- Xét một CSDL QUẢN LÝ SINH VIÊN
CSDL quản lý Sinh Viên có tên SinhVien
Cấu trúc các Table như sau:
Khoa 1-n Lớp 1-n SinhVien 1-n Điểm n-1 Môn_Học n-1 Khối_Kiến_Thức
Khoa (Khoa)
| Ma_Khoa | Ten_Khoa | Nam_Thanh_Lap |
Lop(Lớp)
| Ma_Lop | Ma_Khoa | Ten_Lop |
SinhVien(Sinh viên)
| Ma_SV | Ma_Lop | HoTen | Ns | Dc |
Diem(Điểm)
| Ma_SV | Ma_MH | Diem |
MonHoc(Môn học)
| Ma_MH | Ma_KT | Ten_MH |
Khoi_KT(Khối kiến thức)
| Ma_KT | Ten_KT |
- Các cặp trường hợp dùng chung kết quả:
- Trường hợp tập có 2 bảng: SinhVien – Diem. Diem – MonHoc
- Trường hợp tập có 2 bảng: Lop – SinhVien – Diem. SinhVien – Diem – MonHoc
- Trường hợp tập có 4 bảng(Phần chung lớn nhất)
- Lop – SinhVien – Diem – MonHoc
- Phần không chung của các truy vấn:
- Lop – SinhVien
- Xét một CSDL QUẢN LÝ BÁN HÀNG
Database với tên QLBanHang
Kết quả phần chung của hai truy vấn là: HOADON – KHACHHANG có mối quan hệ n – 1
Từ đây ta có thể sử dụng QR để làm truy vấn chung
- Truy vấn danh sách nhân viên từng làm việc với Khách hàng có mã MaKH là “S001”
| Select NV.”HoNV”, NV.”TenNV”, NV.”DienThoai”, HD.”NgayLapHD”, HD.”NgayNhanHang” |
| FROM “KHACHHANG” as KH |
| JOIN “HOADON” as HD ON HD.”MaKH” = KH.”MaKH” |
| JOIN “NHANVIEN” as NV ON HD.”MaNV” = NV.”MaNV” |
| WHERE KH.”MaKH” = ‘S001’; |
- Truy vấn danh sách sản phẩm mã Khách hàng có MaKH là “D100” đã từng mua
Select SP.”TenSP”, HD.”NgayLapHD”, HD.”NgayNhanHang”, SP.”DonGia”, CT.”SoLuong”
FROM “KHACHHANG” AS KH
JOIN “HOADON” AS HD ON KH.”MaKH” = HD.”MaKH”
JOIN “CHITIETHD” as CT ON CT.”MaHD” = HD.”MaHD”
JOIN “SANPHAM” AS SP ON SP.”MaSP” = CT.”MaSP”
WHERE KH.”MaKH” = ‘D100’
- Tạo KNT:
CREATE MATERIALIZED VIEW MV as
select KH.”MaKH”, HD.”NgayLapHD”, HD.”NgayNhanHang”, HD.”MaHD”, HD.”MaNV”
FROM “KHACHHANG” AS KH
JOIN “HOADON” AS HD ON KH.”MaKH” = HD.”MaKH”
- Truy vấn danh sách nhân viên từng làm việc với Khách hàng có MaKH là “S001”
Select NV.”HoNV”, NV.”TenNV”, NV.”DienThoai”, HD.”NgayLapHD”,HD.”NgayNhanHang”
FROM MV JOIN “NHANVIEN” as NV ON MV.”MaNV” = NV.”MaNV”
JOIN “HOADON” as HD ON MV.”MaHD” = HD.”MaHD”
WHERE MV.”MaKH” = ‘S001’
- Truy vấn danh sách sản phẩm mã Khách hàng có MaKH là “D100” đã từng mua
Select SP.”TenSP”, MV.”NgayLapHD”, MV.”NgayNhanHang”, SP.”DonGia”, CT.”SoLuong”
FROM MV
JOIN “CHITIETHD” as CT ON CT.”MaHD” = MV.”MaHD”
JOIN “SANPHAM” AS SP ON SP.”MaSP” = CT.”MaSP”
WHERE MV.”MaKH” = ‘D100’
Khi ta dùng truy vấn bình thường và có sử dụng KNT thì kết quả như nhau
- Xét một CSDL KNT của học sinh
Gồm có 5 bảng: class; course; grade; student; testscore.
class(id, classname, gradeid)
course(id, coursename)
grade(id, gradename)
student(id, fullname, birthday, country, classid)
testcore(studentid, courseid, score)
- Thử nghiệm và đánh giá
Sử dụng phần mềm CSDL postgreSQL 13. Kiểm thử trên môi trường máy tính là hệ điều hành windows 10; 64 bit; Intel Core i7 – 6600U 2.60GHz; Ram 16.0 GB
Bảng 1: Truy vấn tạo KNT
| KNT | QM | Mục đích |
| mv1 | CREATE MATERIALIZED VIEW mv1 AS Select ClassID, ClassName, GradeId, Min(Score) as MinScore, Max(Score) as MaxScore, Avg(Score) as AvgScore From TestScore Inner join Student on StudentId = Student.ID Inner join Class on ClassId = Class.ID Group by ClassID, ClassName, GradeId Order by ClassID | Tính điểm thấp nhất, điểm cao nhất và điểm trung bình các môn học của học sinh theo các lớp học. |
| mv2 | CREATE MATERIALIZED VIEW mv2 AS Select StudentId, FullName, Country, Birthday, Avg(Score) as AvgScore From TestScore Inner join Student on StudentId = Student.ID Group by StudentID, FullName, Country, Birthday Order by AvgScore; | Hiển thị thông tin của học sinh theo điểm trung bình. |
Bảng 2: Các truy vấn thử nghiệm và KNT có thể viết lại
| # | QU | Dùng KNT | QR |
| 1 | Select ClassID, ClassName, Min(Score) as MinScore, Max(Score) as MaxScore, Avg(Score) as AvgScore From TestScore Inner join Student on StudentId = Student.ID Inner join Class on ClassId = Class.ID Group by ClassID, ClassName Order by ClassID | mv1 | Select ClassID, ClassName, MinScore, MaxScore, AvgScore From mv1 |
| 2 | Select tb1.GradeId, GradeName, Max(AvgScore) as MaxAvgScore From ( Select Avg(Score) as AvgScore , ClassId, Class.GradeId From TestScore Inner join Student on StudentId = Student.ID Inner join Class on ClassId = Class.ID Group by ClassId, Class.GradeId ) as tb1,Grade Where Grade.Id = tb1.GradeId Group by tb1.GradeId, GradeName Order by tb1.GradeId; | mv1 | Select GradeId, GradeName, Max(avgScore) from mv1 inner join Grade on GradeId = Grade.Id Group by GradeId, GradeName Order by GradeId; |
| 3 | Select StudentId, FullName, Country, Birthday, Avg(Score) as AvgScore From TestScore Inner join Student on StudentId = Student.ID Group by StudentID, FullName, Country, Birthday Order by AvgScore; | mv2 | Select StudentId, FullName, Country, Birthday, AvgScore From mv2; |
| 4 | Select StudentId, FullName, Country, Birthday, Avg(Score) as AvgScore From TestScore Inner join Student on TestScore.StudentId = Student.ID Inner join Class on Student.ClassId = Class.ID Inner join Grade on class.GradeId = Grade.Id Where GradeName = 10 Group by TestScore.StudentID, FullName, Country, Birthday Order by AvgScore; | mv2 | Select StudentId, mv2.FullName, mv2.Country, mv2.Birthday, mv2.AvgScore from mv2, student, class, grade where StudentId = student.Id and ClassId = Class.Id and GradeId = Grade.Id and GradeName = 10; |
Bảng 3: Đánh giá hiệu quả mô-đun viết lại truy vấn
| # | Thời gian thực hiện đối với database có trên 400.000 bảng ghi | KNT | |
| Thời gian thực hiện QU | Thời gian thực hiện QR | ||
| 1 | 605 ms | 212 ms | mv1 |
| 2 | 441 ms | 66 ms | mv1 |
| 3 | 590 ms | 130 ms | mv2 |
| 4 | 214 ms | 144 ms | mv2 |
- Kết quả đạt được
Từ bảng 3 cho thấy khi viết lại truy vấn QR thì thời gian thực hiện truy vấn nhỏ hơn nhiều so với trước đó không sử dụng KNT.
Chương 2: THUẬT TOÁN TÌM PHẦN CHUNG LỚN NHẤT GIỮA HAI TRUY VẤN
Coi mỗi bảng như 1 đỉnh của đồ thị, đối với mỗi loại quan hệ, sẽ đặt một giá trị trọng số khác nhau:
+ Mối quan hệ 1-n: Trọng số đặt là 2
+ Mối quan hệ n-1: Trọng số đặt là -2
+ Mối quan hệ 1-1: Trọng số đặt là 1
+ Mối quan hệ n-n: Trọng số đặt là 3
2.2.1. Mô hình biểu diễn truy vấn
- Truy vấn SPJ
Truy vấn SPJ tạo KNT thứ x có thể được biểu diễn như sau: . Trong đó:
– tập các cột/biểu thức được lựa chọn trong mệnh đề SELECT.
là tập hợp các bí danh (alias) của các biểu thức tương ứng trong ; là bí danh của . Mặc định có dạng hoặc – trùng với tên cột trong . Tập hợp các cột trong bảng KNT Tmv chính là .
– tập các bảng gốc được sử dụng trong truy vấn. Mệnh đề FROM là sự kết hợp của và – tập hợp các điều kiện của các phép nối giữa các bảng trong .
– mệnh đề WHERE, điều kiện chọn lựa bản ghi để xử lý. Trong trường hợp truy vấn bao gồm phép nối tường minh, không rỗng. Ngược lại, rỗng và bao gồm cả Đặt . Giả thiết rằng và được chuyển đổi về dạng chuẩn tắc hội.
KNT là kết quả truy vấn được giữ lại trong CSDL dưới dạng bảng. Nếu truy vấn người dùng nhập vào có thể viết lại hướng qua truy vấn tạo KNT, thì có thể lấy kết quả từ KNT, thay vì lấy dữ liệu từ các bảng gốc và xử lý. Ta chỉ xem xét một số mẫu truy vấn và sử dụng KNT. Để đơn giản, ta ký hiệu truy vấn tạo KNT là (materialized view query) và truy vấn do người dùng gửi đến HQT CSDL là (user query). Truy vấn viết lại để sử dụng KNT được ký hiệu là (rewritten query). Tương ứng, ta có truy vấn tạo KNT , truy vấn của của người dùng và truy vấn viết lại .
- Truy vấn với hàm gộp
KNT là kết quả truy vấn được giữ lại trong CSDL dưới dạng bảng. Nếu truy vấn người dùng nhập vào được viết lại hướng qua truy vấn tạo KNT, thì có thể lấy kết quả từ KNT, thay vì lấy dữ liệu từ các bảng gốc và xử lý. Có vô số mẫu truy vấn khác nhau. Tuy nhiên, tài liệu này chỉ xem xét một số mẫu truy vấn và sử dụng KNT để trả lời các truy vấn đó. Để đơn giản, ta ký hiệu truy vấn tạo KNT là và truy vấn do người dùng gửi đến HQT CSDL là . Truy vấn viết lại để sử dụng KNT được ký hiệu là . Tất nhiên, phải tương đương .
Kết quả thực thi một truy vấn bao gồm phép gộp nhóm và hàm thống kê chỉ có thể được sử dụng để trả lời các truy vấn khác nếu chúng có mệnh đề WHERE tương đương nhau.
Truy vấn tạo KNT thứ x-th bao gồm các hàm thống kê có thể được biểu diễn như sau: . Trong đó:
– – tập các cột/biểu thức được lựa chọn trong mệnh đề SELECT. là tập hợp các cột của các bảng trong mệnh đề SELECT. là tập hợp các hàm thống kê với biểu thức (E) trên các cột từ bảng gốc như SUM(E), COUNT(E), MIN(E) và MAX(E). Để phục vụ quá trình cập nhập gia tăng đồng bộ KNT cũng như tăng khả năng sử dụng KNT sau này, AVG(E) tự động được chuyển thành SUM(E) và COUNT(E). E không chứa các hàm thống kê. là tập hợp các bí danh (alias) của các biểu thức tương ứng trong ; là bí danh của . là tập hợp các bí danh của các biểu thức tương ứng trong ; là bí danh của . Mặc định có dạng hoặc – trùng với tên cột trong . Tập hợp các cột trong bảng KNT Tmv chính là .
– – mệnh đề FROM. Mệnh đề FROM là sự kết hợp của tập các bảng gốc được sử dụng trong truy vấn và – tập hợp các điều kiện của các phép nối giữa các bảng trong .
– – mệnh đề WHERE, điều kiện chọn lựa bản ghi để xử lý. Trong trường hợp truy vấn bao gồm phép nối tường minh, không rỗng. Ngược lại, rỗng và bao gồm cả
– – tập các cột/biểu thức gộp nhóm mệnh đề GROUP BY. Mặc định đã có sự biến đổi truy vấn tạo KNT trong quá trình tạo KNT để kết quả bao gồm cả các biểu thức trong mệnh đề GROUP BY; nghĩa là, tự thân đã bao gồm .
Với truy vấn không bao gồm hàm thống kê, không chứa hàm thống kê, , và – rỗng. Tương ứng, ta có truy vấn tạo KNT , truy vấn của của người dùng và truy vấn viết lại . Bảng KNT Tmv bao gồm các cột . Chúng ta quan tâm đến các dạng truy vấn và viết lại truy vấn theo mức độ phức tạp từ thấp đến cao.
2.2.2. Thuật toán tìm phần chung lớn nhất để viết lại truy vấn
Trong khuôn khổ tài liệu này, ta giới hạn tìm kiếm phần chung lớn nhất giữa hai biểu thức phép nối giữa hai truy vấn. Bản chất hai biểu thức nối của hai truy vấn là hai cây nhị phân. Tuy nhiên, “nội dung” có thể dùng chung giữa hai truy vấn phải đảm bảo tính đơn hình (monomorphism). Như vậy, bài toán đặt ra là phải tìm được phần chung lớn nhất giữa hai cây nhị phân là hai biểu thức phép nối và kết quả thực thi biểu thức phép nối của hai phần chung này phải đảm bảo tính đơn hình.
- Mối quan hệ giữa các bảng tham gia vào phép nối
Mối quan hệ được xác định như sau: (i) A 1-n B, nghĩa là có khoá của A làm khoá ngoại trong B; (ii) A 1-1 B, nghĩa là một khoá của A (hoặc B) làm khoá ngoại trong B (hoặc A) và khoá ngoại này đồng thời cũng là khoá (unique key) của B (hoặc A); (iii) A n-n B, nghĩa là một tập thuộc tính của A có mặt trong B hoặc ngược lại và chúng không phải là khoá của một bảng nào.
Nếu xét trong bối cảnh phép nối , ta có có thể thuộc các dạng sau:
- , thường xác định mối quan hệ nếu là khoá và là khoá ngoại; nếu là khoá và là khoá ngoại và đồng thời là khoá; nếu cả và đều không phải là khoá.
- , thường xác định mối quan hệ .
Ta chỉ xét các trường hợp mối quan hệ và .
- Xây dựng cây phép nối
Mục đích: Xây dựng cây biểu thức phép nối dựa trên biểu thức phép nối, làm sao cho:
- Cây phải tương đương với biểu thức phép nối của truy vấn
- Tìm được phần chung lớn nhất giữa hai cây nhị phân theo cách hiệu quả nhất
- Đơn giản trong việc đảm bảo tính đơn hình của kết quả thực thi hai phần chung sẽ tìm được của hai cây
Thủ tục: Sinh cây genTree(biểu-thức-phép-nối, parent = null, trọng-số = 0)
Đầu vào:
- DS bảng tham gia vào biểu thức phép nối
- Biểu thức phép nối (về nguyên tắc nó bao gồm DS bảng)
- DS mối quan hệ giữa các bảng.
- Parent
- Trọng-số (mặc định = 0, nghĩa là phép nối đầu tiên được xét)
Đầu ra: Cây phép nối đã sắp xếp và có đánh trọng số
B0. IF trọng số = 0 (nghĩa phép nối đầu tiên được xét), THEN trọng-số = 100
B1. Cho phép nối .
Xét điều kiện nối . Nếu , hoán vị và .
Sinh nút gốc root().
Sinh nút lá left, root().left = left, left.parent = root(). Left gắng liền với vế trái của .
Sinh nút lá right, root().right = right, right.parent = root(). Right gắn liền với vế phải của .
Root().trọng-số = trọng-số.
B2. Nếu vế trái là một biểu thức trong ngoặc ‘(…)’ thì
BEGIN
IF mối quan hệ left 1-n right, THEN Root().left = genTree(biểu-thức-vế-trái, Root(), trọng-số + 1).
ELSE
IF mối quan hệ left n-1 right, THEN Root().left = genTree(biểu-thức-vế-trái, Root(), trọng-số).
ELSE
IF mối quan hệ left 1-1 right, THEN Root().left = genTree(biểu-thức-vế-trái, Root(), trọng-số).
END
ELSE
BEGIN //Vế trái là một bảng
IF mối quan hệ left 1-n right, THEN
Root().left = ,
.trọng-số = trọng-số + 1.
.parent = root()
ELSE
IF mối quan hệ left n-1 right, THEN
Root().left = ,
.trọng-số = trọng-số.
.parent = root()
ELSE
IF mối quan hệ left 1-1 right, THEN
Root().left = ,
.trọng-số = trọng-số.
.parent = root()
END
B3. Nếu vế phải là một biểu thức trong ngoặc ‘(…)’ thì
BEGIN
IF mối quan hệ left 1-n right, THEN Root().right = genTree(biểu-thức-vế-phải, Root(), trọng-số).
ELSE
IF mối quan hệ left n-1 right, THEN Root().right = genTree(biểu-thức-vế-phải, Root(), trọng-số + 1).
ELSE
IF mối quan hệ left 1-1 right, THEN Root().left = genTree(biểu-thức-vế-phải, Root(), trọng-số).
END
ELSE
BEGIN //Vế phải là một bảng
IF mối quan hệ left 1-n right, THEN
Root().right = ,
.trọng-số = trọng-số.
.parent = root()
ELSE
IF mối quan hệ left n-1 right, THEN
Root().right = ,
.trọng-số = trọng-số + 1.
.parent = root()
ELSE
IF mối quan hệ left 1-1 right, THEN
Root().right = ,
.trọng-số = trọng-số.
.parent = root()
END
B4. Trả lại root().
- Tìm phần chung lớn nhất
+ Ý tưởng chung:
- Dùng ý tưởng partitle graph để so sánh hai cây và tìm phần chung lớn nhất.
- Hai cây đảm bảo tính isomorphism khi và chỉ khi hai nút (bảng) có trọng số nhỏ nhất là trùng nhau.
Thuật toán tìm phần chung lớn nhất.
Đầu vào: 2 cây biểu thức phép nối và .
Đầu ra: Cây con là phần chung lớn nhất.
+ Các bước của thuật toán.
| B1. Lấy hai bảng có trọng số thấp nhất giữa hai phần: và . |
| B2. IF , THEN |
| RETURN Không có phần chung |
| B3. LeftCurrent = .parent, RightCurrent = .parent; |
| B4. Loại bỏ tất cả các nút lá từ hai cây và . |
| B5. Xây dựng partitle graph với phần trái là và phần phải là . |
| B6. Xuất phát từ LeftCurrent và RightCurrent, MaxCommonSubtree = Tìm phần chung lớn nhất giữa phần trái và phần phải. |
| B7. Gắn các nút lá là các bảng vào MaxCommonSubtree. |
| B8. RETURN MaxCommonSubtree. |
Chương 3: KẾT QUẢ DEMO CHƯƠNG TRÌNH ỨNG DỤNG
3.1. GIỚI THIỆU VỀ CHƯƠNG TRÌNH
Chương trình được viết bằng C++ với giả thuyết 2 truy vấn sql đã được chuyển sang dữ liệu dạng đồ thị
3.1.1. Môi trường hoạt động
Hệ điều hành windows 32bit/64 bit
3.1.2. Sơ đồ hoạt động của chương trình
Xử lí tìm cây con chung lớn nhất của 2 cây truy vấn
3.2.1. Chức năng Đọc dữ liệu
Đọc từ file input 🡪 Kết quả Output
3.2.2. Kiểm thử và đánh giá chương trình
Ta sẽ thực hiện thử nghiệm với 2 bộ dữ liệu mẫu
3.2.2.1. Dữ liệu 1
Input: Output:
3.2.2.2. Dữ liệu 2
Input: Output:
Như vậy với chương trình trên thuật toán tìm phần chung lớn nhất giữa hai truy vấn.
Qua quá trình nghiên cứu và tìm hiểu về các vấn đề liên quan đến KNT và ứng dụng lý thuyết đồ thị để tìm phần chung lớn nhất của hai truy vấn, luận văn đã hoàn thành và đạt được một số kết quả sau: Luận văn đã tìm hiểu được cơ sở lý thuyết liên quan đến KNT và ứng dụng lý thuyết đồ thị để tìm phần chung lớn nhất của hai truy vấn. Qua quá trình thử nghiệm và đánh giá khả thi của mô đun ứng dụng của KNT và ứng dụng lý thuyết đồ thị để tìm phần chung lớn nhất của hai truy vấn thì tốc độ thực thi các truy vấn được cải thiện rất nhiều lần, thời gian thực thi được rút ngắn.
Trong tương lai, nghiên cứu và tìm hiểu để có thể giải quyết những điều còn tồn đọng, chưa làm được trong luận văn này, đưa ra giải pháp đề xuất có thể tăng tốc truy cập dữ liệu trong công tác quản lý, quản lý điểm, thống kê, phân tích dữ liệu, hoàn thiện hơn các chức năng quản lý dữ liệu. Xây dựng kho dữ liệu phong phú, đầy đủ hơn về thông tin và chi tiết hơn về nội dung, dữ liệu được cung cấp đầy đủ, cập nhật thường xuyên và chính xác. Luận văn đã dựa vào lý thuyết đồ thị để đưa ra thuật toán tìm phần chung lớn nhất của 2 truy vấn, tuy nhiên chưa thực hiện được việc chuyển đổi 1 chuỗi truy vấn SQL sang dạng 1 cây hoàn chỉnh lưu trữ đầy đủ các thông tin của chuỗi truy vấn, cũng như chưa thực hiện từ kết quả cây chung con lớn nhất đã tìm được, chuyển ngược ra lại 1 câu lệnh SQL tạo khung nhìn thực dựa trên cây con chung đó.
E:\DỮ LIỆU COP CỦA CHỊ YẾN\DAI HOC DA NANG\HE THONG THONG TIN\ON QUANG HUNG
