Tài liệu Luận văn Đối sánh tự động lược đồ XML: BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
--------------------------
LUẬN VĂN THẠC SỸ KHOA HỌC
đối sánh tự động l−ợc đồ XML
NGÀNH: CễNG NGHỆ THễNG TIN
MS: ……………………….
Vế SỸ NAM
NGƯỜI HƯỚNG DẪN KHOA HỌC:
TS. HUỲNH QUYẾT THẮNG
HÀ NỘI - 2006
Mục lục
Danh mục từ viết tắt, thuật ngữ.............................. Error! Bookmark not defined.
Danh mục bảng biểu ................................................ Error! Bookmark not defined.
Danh mục hỡnh vẽ..................................................... Error! Bookmark not defined.
Mở đầu ...................................................................... Error! Bookmark not defined.
1. Giới thiệu chung......................................................... Error! Bookmark not defined.
2. Nội dung luận văn ...................................................... Error! Bookmark not defined.
Chương 1 Đối sỏnh lược đồ ..................................... Error! Bookmark not defined.
1....
114 trang |
Chia sẻ: haohao | Lượt xem: 1016 | Lượt tải: 0
Bạn đang xem trước 20 trang mẫu tài liệu Luận văn Đối sánh tự động lược đồ XML, để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
--------------------------
LUẬN VĂN THẠC SỸ KHOA HỌC
®èi s¸nh tù ®éng l−îc ®å XML
NGÀNH: CÔNG NGHỆ THÔNG TIN
MS: ……………………….
VÕ SỸ NAM
NGƯỜI HƯỚNG DẪN KHOA HỌC:
TS. HUỲNH QUYẾT THẮNG
HÀ NỘI - 2006
Mục lục
Danh mục từ viết tắt, thuật ngữ.............................. Error! Bookmark not defined.
Danh mục bảng biểu ................................................ Error! Bookmark not defined.
Danh mục hình vẽ..................................................... Error! Bookmark not defined.
Mở đầu ...................................................................... Error! Bookmark not defined.
1. Giới thiệu chung......................................................... Error! Bookmark not defined.
2. Nội dung luận văn ...................................................... Error! Bookmark not defined.
Chương 1 Đối sánh lược đồ ..................................... Error! Bookmark not defined.
1.1 Tổng quan về đối sánh lược đồ ............................... Error! Bookmark not defined.
1.1.1 Các khái niệm cơ bản về đối sánh lược đồ ......... Error! Bookmark not defined.
1.1.2 Các lĩnh vực ứng dụng đối sánh lược đồ ............ Error! Bookmark not defined.
1.2 Các tiếp cận đối sánh lược đồ ................................. Error! Bookmark not defined.
1.2.1 Phân loại các tiếp cận đối sánh lược đồ............. Error! Bookmark not defined.
1.2.2 Các tiếp cận đối sánh lược đồ ............................ Error! Bookmark not defined.
1.2.3 Các phương pháp đối sánh lược đồ.................... Error! Bookmark not defined.
1.3 Các hệ thống đối sánh lược đồ XML...................... Error! Bookmark not defined.
1.3.1 Cupid (trung tâm nghiên cứu Microsoft) ............ Error! Bookmark not defined.
1.3.2 Similarity Flooding (Đại học Stanford và đại học Leipzig) ... Error! Bookmark
not defined.
1.3.3 LSD (Đại học Washington)................................. Error! Bookmark not defined.
1.3.4 Clio (IBM Almaden và đại học Toronto) ............ Error! Bookmark not defined.
1.3.5 Một số hệ thống đối sánh lược đồ khác .............. Error! Bookmark not defined.
1.4 Kết chương ............................................................... Error! Bookmark not defined.
Chương 2 Các định nghĩa hình thức ...................... Error! Bookmark not defined.
2.1 Vấn đề đối sánh lược đồ XML ................................ Error! Bookmark not defined.
2.1.1 Đối sánh ngữ nghĩa và đối sánh cú pháp ........... Error! Bookmark not defined.
2.1.2 Thông tin đầu vào của tiến trình đối sánh .......... Error! Bookmark not defined.
2.1.3 Thông tin đầu ra của tiến trình đối sánh ............ Error! Bookmark not defined.
2.1.4 Các định nghĩa hình thức.................................... Error! Bookmark not defined.
2.2 Mô hình hóa lược đồ XML...................................... Error! Bookmark not defined.
2.2.1 Các nút đồ thị lược đồ ........................................ Error! Bookmark not defined.
2.2.2 Các cạnh đồ thị lược đồ...................................... Error! Bookmark not defined.
2.2.3 Các ràng buộc đồ thị lược đồ ............................. Error! Bookmark not defined.
2.2.4 Các định nghĩa hình thức.................................... Error! Bookmark not defined.
2.3 Ánh xạ nguồn–đích .................................................. Error! Bookmark not defined.
2.4 Kết chương ............................................................... Error! Bookmark not defined.
Chương 3 Đối sánh tự động lược đồ XML ............ Error! Bookmark not defined.
3.1 Tổng quan về đối sánh tự động lược đồ XML....... Error! Bookmark not defined.
3.2 Đo độ tương đồng ngôn ngữ.................................... Error! Bookmark not defined.
3.2.1 WordNet và quan hệ ngữ nghĩa giữa các từ ....... Error! Bookmark not defined.
3.2.2 Thuật toán của Hirst và St-Onge ........................ Error! Bookmark not defined.
3.2.3 Giải pháp của hệ thống Cupid ............................ Error! Bookmark not defined.
3.3 Xét tính tương thích kiểu dữ liệu lược đồ XML và phân tích phân cấp kiểu
người thiết kế.................................................................. Error! Bookmark not defined.
3.3.1 Xét tính tương thích kiểu dữ liệu lược đồ XML .. Error! Bookmark not defined.
3.3.2 Phân tích phân cấp kiểu người thiết kế .............. Error! Bookmark not defined.
3.4 Đo độ tương đồng cấu trúc...................................... Error! Bookmark not defined.
3.4.1 Định nghĩa ngữ cảnh nút .................................... Error! Bookmark not defined.
3.4.2 Đo độ tương tự đường dẫn.................................. Error! Bookmark not defined.
3.4.3 Đo độ tương đồng ngữ cảnh nút ......................... Error! Bookmark not defined.
3.5 Đo độ tương đồng nút và tạo ánh xạ giữa các phần tử........Error! Bookmark not
defined.
3.5.1 Đo độ tương đồng nút ......................................... Error! Bookmark not defined.
3.5.2 Tạo ánh xạ giữa các nút và cạnh đối sánh ......... Error! Bookmark not defined.
3.6 Đánh giá tiến trình đối sánh lược đồ XML............ Error! Bookmark not defined.
3.6.1 Các phương pháp đánh giá................................. Error! Bookmark not defined.
3.6.2 Đánh giá giải pháp ............................................. Error! Bookmark not defined.
3.7 Áp dụng đối sánh lược đồ trong bài toán chuyển đổi tài liệu có cấu trúc ...Error!
Bookmark not defined.
3.7.1 Tổng quan về tài liệu có cấu trúc ....................... Error! Bookmark not defined.
3.7.2 Chuyển đổi tự động tài liệu có cấu trúc.............. Error! Bookmark not defined.
3.7.3 Mô hình cho hệ thống chuyển đổi tự động tài liệu XML ...Error! Bookmark not
defined.
3.8 Kết chương ............................................................... Error! Bookmark not defined.
Kết luận và hướng phát triển.................................. Error! Bookmark not defined.
1. Đóng góp chính của luận văn.................................... Error! Bookmark not defined.
2. Hướng phát triển........................................................ Error! Bookmark not defined.
Danh mục tài liệu tham khảo .................................. Error! Bookmark not defined.
Phụ lục....................................................................... Error! Bookmark not defined.
Phụ lục A: Ngôn ngữ đánh dấu mở rộng - XML ........ Error! Bookmark not defined.
Phụ lục B: Lược đồ XML .............................................. Error! Bookmark not defined.
Phụ lục C: Thuật toán của Hirst và St-Onge .............. Error! Bookmark not defined.
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
--------------------------
LUẬN VĂN THẠC SỸ KHOA HỌC
®èi s¸nh tù ®éng l−îc ®å XML
NGÀNH: CÔNG NGHỆ THÔNG TIN
MS: ……………………….
VÕ SỸ NAM
NGƯỜI HƯỚNG DẪN KHOA HỌC:
TS. HUỲNH QUYẾT THẮNG
HÀ NỘI - 2006
Đối sánh tự động lược đồ XML
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
i
Lời cảm ơn
Luận văn này đánh dấu kết thúc hai năm cao học tại trường đại học Bách
Khoa Hà Nội. Trong quãng thời gian tuy chưa dài nhưng cũng không phải là ngắn
đó, tôi đã trưởng thành rất nhiều về kiến thức cũng như khả năng nghiên cứu.
Tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo – TS. Huỳnh Quyết Thắng,
người đã hướng dẫn, giúp đỡ tôi hết sức tận tình trong quá trình thực hiện luận văn
tốt nghiệp. Thầy là người đã cung cấp ý tưởng, tài liệu ban đầu về đề tài, các hướng
dẫn quan trọng trong suốt quá trình thực hiện luận văn, dành thời gian đọc và sửa
chữa báo cáo cũng như có những góp ý rất quan trọng cho tôi trong suốt quá trình
hoàn thiện luận văn này.
Tôi xin cám ơn thư viện trường EPFL, Thụy Sỹ đã cung cấp cho tôi một số tài
liệu tham khảo bổ ích, xin cảm ơn các nhóm sinh viên K48 khoa Công nghệ thông
tin, trường đại học Bách Khoa Hà Nội đã tận tình làm việc cùng tôi và góp nhiều
công sức trong quá trình cài đặt thử nghiệm chương trình.
Tôi xin gửi lời cám ơn sâu sắc tới các thầy giáo, cô giáo của trường đại học
Bách Khoa Hà Nội, khoa Công nghệ thông tin đã tận tình giảng dạy, trang bị kiến
thức cho chúng tôi, xin gửi lời cám ơn bộ môn Kỹ thuật hệ thống, khoa Công nghệ
thông tin, trường đại học Xây dựng Hà Nội đã hết sức tạo điều kiện về thời gian cho
tôi hoàn thành luận văn này.
Tôi cũng xin gửi lời cám ơn tới các bạn của tôi, những người đã chia sẻ với tôi
nhiệt huyết và niềm say mê học tập & nghiên cứu khoa học, chia sẻ với tôi kiến thức
và phương pháp tìm hiểu vấn đề, cung cấp cho tôi các tài liệu thiết thực cũng như
những ý tưởng bổ sung cho luận văn, góp phần giúp tôi thực hiện luận văn này
trong sự cố gắng và nỗ lực cao nhất.
Cuối cùng nhưng cũng là điều quan trọng nhất, cho tôi gửi lời cảm ơn sâu sắc
tới bố, mẹ, em trai và những người thân của tôi, những người đã giúp đỡ tôi rất
nhiều cả về vật chất lẫn tinh thần trong suốt quá trình học tập và công tác, động
viên tôi trong những lúc khó khăn cũng như chia sẻ niềm vui với tôi những lúc
thành công. Một lần nữa tôi xin chân thành cám ơn tất cả./.
Hà Nội, tháng 11 năm 2006
Võ Sỹ Nam
Đối sánh tự động lược đồ XML
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
ii
Mục lục
Danh mục từ viết tắt, thuật ngữ........................................................................... iv
Danh mục bảng biểu .............................................................................................. v
Danh mục hình vẽ................................................................................................... v
Mở đầu .................................................................................................................... 1
1. Giới thiệu chung...........................................................................................................1
2. Nội dung luận văn ........................................................................................................3
Chương 1 Đối sánh lược đồ ................................................................................... 6
1.1 Tổng quan về đối sánh lược đồ .................................................................................7
1.1.1 Các khái niệm cơ bản về đối sánh lược đồ ...........................................................7
1.1.2 Các lĩnh vực ứng dụng đối sánh lược đồ ..............................................................8
1.2 Các tiếp cận đối sánh lược đồ .................................................................................14
1.2.1 Phân loại các tiếp cận đối sánh lược đồ.............................................................14
1.2.2 Các tiếp cận đối sánh lược đồ ............................................................................15
1.2.3 Các phương pháp đối sánh lược đồ....................................................................17
1.3 Các hệ thống đối sánh lược đồ XML......................................................................20
1.3.1 Cupid (trung tâm nghiên cứu Microsoft) ............................................................21
1.3.2 Similarity Flooding (đại học Stanford và đại học Leipzig) ...............................23
1.3.3 LSD (đại học Washington)..................................................................................24
1.3.4 Clio (IBM Almaden và đại học Toronto) ............................................................25
1.3.5 Một số hệ thống đối sánh lược đồ khác ..............................................................26
1.4 Kết chương ...............................................................................................................28
Chương 2 Các định nghĩa hình thức .................................................................. 29
2.1 Vấn đề đối sánh lược đồ XML ................................................................................30
2.1.1 Đối sánh ngữ nghĩa và đối sánh cú pháp ...........................................................30
2.1.2 Thông tin đầu vào của tiến trình đối sánh ..........................................................32
2.1.3 Thông tin đầu ra của tiến trình đối sánh ............................................................34
2.1.4 Các định nghĩa hình thức....................................................................................35
2.2 Mô hình hóa lược đồ XML......................................................................................36
2.2.1 Các nút đồ thị lược đồ ........................................................................................37
2.2.2 Các cạnh đồ thị lược đồ......................................................................................37
2.2.3 Các ràng buộc đồ thị lược đồ .............................................................................38
2.2.4 Các định nghĩa hình thức....................................................................................40
2.3 Ánh xạ nguồn–đích ..................................................................................................43
2.4 Kết chương ...............................................................................................................46
Đối sánh tự động lược đồ XML
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
iii
Chương 3 Đối sánh tự động lược đồ XML ........................................................ 47
3.1 Tổng quan về đối sánh tự động lược đồ XML.......................................................48
3.2 Đo độ tương đồng ngôn ngữ....................................................................................49
3.2.1 WordNet và quan hệ ngữ nghĩa giữa các từ .......................................................49
3.2.2 Thuật toán của Hirst và St-Onge ........................................................................50
3.2.3 Giải pháp của hệ thống Cupid ............................................................................52
3.3 Xét tính tương thích kiểu dữ liệu lược đồ XML và phân tích phân cấp kiểu
người thiết kế..................................................................................................................53
3.3.1 Xét tính tương thích kiểu dữ liệu lược đồ XML ..................................................53
3.3.2 Phân tích phân cấp kiểu người thiết kế ..............................................................55
3.4 Đo độ tương đồng cấu trúc......................................................................................56
3.4.1 Định nghĩa ngữ cảnh nút ....................................................................................56
3.4.2 Đo độ tương tự đường dẫn..................................................................................58
3.4.3 Đo độ tương đồng ngữ cảnh nút .........................................................................63
3.5 Đo độ tương đồng nút và tạo ánh xạ giữa các phần tử.........................................66
3.5.1 Đo độ tương đồng nút .........................................................................................66
3.5.2 Tạo ánh xạ giữa các nút và cạnh đối sánh .........................................................67
3.6 Đánh giá tiến trình đối sánh lược đồ XML............................................................68
3.6.1 Các phương pháp đánh giá.................................................................................68
3.6.2 Đánh giá giải pháp .............................................................................................70
3.7 Áp dụng đối sánh lược đồ trong bài toán chuyển đổi tài liệu có cấu trúc ..........72
3.7.1 Tổng quan về tài liệu có cấu trúc .......................................................................73
3.7.2 Chuyển đổi tự động tài liệu có cấu trúc..............................................................76
3.7.3 Mô hình cho hệ thống chuyển đổi tự động tài liệu XML ....................................78
3.8 Kết chương ...............................................................................................................80
Kết luận và hướng phát triển.............................................................................. 81
1. Đóng góp chính của luận văn....................................................................................81
2. Hướng phát triển........................................................................................................84
Danh mục tài liệu tham khảo .............................................................................. 86
Phụ lục................................................................................................................... 88
Phụ lục A: Ngôn ngữ đánh dấu mở rộng - XML ........................................................89
Phụ lục B: Lược đồ XML ..............................................................................................97
Phụ lục C: Thuật toán của Hirst và St-Onge ............................................................100
Đối sánh tự động lược đồ XML
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
iv
Danh mục từ viết tắt, thuật ngữ
Từ viết tắt/ thuật ngữ Giải nghĩa Ghi chú
CSDL Cơ sở dữ liệu
TTNT Trí tuệ nhân tạo
XML eXtended Markup Language
DTD Document Type Definition
XSD XML Schema Definition
SGML Standard Generalized Markup Language
LCS Longest Common Subsequence
Đối sánh tự động lược đồ XML
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
v
Danh mục bảng biểu
Bảng 3. 1 Đặc điểm các lược đồ thử nghiệm...................................................... 70
Bảng 3. 2 Kết quả đo chất lượng đối sánh ......................................................... 71
Danh mục hình vẽ
Hình 2. 1 Ví dụ về đồ thị lược đồ ........................................................................ 36
Hình 3. 1 Tiến trình tính toán độ tương đồng phần tử ..................................... 49
Hình 3. 2 Ngữ cảnh của một phần tử lược đồ.................................................... 57
Hình 3. 3 So sánh các đối sánh thực với các đối sánh suy diễn được .............. 70
Hình 3. 4 Biểu đồ so sánh kết quả thực thi ........................................................ 72
Hình 3. 5 Mô hình cho hệ thống chuyển đổi tự động tài liệu XML................. 79
Mở đầu
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
1
Mở đầu
1. Giới thiệu chung
Một vấn đề rất quan trọng trong các hệ thống xử lý thông tin là trao đổi
và sử dụng lại dữ liệu giữa các hệ thống có dữ liệu không đồng nhất. Tính
không đồng nhất của dữ liệu là do các tổ chức hoặc ứng dụng thường tạo ra
dữ liệu cho chính mình dựa trên các yêu cầu riêng biệt. Các yêu cầu này hầu
hết thường được đặc tả trong các mô hình dữ liệu trừu tượng, còn gọi là các
lược đồ (chẳng hạn như lược đồ quan hệ, lược đồ hướng đối tượng và gần đây
là lược đồ XML). Trong những năm gần đây, sự phát triển mạnh mẽ của các
nguồn dữ liệu Web với rất nhiều mô hình thông tin và cú pháp mã hóa khác
nhau đã dẫn đến nhu cầu ngày càng cấp thiết của việc phát triển các phương
pháp và công cụ hỗ trợ cho việc trao đổi và sử dụng lại dữ liệu, do vậy đã có
rất nhiều nghiên cứu quan tâm đến vấn đề này. Như ta biết, đối sánh lược đồ
là vấn đề trung tâm trong hầu hết các nghiên cứu đó. Bài toán đối sánh lược
đồ có thể được định nghĩa một cách phi hình thức như sau: [6], [11] “Cho hai
lược đồ S1 và S2 trên mô hình dữ liệu bất kỳ, có thể có thêm thông tin phụ trợ
và một ánh xạ khởi đầu, hãy tìm ánh xạ giữa các phần tử lược đồ thỏa mãn
yêu cầu người dùng”. Nói cách khác, đây là vấn đề tìm kiếm sự tương đồng
giữa các phần tử của S1 và S2 (hay là việc xác định các thành phần tương
đương nhau giữa hai lược đồ nguồn và đích đã cho) bằng cách khai thác các
thông tin tồn tại trong lược đồ, dữ liệu và các nguồn thông tin phụ trợ.
Mở đầu
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
2
Thực tế cho thấy, các thách thức gặp phải khi tìm kiếm giải pháp cho bài
toán đối sánh lược đồ là rất lớn. Thứ nhất, quá trình này cần đến sự phân tích
ngữ nghĩa trong các lược đồ đó, hay nói cách khác ta cần suy diễn được nhận
thức về lược đồ của người tạo ra nó. Tuy vậy, các lược đồ thường được thiết
kế bởi những con người khác nhau với những nhận thức khác nhau về thế giới
thực cho các mục đích khác nhau. Thứ hai, việc khai thác thông tin cho bài
toán đối sánh lược đồ gặp rất nhiều khó khăn vì ta phải khai thác một lượng
lớn thông tin hỗn tạp và không chắc chắn, ví dụ như tài liệu đặc tả lược đồ,
các nguồn dữ liệu của lược đồ… Từ các phân tích trên, có thể thấy rằng việc
đối sánh lược đồ bằng tay thường khá tốn kém và dễ gây lỗi. Điều đó cho thấy
việc phát triển các kỹ thuật nhằm tự động hóa một cách tối đa tiến trình đối
sánh lược đồ là rất quan trọng.
Hiện nay, XML (eXtended Markup Language - ngôn ngữ đánh dấu mở
rộng) [24] đã trở thành chuẩn ngôn ngữ hiệu quả và thích hợp cho việc biểu
diễn dữ liệu trên Web. Nhu cầu sử dụng XML như là chuẩn biểu diễn và trao
đổi dữ liệu ngày càng tăng của cộng đồng Web đã tạo nên một lượng dữ liệu
XML ngày càng lớn. Gắn liền với sự gia tăng đó, một lượng lớn các lược đồ
XML [25], [26], [27] đã được phát triển với rất nhiều đặc tả khác nhau, dẫn
đến một lượng lớn dữ liệu XML không đồng nhất. Thêm vào đó, hiện tại lại
có khá nhiều ngôn ngữ lược đồ khác nhau được đưa ra, dẫn đến sự không
đồng nhất về mặt cú pháp ở các ngôn ngữ lược đồ. Với sự phát triển nhanh
chóng và sự tăng trưởng mạnh mẽ về mặt quy mô của các ứng dụng Web, đặc
biệt là sự phổ dụng của Internet và công nghệ XML, đã có rất nhiều nghiên
cứu quan tâm đến vấn đề trao đổi và sử dụng lại dữ liệu XML. Vấn đề đối
sánh lược đồ XML do vậy ngày càng trở nên quan trọng. Nhằm góp phần tìm
hiểu và giải quyết vấn đề đó một cách hiệu quả hơn, luận văn này sẽ tổng hợp
lại cũng như đưa ra các đóng góp thêm cho bài toán đối sánh lược đồ XML.
Mở đầu
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
3
2. Nội dung luận văn
Luận văn này nghiên cứu vấn đề đối sánh tự động lược đồ XML. Luận
văn bao gồm ba chương. Chương 1 mô tả tổng quan về vấn đề đối sánh lược
đồ. Chương 2 đưa ra các định nghĩa hình thức cho vấn đề đối sánh lược đồ
XML. Chương 3 mô tả giải pháp đối sánh tự động lược đồ XML. Cũng trong
chương 3, chúng tôi sẽ xem xét vấn đề chuyển đổi tự động tài liệu XML. Cuối
cùng, phần kết luận nêu lên những đóng góp chính và các hướng phát triển.
Sau đây là những nội dung chính của luận văn:
Chương 1: Đối sánh lược đồ. Chương này bao gồm ba nội dung chính:
- Trình bày các khái niệm, định nghĩa cơ bản về vấn đề đối sánh lược đồ
và các lĩnh vực ứng dụng chính của đối sánh lược đồ như tích hợp lược đồ,
tích hợp dữ liệu, kho dữ liệu, chuyển đổi (hay dịch, trao đổi) dữ liệu, quản lý
dữ liệu ngang hàng, thương mại điện tử, đối sánh và tích hợp ontology, Web
ngữ nghĩa, xử lý truy vấn ngữ nghĩa, v.v..
- Trình bày các tiếp cận đối sánh lược đồ điển hình. Phần này chúng tôi
sẽ xem xét các tiếp cận điển hình như tiếp cận dựa trên học máy, dựa trên
luật, dựa trên siêu dữ liệu cũng như một số tiếp cận khác. Tiếp theo chúng tôi
sẽ xem xét các phương pháp đối sánh điển hình như đối sánh ngôn ngữ, đối
sánh dựa trên ràng buộc, đối sánh cấu trúc và một số phương pháp khác.
Chúng tôi cũng sẽ phân tích những điểm mạnh cũng như những hạn chế của
các giải pháp này, từ đó lựa chọn giải pháp cho tiếp cận của chúng tôi.
- Mô tả một số hệ thống đối sánh lược đồ cũng như phân tích các đặc
điểm cơ bản nhất của các hệ thống đó. Thông qua các hệ thống này, đặc biệt
là hai hệ thống Cupid [11] và Similarity Flooding [12], chúng tôi sẽ phân tích
các giới hạn của các thuật toán đối sánh lược đồ hiện tại, từ đó lựa chọn các
thuật toán đối sánh sẽ sử dụng trong tiếp cận của chúng tôi.
Mở đầu
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
4
Chương 2: Các định nghĩa hình thức. Chương này bao gồm ba nội dung
chính:
- Trình bày các định nghĩa hình thức cho vấn đề đối sánh lược đồ, tập
trung vào lược đồ XML. Các giải pháp hiện hành nhìn chung không quan tâm
nhiều đến việc đưa ra các định nghĩa hình thức đầy đủ cho vấn đề. Trong
chương này, chúng tôi cũng sẽ mô tả các giả thiết cơ bản cho vấn đề đối sánh
lược đồ XML.
- Trình bày giải pháp mô hình hóa lược đồ XML dựa trên đồ thị gán nhãn
có hướng với các ràng buộc. Các nút của đồ thị biểu diễn các phần tử và các
thuộc tính của lược đồ XML trong khi các cạnh của đồ thị biểu diễn các quan
hệ khác nhau giữa các phần tử.
- Mô tả đại số ánh xạ nguồn–đích áp dụng cho vấn đề chuyển đổi dữ liệu.
Đại số ánh xạ nguồn–đích là một mở rộng của đại số quan hệ chuẩn. Trong
luận văn này chúng tôi sẽ xem xét tập các phép toán bao gồm hợp, chọn,
nhập, tách, nối, áp dụng và đổi tên.
Chương 3: Đối sánh tự động lược đồ XML.
Chương này mô tả giải pháp đối sánh tự động lược đồ XML, đánh giá
giải pháp và mô tả một ứng dụng điển hình cho đối sánh lược đồ, vấn đề
chuyển đổi tự động tài liệu XML. Chương này bao gồm các nội dung chính
sau:
- Mô tả tiến trình tính toán độ tương đồng phần tử theo ba pha:
+ Đo độ tương đồng ngôn ngữ: sử dụng thuật toán của Hirst và St-
Onge để tính toán khoảng cách ngữ nghĩa dựa trên WordNet [7]. Thuật toán
này được thay đổi để đưa ra hệ số tương đồng cũng như các quan hệ ngữ
nghĩa (tương đương, rộng hơn, hẹp hơn, v.v..).
+ Xét tính tương thích kiểu dữ liệu: dựa trên việc phân tích các kiểu dữ
liệu lược đồ XML để suy ra hệ số tương thích kiểu dữ liệu. Với nút nguyên tố
(tức nút lá) chúng tôi sử dụng phân cấp kiểu lược đồ XML [27], còn với nút
Mở đầu
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
5
trung gian chúng tôi sử dụng các tính năng như thừa kế kiểu, nhóm thay thế
và kiểu trừu tượng để tìm kiếm các ánh xạ phức hợp.
+ Đo độ tương đồng cấu trúc: khác với các thuật toán đối sánh cấu trúc
hiện hành, chúng tôi nhấn mạnh vào khái niệm ngữ cảnh của phần tử. Ngữ
cảnh của một phần tử là sự kết hợp ngữ cảnh tổ tiên, ngữ cảnh con và ngữ
cảnh lá của nó. Để so sánh các ngữ cảnh này, chúng tôi so sánh các đường
dẫn dựa trên các ý tưởng về trả lời truy vấn đường dẫn.
- Đưa ra các ánh xạ trực tiếp cũng như phức hợp giữa các phần tử lược
đồ (với các phép toán chuyển đổi và điều kiện chuyển đổi tương ứng) từ độ
tương đồng phần tử đã tính toán.
- Đánh giá giải pháp đối sánh lược đồ XML đã đưa ra sử dụng các phép
đo chất lượng được đã được định nghĩa trong [5].
Cũng trong chương này, chúng tôi sẽ xem xét một trong những ứng dụng
điển hình của đối sánh lược đồ, vấn đề chuyển đổi tài liệu có cấu trúc. Đầu
tiên chúng tôi mô tả tổng quan về tài liệu có cấu trúc, tiếp theo chúng tôi trình
bày vấn đề chuyển đổi tự động tài liệu có cấu trúc và cuối cùng chúng tôi đưa
ra một mô hình cho hệ thống chuyển đổi tự động tài liệu XML. Trong tương
lai chúng tôi có ý định áp dụng giải pháp đối sánh lược đồ nêu trên vào mô
hình này.
Kết luận và các hướng phát triển.
Trong phần này, chúng tôi sẽ nêu lên các đóng góp chính của luận văn và
đưa ra một số định hướng phát triển trong tương lai cho đề tài.
Chương 1: Đối sánh lược đồ
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
6
Chương 1
Đối sánh lược đồ
Trong chương này chúng tôi tổng hợp lại các kết quả nghiên cứu điển
hình về vấn đề đối sánh lược đồ. Trước hết chúng tôi trình bày các khái niệm
cơ bản cũng như các lĩnh vực ứng dụng điển hình của đối sánh lược đồ. Như
ta sẽ thấy, các lĩnh vực này là rất phong phú, cho thấy tầm quan trọng của
bài toán đối sánh lược đồ. Tiếp theo chúng tôi mô tả các tiếp cận đối sánh cơ
bản và các phương pháp đối sánh thông dụng hiện nay. Dựa trên các khảo
sát về đối sánh lược đồ cũng như một số nghiên cứu gần đây, chúng tôi tiến
hành phân tích và so sánh các tiếp cận này. Như ta sẽ thấy, các giải pháp đối
sánh thường kết hợp nhiều phương pháp khác nhau để tăng tính hiệu quả cho
tiến trình đối sánh.
Trong chương này chúng tôi cũng mô tả một số hệ thống đối sánh lược
đồ điển hình đã được thực hiện, đánh giá và so sánh các thuật toán được sử
dụng trong các hệ thống này. Từ các đánh giá đó chúng tôi nêu ra các hạn
chế cơ bản của các thuật toán này, đặc biệt là trong vấn đề chuyển đổi dữ
liệu. Cuối cùng, trên cơ sở các phân tích trên, chúng tôi sẽ chứng tỏ rằng các
thuật toán đối sánh lược đồ hiện tại cần được phát triển và hoàn thiện thêm
nhằm giải quyết vấn đề tự động hóa tiến trình đối sánh lược đồ một cách có
hiệu quả nhất.
Chương 1: Đối sánh lược đồ
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
7
1.1 Tổng quan về đối sánh lược đồ
1.1.1 Các khái niệm cơ bản về đối sánh lược đồ
Đối sánh lược đồ là quá trình thao tác trên các lược đồ với đầu vào là hai
lược đồ không đồng nhất và có thể có thêm thông tin phụ, trả về một tập các
ánh xạ cho biết sự liên quan ngữ nghĩa giữa các phần tử lược đồ [17]. Trong
thực tế, đối sánh lược đồ thường được thực hiện bằng tay với sự hỗ trợ của
các công cụ đồ họa. Quá trình này thường tốn thời gian và dễ gây lỗi, bởi vậy
đã có nhiều nghiên cứu được tiến hành nhằm tự động hóa tiến trình đối sánh
lược đồ. Tuy nhiên đây là một vấn đề khó và phức tạp do một số lý do cơ bản
sau: [21]
- Các phần tử lược đồ được đối sánh trên cơ sở ngữ nghĩa của chúng.
Ngữ nghĩa có thể được thể hiện từ một số nguồn thông tin như người thiết kế,
tài liệu, lược đồ và thể hiện dữ liệu. Thực tế cho thấy người thiết kế rất khó để
nhớ được tất cả chi tiết lược đồ và tài liệu hiện có thì thường không chính xác,
không được cập nhật và không thể truy cập. Do đó tiến trình đối sánh lược đồ
thường dựa hoàn toàn trên các dấu hiệu trong lược đồ và thể hiện dữ liệu.
- Các lược đồ đã phát triển cho các ứng dụng khác nhau thì thường
không đồng nhất, tức là mặc dù dữ liệu chúng mô tả là tương đồng về ngữ
nghĩa nhưng cấu trúc và cú pháp sử dụng lại có thể khác nhau đáng kể.
- Để giải quyết các xung đột ngữ nghĩa và lược đồ, đối sánh lược đồ
thường dựa trên tên phần tử, kiểu dữ liệu phần tử, các định nghĩa cấu trúc, các
ràng buộc toàn vẹn và các giá trị dữ liệu. Tuy vậy, các dấu hiệu này thường
không chắc chắn và không đầy đủ. Ví dụ các nhãn giống nhau có thể được sử
dụng cho các phần tử lược đồ có ý nghĩa hoàn toàn khác nhau. Ngược lại, hai
phần tử với các nhãn khác nhau có thể tham chiếu tới cùng một thực thể thực
tế. Kiểu dữ liệu cũng thường không chính xác (ví dụ sử dụng kiểu "string"
Chương 1: Đối sánh lược đồ
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
8
thay vì "date") và các ràng buộc thường là không đầy đủ. Trong điều kiện
này, vấn đề chính sẽ không chỉ là việc phải xác định được các quan hệ đang
tồn tại giữa các phần tử lược đồ mà còn phải chắc chắn rằng tiến trình đối
sánh sẽ không đưa ra các ánh xạ không chính xác.
- Ánh xạ đơn giản nhất là ánh xạ một-một, nối kết một phần tử lược đồ
nguồn trực tiếp tới một phần tử lược đồ đích. Tuy vậy trong thực tế, một phần
tử trong lược đồ này có thể tương ứng với nhiều phần tử trong lược đồ khác
bằng cách áp dụng một hoặc một vài phép toán (ví dụ phần tử đích “Name”
tương ứng với ghép nối của hai phần tử nguồn “firstName” và “lastName”) và
thậm chí nhiều phần tử trong lược đồ này cũng có thể tương ứng với nhiều
phần tử trong một lược đồ khác. Loại ánh xạ này được gọi là phức hợp hay
gián tiếp và thường không thể suy ra được ngay từ lược đồ và các thể hiện mà
thường đòi hỏi sự can thiệp của người dùng. Việc khám phá ánh xạ phức hợp
là một vấn đề khó và phức tạp bởi vì quá trình đối sánh không chỉ cần tìm
kiếm các ánh xạ này mà còn phải nhận biết các phép toán cần đến chẳng hạn
như ghép nối hai phần tử, hợp nhất hoặc phân chia các giá trị dữ liệu, v.v..
- Hiển nhiên quá trình đối sánh lược đồ không thể thực hiện tự động
được hoàn toàn, do vậy nó đòi hỏi phải có sự can thiệp của người dùng. Từ đó
có thể thấy một điều quan trọng là quá trình đối sánh không chỉ cần tự động
đến mức có thể mà còn phải nhận biết được khi nào đầu vào người dùng là
cần thiết và đầu vào đó phải được khai thác một cách hiệu quả nhất.
1.1.2 Các lĩnh vực ứng dụng đối sánh lược đồ
Đối sánh lược đồ là bước then chốt trong những ứng dụng mà dữ liệu
chúng xử lý được cấu trúc hóa dưới các mô hình đã chỉ ra (chẳng hạn như
lược đồ quan hệ, lược đồ hướng đối tượng, DTD, lược đồ XML, v.v..) hoặc
những ứng dụng mà các lược đồ chúng khai thác là không đồng nhất. Đối
Chương 1: Đối sánh lược đồ
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
9
sánh lược đồ cho phép thao tác trên các lược đồ, dịch dữ liệu và trả lời truy
vấn qua các lược đồ không đồng nhất. Nhiều ứng dụng khác nhau dựa trên đối
sánh lược đồ đã xuất hiện và đã được nghiên cứu rộng rãi trong các lĩnh vực
cơ sở dữ liệu (CSDL) và trí tuệ nhân tạo (TTNT) [17], chẳng hạn như tích
hợp lược đồ, tích hợp dữ liệu, kho dữ liệu, chuyển đổi (hay dịch, trao đổi) dữ
liệu, quản lý dữ liệu ngang hàng, thương mại điện tử, đối sánh và tích hợp
ontology, Web ngữ nghĩa, xử lý truy vấn ngữ nghĩa, v.v.. Sau đây chúng tôi sẽ
xem xét tổng quan các vấn đề chính trong các lĩnh vực này.
1.1.2.1 Tích hợp lược đồ
Hầu hết các nghiên cứu về đối sánh lược đồ ban đầu là nhằm giải quyết
vấn đề tích hợp lược đồ, là vấn đề hợp nhất các lược đồ tự trị và không đồng
nhất thành một lược đồ tổng thể, gọi là lược đồ trung gian. Vấn đề tích hợp
lược đồ là một mối quan tâm chính trong hai thập kỷ qua trong lĩnh vực
CSDL [17]. Do các lược đồ là tự trị và được phát triển độc lập, chúng thường
biểu diễn không đồng nhất các ngôn ngữ và cấu trúc khác nhau. Quá trình tích
hợp đòi hỏi nhận dạng được các phụ thuộc liên lược đồ. Đây là một quá trình
đối sánh lược đồ. Một khi chúng đã được nhận dạng, các phần tử đối sánh
được hợp nhất dưới một lược đồ trung gian cố kết.
1.1.2.2 Tích hợp dữ liệu
Các hệ thống tích hợp dữ liệu có mục đích cung cấp cho người dùng một
giao diện truy vấn đồng bộ cho rất nhiều nguồn dữ liệu. Hai thành phần chính
tạo thành kiến trúc của một hệ thống tích hợp dữ liệu: trình bao bọc và trình
môi giới. Trình bao bọc bọc một nguồn thông tin và mô hình hóa nguồn thông
tin đó sử dụng một lược đồ nguồn. Trình môi giới duy trì một lược đồ tổng thể
và các ánh xạ giữa lược đồ tổng thể và các lược đồ nguồn. Mỗi khi người
dùng đưa ra một truy vấn trên lược đồ tổng thể, trình môi giới sử dụng các
ánh xạ này để công thức hóa lại một truy vấn tổng thể thành một tập các truy
Chương 1: Đối sánh lược đồ
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
10
vấn con mà có thể thi hành trong các lược đồ nguồn và như vậy trình môi giới
có thể tập hợp các trả lời được trả lại từ các nguồn và kết hợp chúng thành trả
lời cho truy vấn [21].
Như vậy một vấn đề then chốt trong việc xây dựng hệ thống tích hợp dữ
liệu là việc cung cấp chính xác các ánh xạ giữa các lược đồ tổng thể và nguồn.
Hiện nay, có hai giải pháp chính cho việc cung cấp các ánh xạ này: khung
nhìn tổng thể và khung nhìn cục bộ. Trong tiếp cận đầu, lược đồ trung gian
được định nghĩa dưới dạng các lược đồ của các nguồn. Còn trong tiếp cận
sau, các mô tả của nguồn được cho theo hướng ngược lại. Thuận lợi chính của
tiếp cận đầu là việc công thức hóa lại truy vấn là đơn giản. Tuy vậy, việc thêm
các nguồn vào lược đồ trung gian lại không phải là việc tầm thường. Ngược
lại, trong tiếp cận sau, việc công thức hóa lại truy vấn khó hơn nhưng việc
thêm vào các nguồn mới thì khá đơn giản. Từ đó một số nghiên cứu đã đề
xuất giải pháp kết hợp hai tiếp cận trên để tích hợp các nguồn dữ liệu không
đồng nhất [20].
1.1.2.3 Kho dữ liệu
Một biến thể của vấn đề tích hợp dữ liệu là tập hợp các nguồn dữ liệu
tích hợp vào một kho tập trung, gọi là kho dữ liệu. Quá trình này đòi hỏi phải
chuyển đổi dữ liệu từ định dạng nguồn thành định dạng kho dữ liệu, do đó có
thể sử dụng đối sánh lược đồ để thực hiện các chuyển đổi này. Với một nguồn
dữ liệu đã cho, một phương pháp thích hợp để tạo các chuyển đổi là tìm kiếm
các phần tử của nguồn mà có mặt trong kho dữ liệu. Thuận lợi chính của kho
dữ liệu là hiệu quả cao trong trả lời truy vấn (bởi vì các truy vấn được áp dụng
trực tiếp tới dữ liệu trong kho). Tuy vậy, nó đòi hỏi kho phải được cập nhật
khi dữ liệu thay đổi, điều này không thích hợp khi điều quản một số lượng lớn
nguồn hoặc khi nguồn thường xuyên thay đổi. Hiện nay một khung làm việc
Chương 1: Đối sánh lược đồ
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
11
hỗ trợ cho các khung nhìn tích hợp mà kết hợp các tiếp cận kho dữ liệu và
kho ảo đã được đề xuất [17].
1.1.2.4 Chuyển đổi dữ liệu
Trong vài năm gần đây, sự phát triển nhanh chóng của thông tin trực
tuyến trong các nguồn không đồng nhất phân biệt lưu trữ dưới các định dạng
khác nhau đã dẫn đến một ứng dụng khác đòi hỏi việc đối sánh lược đồ: trao
đổi dữ liệu. Trao đổi dữ liệu mà thường được gọi là dịch hay chuyển đổi dữ
liệu là vấn đề dịch nội dung của nguồn dữ liệu thành thể hiện của một lược đồ
đích mà phản ánh dữ liệu nguồn chính xác đến mức có thể.
Tuy vấn đề trao đổi dữ liệu có một số điểm tương đồng với vấn đề tích
hợp dữ liệu, vẫn có một số khác biệt quan trọng giữa hai vấn đề này. Trong
kịch bản chuyển đổi dữ liệu, lược đồ đích nhìn chung được tạo ra độc lập và
có các ràng buộc của bản thân nó. Còn trong tích hợp dữ liệu lược đồ tổng thể
là một lược đồ ảo và có tính hòa hợp, không có các ràng buộc định nghĩa
trước. Một khác biệt quan trọng nữa là trong trao đổi dữ liệu ta phải tạo ra
một thể hiện đích mà phản ánh tốt nhất thể hiện nguồn đã cho. Trong tích hợp
dữ liệu không có sự trao đổi nào về dữ liệu được yêu cầu. Việc tự động hóa
quá trình dịch dữ liệu đòi hỏi sử dụng đối sánh lược đồ để phát hiện sự tương
đồng giữa lược đồ nguồn và đích, đây là một bước then chốt để đưa ra một
chương trình dịch thích hợp [17].
1.1.2.5 Thương mại điện tử
Với sự phổ biến của Internet hiện nay, các công ty kinh doanh ngày càng
phải quản lý nhiều giao dịch trực tuyến như trao đổi thông tin, đặt hàng, xác
nhận và thanh toán... Các giao dịch này là quá trình trao đổi các tài liệu hay
thông điệp giữa các công ty. Tuy vậy các công ty thường phát triển ứng dụng
với các định dạng thông điệp khác nhau như EDI (Electronic Data Exchange),
Chương 1: Đối sánh lược đồ
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
12
XML (Extended Markup Language) hoặc một số định dạng khác. Để trao đổi
các thông điệp đó, các ứng dụng cần phải chuyển đổi được các thông điệp từ
định dạng này sang định dạng khác. Như đã nói ở trên, đây chính là vấn đề
chuyển đổi dữ liệu [17].
1.1.2.6 Quản lý dữ liệu ngang hàng
Một ứng dụng quan trọng của đối sánh lược đồ là quản lý dữ liệu ngang
hàng, là một mở rộng tự nhiên của tích hợp dữ liệu. Ngược lại với môi trường
tích hợp dữ liệu, một quản lý dữ liệu ngang hàng không dựa trên khái niệm
lược đồ trung gian mà cho phép một số tùy ý các điểm truy vấn và lấy dữ liệu
trực tiếp từ mỗi điểm khác. Việc xử lý thông tin và lấy nội dung giữa vô số
các điểm tự trị đòi hỏi các kỹ thuật đối sánh thích hợp để xác định các ánh xạ
giữa các khái niệm của các điểm khác nhau mà có liên quan về ngữ nghĩa
[17].
1.1.2.7 Đối sánh và tích hợp ontology
Ontology được định nghĩa như là việc khái niệm hóa một lĩnh vực dưới
dạng các khái niệm và quan hệ. Hiện nay ontology được thừa nhận là một
công cụ cơ bản cho phép chia sẻ tri thức giữa các ứng dụng phân tán và không
đồng nhất. Nhiều nghiên cứu xoay quanh ontology đã được thực hiện, từ thiết
kế đến phát triển và sử dụng lại. Đối sánh ontology là một trong những bước
cơ bản của hầu hết các ứng dụng dựa trên ontology, trong đó có vấn đề tích
hợp ontology. [6].
1.1.2.8 Web ngữ nghĩa
Một trong những vấn đề đang được quan tâm nhiều hiện nay là Web ngữ
nghĩa, tức là vấn đề sử dụng một số ontology lĩnh vực nhằm mô tả ý nghĩa của
dữ liệu trên Web. Sự phát triển nhanh chóng của Internet với lượng thông tin
khổng lồ khiến ta rất khó khai thác và sử dụng hiệu quả các nguồn thông tin
Chương 1: Đối sánh lược đồ
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
13
đó, bởi vì các thông tin trên Web hiện nay được thiết kế chủ yếu cho con
người sử dụng chứ không phải máy tính. Mục đích của Web ngữ nghĩa là làm
giàu các tài liệu Web hiện nay bằng các mô tả ngữ nghĩa nhằm làm cho máy
tính có thể hiểu được. Phương pháp làm giàu các tài liệu Web hiện nay là sử
dụng ontology. Tuy vậy các Website khác nhau lại thường sử dụng ontology
khác nhau, bởi vậy để làm cho Web có khả năng liên tác được, ta cần các kỹ
thuật đối sánh thích hợp giữa các ontology tự trị để xác định các ánh xạ ngữ
nghĩa giữa các khái niệm ontology khác nhau mà có liên quan về ngữ nghĩa
[6].
1.1.2.9 Xử lý truy vấn ngữ nghĩa
Tích hợp dữ liệu, kho dữ liệu, và chuyển đổi dữ liệu nhìn chung là các
vấn đề tương tự nhau bởi vì chúng đều phải phân tích các lược đồ để đưa ra
các ánh xạ (và có thể một lược đồ tích hợp) – ta gọi đây là việc phân tích tại
thời điểm thiết kế. Một vấn đề khác hơn đôi chút là xử lý truy vấn ngữ nghĩa -
một vấn đề tại thời điểm thực thi ở đó người dùng sẽ chỉ rõ đầu ra của một
truy vấn và hệ thống sẽ tính toán xem làm thế nào để đưa ra đầu ra đó. Đặc tả
của người dùng được phát biểu dưới dạng các khái niệm quen thuộc với họ
mà có thể không giống như tên các phần tử được chỉ ra trong lược đồ CSDL.
Bởi vậy, trong pha đầu tiên của việc xử lý truy vấn, hệ thống phải ánh xạ các
khái niệm người dùng yêu cầu trong đầu ra truy vấn tới các phần tử lược đồ.
Đây cũng là một ứng dụng tự nhiên của phép toán đối sánh.
Sau khi ánh xạ đầu ra truy vấn tới các phần tử lược đồ, hệ thống phải
nhận được một phát biểu cho biết ngữ nghĩa của ánh xạ. Đã có nhiều kỹ thuật
được phát triển trong nhiều thập kỷ qua nhằm thu nhận các phát biểu này.
Một trong những hướng nghiên cứu hiện nay là tổng quát hóa các kỹ thuật
này để chỉ ra ngữ nghĩa của một ánh xạ đưa ra bởi phép toán đối sánh tìm
được [17].
Chương 1: Đối sánh lược đồ
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
14
1.2 Các tiếp cận đối sánh lược đồ
1.2.1 Phân loại các tiếp cận đối sánh lược đồ
Đối sánh lược đồ là một vấn đề mới mẻ và thường được nghiên cứu riêng
lẻ trên nhiều lĩnh vực khác nhau, do vậy đã có nhiều khảo sát được đưa ra
nhằm phân loại các tiếp cận này. Đáng chú ý hơn cả là khảo sát của Rahm &
Bernstein [17], trong đó các tác giả phân biệt các phương pháp đối sánh dựa
trên phương pháp tiếp cận mà chúng sử dụng như sau:
* Tiếp cận dựa trên lược đồ >< Tiếp cận dựa trên thể hiện: Tiếp cận dựa
trên lược đồ chỉ sử dụng các thông tin chứa trong lược đồ như tên, kiểu... Còn
tiếp cận dựa trên dữ liệu chỉ sử dụng nội dung dữ liệu.
* Tiếp cận dựa trên phần tử >< Tiếp cận dựa trên cấu trúc: quá trình đối
sánh có thể thực hiện cho từng phần tử (như các thuộc tính) hoặc kết hợp các
phần tử với nhau trong 1 cấu trúc.
* Tiếp cận dựa trên ngôn ngữ >< Tiếp cận dựa trên ràng buộc: đối sánh
có thể sử dụng cách tiếp cận dựa trên ngôn ngữ như so sánh tên các phần tử,
các thông tin mô tả phần tử hoặc sử dụng cách tiếp cận dựa trên ràng buộc
như ràng buộc như kiểu dữ liệu, ràng buộc đơn nhất, khóa, v.v..
* Tiếp cận lai >< Tiếp cận kết hợp: Để có một kết quả đối sánh tốt hơn
ta thường kết hợp các tiếp cận độc lập với nhau. Các cách tiếp cận này có thể
được thực hiện trong một bộ đối sánh lai hoặc kết hợp các kết quả đối sánh
của các tiếp cận độc lập khác nhau.
* Số yếu tố đối sánh: kết quả đối sánh có thể là một hay nhiều phần tử
của lược đồ nguồn đối sánh với một hay nhiều phần tử của lược đồ đích. Có
bốn trường hợp cơ bản, bao gồm đối sánh 1:1, 1:n, n:1 và n:m. Ngoài ra một
phần tử của lược đồ này cũng có thể liên quan đến nhiều phần tử của lược đồ
kia, khi đó có thể cần đến các phép toán hợp nhất hoặc phân tách.
Chương 1: Đối sánh lược đồ
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
15
* Thông tin trợ giúp: các tiếp cận đối sánh thường sử dụng nhiều nguồn
thông tin trợ giúp khác nhau như từ điển, lược đồ tổng thể, các kết quả đối
sánh sẵn có từ trước hay đầu vào người dùng.
1.2.2 Các tiếp cận đối sánh lược đồ
Các tiếp cận đối sánh lược đồ đã được phát triển chủ yếu trong các
nghiên cứu về CSDL và TTNT. Trong mục này chúng tôi sẽ tổng kết lại, mô
tả và so sánh các tính năng đặc trưng của các tiếp cận này.
1.2.2.1 Tiếp cận dựa trên học máy
Học máy là khả năng khai thác các kết quả nhận được trước đó của một
máy để cải thiện hiệu năng của nó, đặc biệt là để tự động hóa các quá trình đắt
tiền và tốn thời gian. Nhiều nghiên cứu gần đây trong các lĩnh vực CSDL và
TTNT đã tận dụng các kỹ thuật học máy để thực hiện đối sánh lược đồ [21],
[6]. Các công cụ đối sánh lược đồ dựa trên học máy thông thường bao gồm
một số các môđun, gọi là người học bao gồm một môđun riêng và siêu người
học để kết hợp chúng. Mỗi người học khai thác một loại thông tin khác nhau
có trong các định nghĩa cấu trúc và/hoặc trong các nguồn dữ liệu. Một khi
người học đã được đào tạo, công cụ đối sánh có thể tìm kiếm các ánh xạ cho
một nguồn dữ liệu mới bằng cách áp dụng các người học và sau đó kết hợp
các kết quả của chúng bằng cách sử dụng một siêu người học. Ví dụ hệ thống
LSD [6] áp dụng một chiến lược siêu học để tạo nên một số đối sánh cơ sở mà
có xem xét đến các thể hiện dữ liệu hoặc thông tin lược đồ. Ngoài ra còn một
số hệ thống khác như được nêu trong mục 1.3.
1.2.2.2 Tiếp cận dựa trên luật
Phần lớn các công cụ đối sánh lược đồ hiện tại đều sử dụng luật để đối
sánh các lược đồ không đồng nhất. Đã có nhiều nghiên cứu về vấn đề này cả
trong lĩnh vực CSDL và TTNT [6], [17], [21]. Các tiếp cận dựa trên luật khai
Chương 1: Đối sánh lược đồ
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
16
thác nhiều loại thông tin lược đồ như tên phần tử, kiểu dữ liệu, các ràng buộc
phần tử và phân cấp cấu trúc. Hệ thống Cupid [11] và Similarity Flooding
[12] sử dụng các luật tính toán độ tương đồng giữa hai lược đồ như là tổng có
trọng số của các độ tương đồng tên phần tử, kiểu dữ liệu và vị trí cấu trúc.
1.2.2.3 Tiếp cận dựa trên siêu dữ liệu
Một tiếp cận khác cho vấn đề đối sánh lược đồ là tiếp cận dựa trên siêu
dữ liệu. Các tiếp cận dựa trên siêu dữ liệu khai thác thêm thông tin ngữ nghĩa
được cung cấp chung bởi các chuyên gia lĩnh vực, ví dụ như siêu dữ liệu RDF
hoặc các ontology lĩnh vực. Nhìn chung tiếp cận này cố gắng ánh xạ tự động
tất cả các trường của mỗi nguồn dữ liệu (hoặc lược đồ) để định nghĩa trước
ontology lĩnh vực và sau đó thực hiện đối sánh lược đồ ở mức ontology. Như
vậy tiếp cận này thực chất là giải pháp chuyển vấn đề ánh xạ các nguồn dữ
liệu và các lược đồ thành việc ánh xạ các ontology.
1.2.2.4 Một số tiếp cận khác
Ngoài việc sử dụng kỹ thuật học máy, một số tiếp cận còn sử dụng mạng
nơ-ron để đối sánh lược đồ [21]. Tiếp cận sử dụng mạng nơ-ron khai thác các
ưu điểm của mạng nơ-ron trong việc phát hiện sự tương đồng giữa các nguồn
dữ liệu. Lợi ích chính của mạng nơ-ron là thuật toán sử dụng trong pha đào
tạo không cần huấn luyện. Một số tiếp cận khác cũng đã được đề xuất cho vấn
đề đối sánh lược đồ, chẳng hạn tiếp cận hướng đối tượng [21]. Tiếp cận
hướng đối tượng dựa trên biểu diễn các lược đồ theo mô hình hướng đối
tượng, sau đó dịch các đặc tả lược đồ thành các biểu diễn hướng đối tượng
này. Tiếp cận này thường được sử dụng trong các hệ thống tích hợp dữ liệu.
1.2.2.5 So sánh các tiếp cận
Các tiếp cận trên cơ sở luật nhìn chung có giá thành không lớn và hiệu
năng cao do chúng không đòi hỏi phải có pha đào tạo và thường chỉ hoạt động
Chương 1: Đối sánh lược đồ
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
17
trên các lược đồ mà bỏ qua các thể hiện dữ liệu. Tiếp cận trên cơ sở luật thích
hợp trong việc thu thập dễ dàng tri thức người dùng về lĩnh vực. Tuy vậy các
tiếp cận trên cơ sở luật không thể khai thác thông tin về các thể hiện một cách
hiệu quả và gặp phải một số vấn đề với các phần tử lược đồ mà không tìm
thấy các luật hiệu quả; khi đó ta cần cung cấp các dấu hiệu cần thiết.
Các tiếp cận trên cơ sở học yêu cầu nhiều dữ liệu đào tạo và các ví dụ
đào tạo đúng. Hơn nữa các tiếp cận trên cơ sở học không thể làm việc chính
xác nếu không cung cấp một đối sánh ban đầu (mà thông thường được người
dùng cung cấp) và một tập tiêu biểu các nguồn dữ liệu, điều này giới hạn đáng
kể việc ứng dụng của các phương pháp này. Do các tiếp cận trên cơ sở học
dựa cơ bản trên các nguồn dữ liệu và trên các ánh xạ giữa các nút lá của hai
cây, chúng không khai thác được các cấu trúc phân cấp thực sự, là vấn đề căn
bản của dữ liệu có cấu trúc. Cuối cùng, nhiều tiếp cận trên cơ sở học chỉ sử
dụng một người học đơn, và do đó mức chính xác và khả năng ứng dụng bị
hạn chế [6], [21].
1.2.3 Các phương pháp đối sánh lược đồ
Dù sử dụng các tiếp cận trên cơ sở luật hay trên cơ sở học, tất cả các
công cụ đối sánh đều khai thác tên phần tử, kiểu dữ liệu, các ràng buộc và
định nghĩa cấu trúc. Trên cơ sở xem xét các dự án đã thực hiện và các khảo
sát về vấn đề đối sánh lược đồ [17] ta có thể phân chia các phương pháp đối
sánh lược đồ thành ba loại: đối sánh ngôn ngữ, đối sánh trên cơ sở ràng buộc
và đối sánh cấu trúc. Các công cụ đối sánh lược đồ thường kết hợp các
phương pháp này để thực hiện quá trình đối sánh.
1.2.3.1 Đối sánh ngôn ngữ
Đối sánh ngôn ngữ về cơ bản dựa trên tên các thành phần lược đồ để tìm
kiếm đối sánh giữa các lược đồ. Để làm việc, đối sánh ngôn ngữ thường yêu
Chương 1: Đối sánh lược đồ
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
18
cầu sử dụng tên mô tả. Sự tương đồng của tên được đo theo nhiều cách khác
nhau như đo sự bằng nhau của tên, sự bằng nhau của biểu diễn tên hợp quy
tắc sau khi phân luồng và các xử lý khác, sự tương đồng của tên dựa trên các
dãy con chung, khoảng cách soạn thảo…, hay còn gọi là so sánh cú pháp. Đối
sánh tên dựa trên cú pháp chỉ tính toán độ tương đồng dựa trên các xâu biểu
diễn tên. Nhiều thuật toán so sánh xâu đã được phát triển trong các lĩnh vực
khác nhau như sửa lỗi chính tả, thu thập văn bản, v.v.. Đối với vấn đề đối
sánh lược đồ, đã có nhiều thuật toán dạng này được áp dụng, chẳng hạn như
EditDistance, N-Gram, SoundEx, v.v.. EditDistance là phương pháp tính độ
tương đồng của hai xâu từ số lần thực hiện các thao tác xóa, thêm, thay thế ký
tự cần thiết để chuyển một xâu này thành xâu kia. N-Gram là phương pháp so
sánh xâu theo tập n-gram của nó, ví dụ xâu doc và document tương tự nhau
theo tập tri-gram vì tập {doc} và tập {doc,ocu,cum,ume,men,ent} chia sẻ
phần tử “doc”. Còn SoundEx là phương pháp tính độ tương đồng âm thanh
giữa các tên tương ứng với mã SoundEx. Phương pháp này tỏ ra khá hiệu quả
cho các từ được viết khác nhau nhưng có khả năng giống nhau, ví dụ
document và documentation. Sự tương đồng của tên cũng có thể được tính
toán dựa trên các quan hệ đồng nghĩa, trái nghĩa, tổng quát, bộ phận… giữa
các từ, hay còn gọi là so sánh ngữ nghĩa. Các quan hệ này thu được bằng cách
sử dụng từ điển nói chung và các từ điển chuyên ngành nói riêng.
Việc sử dụng phương pháp đối sánh ngôn ngữ có thể đưa đến những đối
sánh không chính xác về mặt ngữ nghĩa. Ví dụ hai phần tử cùng tên có thể
biểu diễn các khái niệm hoàn toàn khác nhau hoặc ngược lại, hai phần tử có
tên không giống nhau song lại có thể biểu diễn ngữ nghĩa tương đồng. Hơn
nữa đối sánh ngôn ngữ còn phải đối phó với các trường hợp đặc biệt như sử
dụng chữ viết tắt, chữ rút gọn (là từ gồm những chữ cái đầu của các từ), tên
có giới từ hay mạo từ, v.v.. Tuy còn tồn tại các vấn đề trên, đối sánh ngôn ngữ
Chương 1: Đối sánh lược đồ
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
19
lại khá dễ thực hiện và có thể cho một ánh xạ ban đầu, sau đó ta có thể xác
nhận hoặc hủy bỏ bằng các phương pháp đối sánh khác.
1.2.3.2 Đối sánh dựa trên ràng buộc
Các ràng buộc lược đồ (nếu chúng là các tập thích đáng) có thể cho một
dấu hiệu đáng quan tâm về cách đối sánh các phần tử lược đồ và do đó giảm
nhẹ số lượng các ứng viên đối sánh (thu được từ phương pháp đối sánh ngôn
ngữ). Các ràng buộc lược đồ bao gồm kiểu dữ liệu, phạm vi giá trị, các ràng
buộc đơn nhất và toàn vẹn, v.v.. Như ta biết, các khuyến nghị lược đồ thường
cung cấp một tập các kiểu dữ liệu nguyên gốc, do vậy việc phân tích các kiểu
dữ liệu này có thể cung cấp cho ta các ứng viên đối sánh. Một ví dụ về hệ
thống sử dụng tính tương thích kiểu dữ liệu là Cupid [11]. Việc so sánh phạm
vi giá trị số và/hoặc mẫu ký tự cũng có thể có ích trong việc suy ra các ứng
viên đối sánh này, ví dụ chúng có thể cho phép nhận biết số điện thoại, mã
bưu điện và địa chỉ. Vấn đề nảy sinh trong việc sử dụng kiểu dữ liệu là khi
chúng không đủ rõ ràng (ví dụ một trường đã được khai báo như một số
nguyên lại được khai báo như một xâu).
1.2.3.3 Đối sánh cấu trúc
Thông tin cấu trúc (đặc biệt là các cấu trúc phân cấp) là rất có ích trong
việc xem xét tính tương đồng về ngữ nghĩa của các phần tử lược đồ. Độ tương
đồng cấu trúc là một phép đo độ tương đồng của ngữ cảnh mà trong đó các
phần tử xuất hiện. Trong khi rất nhiều tài liệu, công trình nghiên cứu đề cập
đến đối sánh ngôn ngữ và đối sánh dựa trên ràng buộc và hầu hết đều áp dụng
được cho DTD và lược đồ XML, cho đến nay rất ít nghiên cứu quan tâm đến
cấu trúc của XML trong các phương pháp đối sánh lược đồ của chúng. Lí do
cơ bản là hầu hết các hệ thống đối sánh lược đồ được phát triển trong lĩnh vực
CSDL và do đó về cơ bản chỉ đối phó với các lược đồ quan hệ. Ngược lại với
dữ liệu XML, CSDL quan hệ có rất ít dữ liệu cấu trúc. Hầu hết công việc
Chương 1: Đối sánh lược đồ
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
20
trong đối sánh cấu trúc lược đồ quan hệ được thực hiện theo các khóa ngoại
để tìm kiếm quan hệ giữa các dữ liệu.
Một số dự án gần đây bắt đầu quan tâm đến cách khai thác cấu trúc XML
trong quá trình đối sánh. Hệ thống Xyleme [4] tính toán độ tương đồng cấu
trúc giữa hai phiên bản của cùng một tài liệu XML trên cơ sở các quan hệ tổ
tiên và con cháu giữa các nút. Xyleme là một công cụ phát hiện các thay đổi
phiên bản giữa các tài liệu XML, điều này nghĩa là các tài liệu nguồn và đích
có độ tương đồng cao, là một giả thiết không có giá trị lắm trong đối sánh
lược đồ.
1.3 Các hệ thống đối sánh lược đồ XML
Gần đây đã có nhiều tiếp cận khác nhau về vấn đề đối sánh lược đồ được
đưa ra trong các lĩnh vực ứng dụng khác nhau, chẳng hạn như chuyển đổi tự
động tài liệu có cấu trúc. Các tác giả trong [9] đề xuất một tiếp cận trực tiếp
cú pháp cho việc tự động hóa các chuyển đổi cấu trúc giữa hai văn phạm trên
cơ sở các bộ chuyển đổi phi trạng thái hữu hạn. Ý tưởng ở đây là tạo một
chuyển đổi bán tự động nếu người dùng định nghĩa một đối sánh giữa các
phần tử chứa văn bản tài liệu (tức là các lá). Tiếp cận này gặp phải một số hạn
chế: đầu tiên nó chỉ làm việc nếu hai văn phạm có phần chung, làm hạn chế
phạm vi của các chuyển đổi trong các chuyển đổi cục bộ. Hơn nữa, tiếp cận
này không có khả năng giải quyết tất cả sự không đồng nhất có thể xảy ra
giữa các tài liệu có cấu trúc, chẳng hạn một kiểu phần tử cấu trúc trong tài
liệu nguồn sẽ được chuyển đổi thành cùng kiểu phần tử trong tài liệu đích. Ví
dụ, một danh sách các nút thay thế trong tài liệu nguồn chỉ có thể được
chuyển đổi thành một danh sách bao gồm cùng số lượng các phần tử lặp lại.
Bên cạnh các nghiên cứu trong lĩnh vực tài liệu, các nghiên cứu trong
lĩnh vực CSDL và TTNT đã xem xét một cách rộng hơn vấn đề đối sánh lược
Chương 1: Đối sánh lược đồ
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
21
đồ trong nhiều lĩnh vực ứng dụng khác nhau. Với sự phát triển của XML,
nhiều thuật toán đối sánh đã xem xét cấu trúc phân cấp của XML. Sau đây
chúng tôi sẽ xem xét một số giải thuật và hệ thống đối sánh lược đồ điển hình.
1.3.1 Cupid (trung tâm nghiên cứu Microsoft)
Cupid là một bộ đối sánh lai kết hợp một vài phương pháp đối sánh [11].
Đây là một bộ đối sánh được phát triển với mục đích áp dụng cho các mô
hình dữ liệu tổng quát và đã được áp dụng cho các nguồn dữ liệu XML và
quan hệ. Tiến trình đối sánh có ba pha:
* Pha đầu tiên là đối sánh ngôn ngữ. Trước hết tên phần tử được phân
tích thành các token dựa trên các dấu phân tách và được mở rộng để nhận
dạng các chữ viết tắt (abbreviation) hoặc chữ rút gọn (acronym) sử dụng một
từ điển đồng nghĩa cho cả ngôn ngữ chung và các tham khảo riêng lĩnh vực.
Sau đó Cupid sẽ phân cụm các phần tử lược đồ thành các danh mục dựa trên
kiểu dữ liệu và nội dung ngôn ngữ để giảm bớt số lượng phép so sánh một-
một giữa các phần tử lược đồ (chỉ các phần tử thuộc về các danh mục giống
nhau trong hai lược đồ mới được xem xét). Tiếp theo Cupid tính toán một hệ
số tương đồng ngôn ngữ giữa các cặp tương thích về kiểu dữ liệu và nội dung
ngôn ngữ dựa trên việc đối sánh xâu con và một từ điển đồng nghĩa có các
quan hệ đồng nghĩa (synonymy) và bao nghĩa (hypernymy). Kết quả của pha
này là một bảng các hệ số tương đồng ngôn ngữ trong phạm vi [0, 1] giữa các
phần tử trong hai lược đồ.
* Pha thứ hai chuyển đổi các lược đồ nguyên thủy thành cây và sau đó
thực hiện đối sánh cấu trúc từ dưới lên. Giả thiết cơ bản trong pha đối sánh
cấu trúc của Cupid là nhiều nội dung thông tin được biểu diễn trong các lá và
các lá đó có ít sự thay đổi giữa các lược đồ và tiếp đó là cấu trúc trong. Các
phần tử trong hai cây đang được so sánh được duyệt theo thứ tự trước. Độ
tương đồng giữa các nút là dựa trên độ tương đồng ngôn ngữ và độ tương
Chương 1: Đối sánh lược đồ
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
22
đồng của các tập lá của chúng. Nếu độ tương đồng vượt qua một ngưỡng thì
độ tương đồng tập lá của chúng được tăng lên, với lý lẽ là các lá với các tổ
tiên tương đồng cao sẽ xuất hiện trong các ngữ cảnh tương đồng. Việc tính
toán độ tương đồng cấu trúc có một sự đệ quy lẫn nhau: hai phần tử là tương
đồng nếu các tập lá tương ứng của chúng là tương đồng, và sự tương đồng của
các lá lại bị tác động bởi độ tương đồng của các nút trung gian. Pha này kết
thúc bằng việc tính toán trung bình có trọng số của độ tương đồng ngôn ngữ
và cấu trúc.
* Pha thứ ba sẽ đưa ra ánh xạ cuối cùng giữa các phần tử lược đồ dựa
trên các hệ số thu được trong pha hai. Pha này phụ thuộc nhiều vào ứng dụng
nên không được nhấn mạnh trong thuật toán.
Cấu trúc lược đồ trong Cupid được sử dụng như là một ràng buộc đối
sánh, tức là cấu trúc của hai nút càng tương đồng thì hai nút càng tương đồng.
Do điều này, Cupid phải đối mặt với những vấn đề như các khái niệm tương
đương xuất hiện trong các cấu trúc khác nhau hoàn toàn hay các khái niệm
độc lập hoàn toàn lại thuộc vào các cấu trúc đồng dạng. Dù gặp phải các vấn
đề này, Cupid vẫn là thuật toán đối sánh đáng chú ý cho dữ liệu XML do đã
vượt ra ngoài biểu diễn cây cổ điển để điều quản các lược đồ XML (hay bất
kỳ đồ thị có gốc nào đó) với việc xem xét các kiểu chia sẻ và các ràng buộc
tham chiếu. Ý tưởng ở đây là dựa trên việc chuyển đổi đồ thị có gốc thành cây
và điều này là vì hai lý do: sử dụng lại thuật toán đối sánh cấu trúc cho cây và
đối phó với các ánh xạ phụ thuộc ngữ cảnh. Trong trường hợp các kiểu chia
sẻ, với mỗi phần tử Cupid thêm một nút cây lược đồ mà các nút kế tiếp nó là
các nút tương ứng với các phần tử có thể tiếp cận đến qua một số bất kỳ các
quan hệ IsTypeOf theo sau bởi một quan hệ chứa đơn. Cây cũng được tăng
cường thêm các nút nhằm mô hình hóa các ràng buộc tham chiếu, là các ràng
buộc mà được thể hiện như là các khung nhìn kết nối tiềm tàng. Với mỗi khóa
Chương 1: Đối sánh lược đồ
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
23
ngoại, một nút mới mà biểu diễn kết nối các phần tử participate (các bảng
trong các lược đồ quan hệ) được đưa ra. Tuy có các mở rộng này, Cupid vẫn
không khai thác các tính năng khác của lược đồ XML như nhóm thay thế,
kiểu trừu tượng, v.v.. điều mà có thể cho ta các dấu hiệu có ý nghĩa trong việc
giải quyết vấn đề đối sánh lược đồ XML.
1.3.2 Similarity Flooding (đại học Stanford và đại học Leipzig)
Trong [12], các tác giả đưa ra một thuật toán đối sánh cấu trúc gọi là
Similarity Flooding (SF). Thuật toán SF được thực thi như là một phần của
một công cụ thao tác lược đồ tổng quát mà hỗ trợ, ngoài bộ đối sánh SF cấu
trúc, một bộ đối sánh tên, các bộ chuyển đổi lược đồ và một số bộ lọc nhằm
lựa chọn các ứng viên đối sánh tốt nhất từ danh sách các cặp ánh xạ đã xếp
hạng được trả về từ thuật toán SF. Tiến trình đối sánh bắt đầu bằng cách
chuyển đổi hai lược đồ đầu vào thành biểu diễn đồ thị gán nhãn. Sau đó bộ
đối sánh tên được sử dụng để cung cấp một ánh xạ khởi đầu mà cung cấp cho
bộ đối sánh SF cấu trúc. Cuối cùng, một số bộ lọc được áp dụng để chọn ra
các ánh xạ thích đáng.
Đối sánh cấu trúc SF dựa trên ý tưởng sau: đầu tiên các lược đồ được đối
sánh sẽ được chuyển đổi thành các đồ thị gán nhãn có hướng; thứ hai việc
tính toán điểm cố định lặp lại được sử dụng để xác định các ứng viên đối sánh
giữa các nút của đồ thị lược đồ. Để tính toán độ tương đồng nút, SF dựa trên
trực giác rằng các nút của hai đồ thị phân biệt là tương đồng khi các nút gần
kề là tương đồng. Đầu tiên một đồ thị lan truyền tương đồng được xây dựng,
đó là một cấu trúc dữ liệu phụ trợ dẫn xuất từ hai lược đồ đang được đối sánh,
chẳng hạn là A và B. Để thu được đồ thị lan truyền tương đồng, một đồ thị
liên kết cặp được tính toán từ A và B. Mỗi phần tử trong đồ thị liên kết là một
phần tử, gọi là cặp ánh xạ, từ A×B. Hai cặp ánh xạ, ví dụ (a, b) và (a1, b1)
được kết nối dựa trên trực giác rằng nếu a và b là tương đồng, thì có thể con
Chương 1: Đối sánh lược đồ
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
24
cháu trực tiếp của chúng a1 và b1 cũng tương đồng. Đồ thị liên kết cặp đôi
được sử dụng để lan truyền độ tương đồng giữa các nút sử dụng một tiến trình
lặp lại, trong đó mọi sự lặp lại sự tương đồng của một cặp ánh xạ được gia
tăng bởi sự tương đồng của các láng giềng của nó. Tiến trình lặp sẽ hội tụ sau
một số lớn nhất các bước lặp xác định.
SF đã được áp dụng cho một số định dạng đầu vào khác nhau bao gồm
quan hệ, XML và RDF. Thuật toán chỉ làm việc với các đồ thị gán nhãn có
hướng. Điều đó làm giảm giá trị khi việc gán nhãn là đồng bộ hoặc không
trực tiếp. Một giả thiết quan trọng trong thuật toán là sự gần kề đó có đóng
góp vào việc truyền sự tương đồng. Do đó, thuật toán sẽ thực hiện không
được như mong đợi trong trường hợp thông tin gần kề không được duy trì.
Như trong hệ thống LSD, chỉ có thông tin cấu trúc được sử dụng là quan hệ
cha mẹ – con cái, các thuộc tính và các quan hệ tổ tiên – cháu chắt bị bỏ qua.
Hơn nữa, SF bỏ qua tất cả kiểu của các ràng buộc trong khi thực hiện đối sánh
cấu trúc. Các ràng buộc như các ràng buộc kiểu và toàn vẹn được sử dụng vào
cuối tiến trình để lọc các cặp ánh xạ với sự trợ giúp của người dùng.
1.3.3 LSD (đại học Washington)
Hệ thống LSD (Learning Source Description) [6] sử dụng các kỹ thuật
học máy để đối sánh một nguồn dữ liệu mới dựa vào một lược đồ tổng thể
định nghĩa trước đó. LSD dựa trên sự kết hợp một vài kết quả đối sánh nhận
được từ những người học độc lập. Những người học này được đào tạo trong
một pha tiền xử lý. Với một ánh xạ ban đầu (thường do người dùng cung cấp)
giữa một nguồn dữ liệu đã cho và lược đồ tổng thể, pha tiền xử lý phân tích
các thể hiện từ nguồn dữ liệu đó để đào tạo những người học khác nhau và
khám phá các mẫu thể hiện đặc trưng và các luật đối sánh. Các mẫu và luật
sau đó được sử dụng để đối sánh các nguồn dữ liệu mới với lược đồ tổng thể.
Tất cả những người học cơ sở (người học tên, người học nội dung, v.v..) đều
Chương 1: Đối sánh lược đồ
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
25
không thể điều quản được cấu trúc phân cấp của XML bởi vì chúng "trải
phẳng" tất cả cấu trúc trong mỗi thể hiện vào và chỉ sử dụng các từ trong thể
hiện như là các token. Để giải quyết vấn đề này, LSD đưa ra một người học
XML-riêng để giúp cải thiện các kết quả đối sánh của nó. Nó cũng tương tự
như người học Naive-Bayes bởi vì nó sử dụng tần số xuất hiện của từ để tìm
kiếm các đối sánh có thể, không chỉ xét tên phần tử như là các token mà còn
xét các cạnh giữa các phần tử, do đó thao tác trên hai kiểu token: token nút và
token cạnh. Mỗi nút không gốc trên cây lập thành một token nút và mỗi nút
với nút con của nó lập thành một token cạnh. Cho dù điều này giúp cải thiện
kết quả, tiếp cận này gặp phải một số giới hạn do nó không khai thác đầy đủ
cấu trúc XML. Ví dụ, không có sự phân biệt giữa các phần tử và các thuộc
tính (thuộc tính được xem như một phần của phần tử, bởi vậy chúng không
được xét đến nữa). Hơn nữa, chỉ có một quan hệ cấu trúc được xét đến trong
hệ thống LSD là quan hệ cha mẹ – con cái, không đủ để mô tả ngữ cảnh của
một phần tử, và giới hạn phạm vi của hệ thống trong các cấu trúc tương đồng
có cùng chiều sâu. Nhiều thông tin cấu trúc phải được đưa vào trương mục
như là quan hệ anh chị em, tổ tiên – con cháu, các ràng buộc toàn vẹn, v.v..
1.3.4 Clio (IBM Almaden và đại học Toronto)
Trong [13] các tác giả đưa ra công cụ Clio nhằm ánh xạ giữa các lược đồ
quan hệ và XML, trong đó một ánh xạ mức cao được dịch thành các truy vấn
chuyển đổi dữ liệu nguồn thành thành biểu diễn đích. Hệ thống Clio làm việc
theo hai pha. Trong pha đầu, một ánh xạ mức cao (một tập các tương ứng
thuộc tính-thuộc tính) được biến đổi thành một ánh xạ lôgic nắm giữ sự lựa
chọn thiết kế lược đồ (ví dụ cấu trúc phân cấp trong trường hợp các lược đồ
XML). Pha thứ hai dịch ánh xạ lôgic thành truy vấn có ý nghĩa mà đưa ra dữ
liệu thỏa mãn các ràng buộc và cấu trúc của lược đồ đích.
Chương 1: Đối sánh lược đồ
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
26
Ánh xạ mức cao có thể nhận được từ một bộ đối sánh ngôn ngữ so sánh
tên các phần tử. Việc tính toán ánh xạ lôgic được thực hiện trong hai bước.
Thứ nhất, ta liệt kê các đường dẫn truy cập lôgic tồn tại trong mỗi lược đồ.
Các định nghĩa đường dẫn này về cơ bản dựa trên hai loại quan hệ: các định
nghĩa khóa và khóa ngoại và các quan hệ mẹ-con. Để thực hiện điều này, ta
sử dụng phương pháp quan hệ cổ điển để tính toán tất cả các kết nối lồng
trong lược đồ, và do đó liệt kê tất cả các quan hệ lôgic trong các lược đồ này.
Thứ hai, một thuật toán ánh xạ sẽ xem xét mỗi cặp quan hệ lôgic nguồn và
quan hệ lôgic đích, và tính toán cho mỗi cặp một phụ thuộc nguồn-đích. Việc
tính toán phụ thuộc được định hướng bởi tất cả các tương ứng mà thích đáng
cho quan hệ lược đồ nguồn và quan hệ lược đồ đích đã cho. Công cụ Clio có
hiệu quả trong việc khám phá tất cả các kiểu đối sánh, ngay cả các kết nối
phức hợp bao gồm các khóa, nhưng nó đòi hỏi nhiều sự can thiệp của người
dùng (mỗi khi một cặp đối sánh được phát hiện). Hơn nữa, chỉ có quan hệ mẹ-
con được sử dụng trong quá trình đối sánh, và không có chi tiết nào về việc sử
dụng các tính năng như là kiểu.
1.3.5 Một số hệ thống đối sánh lược đồ khác
Cũng dựa vào khảo sát của Rahm và Bernstein cũng như một số khảo sát
khác (chẳng hạn như khảo sát của Shvaiko và Euzenat), sau đây chúng tôi mô
tả một số hệ thống đối sánh lược đồ khác. Các hệ thống này đã và đang được
triển khai trong một số lĩnh vực khác nhau, do đó chúng cũng cho ta thấy một
cái nhìn tổng quan về phạm vi áp dụng của đối sánh lược đồ.
* COMA: COMA là một công cụ đối sánh lược đồ theo phương pháp kết
hợp. COMA cung cấp một thư viện mở rộng các thuật toán đối sánh, một
khung làm việc để kết hợp các kết quả đối sánh khác nhau và đánh giá hiệu
quả của các phương pháp đó. Hầu hết các bộ đối sánh này đều sử dụng
phương pháp đối sánh xâu, một số khác thì sử dụng các kỹ thuật như Cupid.
Chương 1: Đối sánh lược đồ
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
27
* SemInt: SemInt là hệ thống đối sánh lược đồ dựa trên dữ liệu. Nó bao
gồm 15 tiêu chuẩn dựa trên ràng buộc và 5 tiêu chuẩn dựa trên nội dung được
hình thành từ các bản ghi dữ liệu và được chuẩn hóa trong khoảng [0,1], mỗi
thuộc tính là một điểm trong không gian 20 chiều. Hệ thống cho phép tạo ánh
xạ giữa các phần tử độc lập sử dụng mạng nơ-ron nhưng không hỗ trợ đối
sánh ngôn ngữ và đối sánh đồ thị.
* SKAT: SKAT thực hiện đối sánh dựa trên lược đồ sử dụng luật. Luật là
các biểu thức trong logic vị từ để thể hiện các quan hệ tương đương, không
tương đương và các hàm được định nghĩa để sinh ra các luật đối sánh mới.
SKAT được sử dụng trong kiến trúc ONION, một kiến trúc được phát triển
cho lĩnh vực tích hợp ontology. Trong ONION, các ontology được chuyển
thành mô hình CSDL hướng đối tượng dựa trên đồ thị.
* TransScm: TransScm sử dụng phương pháp đối sánh dựa trên lược dồ
để thực hiện việc chuyển đổi dữ liệu. Lược đồ được biểu diễn dưới dạng đồ
thị. Tập luật được xây dựng bởi người quản trị được áp dụng vào các nút của
đồ thị. Quá trình đối sánh được thực hiện theo mô hình trên xuống với quy
luật là các nút cha mẹ sẽ cần kết quả đối sánh của các nút con cái.
* DIKE: hệ thống DIKE tích hợp nhiều lược đồ quan hệ bằng cách khai
thác yếu tố tương tự giữa hai phần tử của lược đồ phụ thuộc vào sự tương tự
của các phần tử lân cận. Đối sánh lược đồ là bước cơ bản trong hệ thống này.
Ngoài các hệ thống trên, còn một số hệ thống khác nữa như ARTEMIS
& MOMIS, Delta (MITRE), Tess, S-Match, OLA, NOM, QOM, Anchor-
PROMPT, v.v.. Các hệ thống này đều dựa trên đối sánh lược đồ và đã đưa ra
nhiều phương pháp đối sánh khác nhau, nhưng nhìn chung hầu hết các
phương pháp này đều có thể quy về một trong các tiếp cận ta đã xem xét ở
phần trên. Chi tiết hơn về các hệ thống này có thể xem khảo sát của Rahm và
Bernstein cũng như khảo sát của Shvaiko và Euzenat.
Chương 1: Đối sánh lược đồ
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
28
1.4 Kết chương
Như đã phân tích ở trên, các thuật toán đối sánh lược đồ khác nhau đã bắt
đầu quan tâm đến cấu trúc XML.Trong khi các phương pháp đối sánh ngôn
ngữ và đối sánh dựa trên ràng buộc đã được phát triển rộng rãi và có khả năng
áp dụng cho lược đồ XML, các phương pháp đối sánh cấu trúc đã đề xuất vẫn
còn không hiệu quả và có nhiều hạn chế (chỉ làm việc với DTD và chỉ khai
thác các quan hệ cha mẹ - con cái). Như ta thấy, từ tổ chức cấu trúc trong tài
liệu XML ta có thể suy ra được một số ngữ nghĩa của dữ liệu, do vậy các tiếp
cận đối sánh lược đồ XML nên khai thác thông tin này nhằm làm tăng độ
chính xác đối sánh. Thách thức cơ bản đặt ra ở đây là nhận biết các tính năng
cấu trúc hữu ích cho việc giải quyết vấn đề đối sánh lược đồ XML.
Bằng cách phân tích các thuật toán đối sánh lược đồ hiện hành, ta thấy
rằng các tiếp cận này thường mô tả không đủ rõ ràng và chính xác các định
nghĩa hình thức cho vấn đề mà chúng giải quyết và các giả thiết đặt ra trong
các tiếp cận đó. Chẳng hạn các tiếp cận này chưa mô tả rõ ràng thông tin đầu
vào và đầu ra cho tiến trình đối sánh cũng như các giả thiết làm tiền đề cho
tiến trình đối sánh. Các hạn chế này làm cho việc mở rộng các nghiên cứu này
tỏ ra khóa khăn hơn. Nhằm giải quyết vấn đề này, trong chương tiếp theo,
chúng tôi sẽ mô tả các định nghĩa hình thức đầy đủ hơn cho vấn đề đối sánh
lược đồ XML.
Chương 2: Các định nghĩa hình thức
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
29
Chương 2
Các định nghĩa hình thức
Như đã trình bày trong chương trước, đối sánh lược đồ là bài toán trung
tâm trong rất nhiều ứng dụng hiện nay. Đây là vấn đề thu hút nhiều sự chú ý
trong thời gian qua và đã có khá nhiều nghiên cứu đề xuất các giải pháp đối
sánh tương đối hiệu quả. Tuy nhiên các nghiên cứu này thường không cung
cấp đầy đủ các định nghĩa hình thức cho vấn đề. Để đánh giá được các tiếp
cận đã đề xuất cũng như phát triển và hoàn thiện hơn nữa các tiếp cận hiện
có, việc đưa ra các định nghĩa hình thức đầy đủ cho vấn đề là điều cực kỳ cần
thiết. Tuy vậy, việc đưa ra các định nghĩa hoàn chỉnh thường đòi hỏi phải có
những nghiên cứu tương đối chín muồi, nhưng trong thời điểm hiện nay, đây
vẫn còn là một vấn đề khá mới mẻ.
Trong luận văn này chúng tôi quan tâm đến vấn đề đối sánh lược đồ
XML. Với mục đích phát triển một giải pháp nhằm tự động hóa tiến trình đối
sánh lược đồ XML, chúng tôi cố gắng tổng hợp lại các nghiên cứu liên quan,
dựa trên các định nghĩa đã có, không những trong vấn đề đối sánh lược đồ
mà cả trong các lĩnh vực tương tự để đưa ra các định nghĩa hình thức cơ bản
nhất cho vấn đề này. Các khía cạnh mà chúng tôi sẽ xem xét trong chương
này là vấn đề đối sánh ngữ nghĩa lược đồ, mô hình dữ liệu biểu diễn lược đồ
XML và cuối cùng là các phép toán chuyển đổi dữ liệu.
Chương 2: Các định nghĩa hình thức
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
30
2.1 Vấn đề đối sánh lược đồ XML
2.1.1 Đối sánh ngữ nghĩa và đối sánh cú pháp
Như đã đề cập trong chương trước, đối sánh lược đồ thường được định
nghĩa là quá trình tìm kiếm sự tương đồng giữa các lược đồ dựa trên ngữ
nghĩa của chúng. Do đó đối sánh lược đồ thường được xem như là đối sánh
lược đồ ngữ nghĩa và hai thuật ngữ này thường được dùng thay thế lẫn nhau
mà không ai định nghĩa chính xác thế nào là ngữ nghĩa. Trong chương sau,
trong khi xem xét vấn đề đối sánh tự động lược đồ XML, chúng tôi sẽ xem
xét cụ thể hơn ý nghĩa của thuật ngữ này.
Hiện nay chỉ mới có một nghiên cứu đưa ra các định nghĩa hình thức cho
vấn đề đối sánh lược đồ [11] và một nghiên cứu đưa ra những định nghĩa hạn
chế hơn [6]. Dựa trên những nghiên cứu đó và trên cơ sở các định nghĩa hình
thức trong một số lĩnh vực khác (tích hợp dữ liệu, chuyển đổi dữ liệu, xử lý
truy vấn ngữ nghĩa, đối sánh & tích hợp ontology, v.v.. xem khảo sát của
Rahm và Bernstein [17]), chẳng hạn như những định nghĩa đã được đưa ra
trong [5] hay [20], trong phần tiếp theo, chúng tôi sẽ trình bày một định nghĩa
hình thức đầy đủ hơn cho vấn đề này. Như ta thấy, hầu hết những nghiên cứu
về đối sánh lược đồ đều đặt giả thiết là người dùng có thể quyết định một lược
đồ đã cho là chính xác hay không. Điều này đòi hỏi người dùng phải hiểu ý
nghĩa của nội dung lược đồ. Trong thực tế, các khái niệm nói chung và các
quan hệ ngữ nghĩa giữa chúng chỉ tồn tại trong ý nghĩ người dùng và không
cụ thể (trừu tượng). Trong khi đó lược đồ cú pháp lại tồn tại ở dạng hình thức,
tức là dựa trên cơ sở biểu diễn cụ thể của một tập các khái niệm ngữ nghĩa và
các quan hệ giữa chúng (ví dụ về lược đồ cú pháp là lược đồ quan hệ, lược đồ
hướng đối tượng, lược đồ XML, v.v..). Đối sánh ngữ nghĩa là quá trình người
dùng xem xét xem hai (hay nhiều hơn) khái niệm ngữ nghĩa là tương đồng
như thế nào trên cơ sở một số hàm tương đồng chủ quan.
Chương 2: Các định nghĩa hình thức
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
31
Khi phân tích sự tương đồng giữa hai phần tử cú pháp cụ thể a và b, đầu
tiên người dùng thường ánh xạ chúng thành các khái niệm ngữ nghĩa trong ý
nghĩ α và β (đây là quá trình hiểu biết về các lược đồ cú pháp) sau đó thực
hiện đối sánh ngữ nghĩa, tức là suy ra sự tương đồng giữa a và b trên cơ sở sự
tương đồng của α và β. Khi phát hiện tự động sự tương đồng giữa hai lược đồ
cú pháp, công cụ đối sánh không quan tâm đến hiểu biết của người dùng mà
chỉ quan tâm đến các dấu hiệu về cú pháp trong các lược đồ cú pháp và dữ
liệu. Do đó trong việc giải quyết vấn đề đối sánh lược đồ tự động, giải pháp
đề xuất phải tiệm cận đến sự tương đồng ngữ nghĩa một cách tối đa bằng cách
sử dụng các dấu hiệu cú pháp, từ đó ta có giả thiết sau:
Giả thiết 1: Các dấu hiệu cú pháp của hai lược đồ càng tương đồng, ngữ
nghĩa của hai lược đồ càng tương đồng.
Hiện nay, đã có một số nghiên cứu quan tâm đến việc thiết kế các lược
đồ XML sao cho phản ánh được hiểu biết của người dùng. Các tác giả trong
[18] đã đề nghị giải pháp mô hình hóa (về mặt khái niệm) các lược đồ XML
trên cơ sở ngôn ngữ mô hình hóa hợp nhất (Unified Modeling Language -
UML). Một phần cơ bản của UML tĩnh đã được sử dụng để thiết kế các lược
đồ XML. Một tiếp cận khác đó là sử dụng phương pháp hướng đối tượng để
thiết kế một cách khái niệm các lược đồ XML [21]. Tiếp cận này đưa ra các
lược đồ XML mà mỗi phần tử lược đồ biểu diễn một thực thể ngữ nghĩa và
mỗi quan hệ lược đồ biểu diễn một quan hệ ngữ nghĩa. Một đường dẫn trong
cây XML cũng biểu diễn một quan hệ ngữ nghĩa hỗn hợp. Do vậy, lược đồ
XML phản ánh được hiểu biết của người thiết kế lược đồ. Tuy các phương
pháp này cung cấp cơ sở mô hình hóa để thiết kế các lược đồ XML nhưng
chúng không chỉ ra các thuộc tính và các ràng buộc thêm vào (chẳng hạn như
các kiểu dữ liệu hay các ứng viên) được gán cho các phần tử lược đồ như thế
nào. Vấn đề này phụ thuộc vào kinh nghiệm thực tế của người thiết kế. Sự
Chương 2: Các định nghĩa hình thức
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
32
không đồng nhất giữa các lược đồ phản ánh hai vấn đề: thứ nhất là sự hiểu
biết khác nhau của người thiết kế lược đồ và thứ hai là sự khác biệt trong việc
mô hình hóa và ràng buộc (về mặt khái niệm) các thực thể giống nhau. Như
vậy để so sánh được hai lược đồ XML ta cần làm rõ cả hai vấn đề trên.
Trong luận văn này chúng tôi mô hình hóa lược đồ XML dưới dạng đồ
thị gán nhãn có hướng, gọi là đồ thị lược đồ (xem mục 2.3.2) trong đó các nút
và cạnh phản ánh hiểu biết của người thiết kế lược đồ, các ràng buộc trên các
nút và cạnh phản ánh các ràng buộc mà người thiết kế lược đồ đặt ra. Mô hình
này có hai lợi ích chính: thứ nhất là thể hiện rõ các tính năng lược đồ XML sử
dụng trong tiến trình đối sánh, thứ hai là chuẩn hóa các ngôn ngữ lược đồ
XML để đồng nhất hóa các biểu diễn, do vậy ta không cần quan tâm đến các
khác biệt về mặt cú pháp nữa.
2.1.2 Thông tin đầu vào của tiến trình đối sánh
Để tự động hóa được vấn đề đối sánh ngữ nghĩa, đầu tiên ta cần chỉ ra
chính xác kiểu thông tin đầu vào và đầu ra. Nhìn chung thông tin đầu vào có
thể là bất kỳ tri thức nào về lược đồ được đối sánh, các thể hiện và các miền
của chúng. Trong mục này, ta sẽ mô tả các loại thông tin đầu vào sau:
- Thông tin lược đồ: đề cập đến các khởi dựng cú pháp như các phần tử,
tên, tổ chức cấu trúc của chúng, quan hệ giữa các phần tử, các ràng buộc lược
đồ, v.v.. Như đã đề cập trong chương 1, hiện nay rất ít các thuật toán đối sánh
lược đồ XML (mà có quan tâm đến đối sánh cấu trúc) khai thác tất cả các tính
năng lược đồ XML. Khái niệm đồ thị lược đồ (mô tả trong phần sau) sẽ khắc
phục được vấn đề này.
- Thể hiện dữ liệu: Thông thường chỉ có giải pháp đối sánh trên cơ sở
học quan tâm đến việc phân tích nội dung của các thể hiện dữ liệu. Như đã chỉ
ra trong chương 2, giải pháp đối sánh trên cơ sở luật (phân tích lược đồ để
Chương 2: Các định nghĩa hình thức
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
33
thực hiện đối sánh) có thể được bổ sung bằng cách phân tích nội dung thể
hiện dữ liệu, khi nó có sẵn. Tuy vậy, trong vấn đề sử dụng lại nội dung, tập
các thể hiện dữ liệu có thể không tồn tại sẵn do đó ta sẽ không khai thác thông
tin này.
- Phản hồi người dùng: Như ta thấy, tiến trình đối sánh không thể tự
động hóa được hoàn toàn, do vậy luôn phải có sự can thiệp của người dùng.
Trong hầu hết các thuật toán hiện hành, đầu vào người dùng thường được yêu
cầu trước khi đối sánh (để cung cấp một đối sánh ban đầu) hoặc sau khi đối
sánh (để xác nhận đầu ra đối sánh). Mục đích của ta là gắn lược đồ đích với
dữ liệu nguồn như người dùng mong muốn. Do đó ta có thể giả thiết rằng
người dùng biết những gì họ muốn trong thể hiện đích và có thể quyết định
một đối sánh là chính xác hay không. Hơn nữa, họ có thể quyết định một số
vấn đề, chẳng hạn nếu thấy một kết quả có khả năng mất mát thông tin từ
nguồn thì đích phải được thay đổi.
Giả thiết 2: Người dùng biết chính xác các chi tiết lược đồ đích và có thể
quyết định được một ánh xạ có chính xác hay không để đưa ra một phép toán
chuyển đổi mong muốn. Bên cạnh đó, người dùng có thể hủy bỏ dữ liệu hoặc
thay đổi và điều chỉnh lược đồ đích.
- Thông tin phụ trợ: Một số thuật toán đối sánh dựa trên việc sử dụng từ
điển đồng nghĩa và các từ điển nói chung để thực hiện đối sánh thuật ngữ.
Trong luận văn này chúng tôi sử dụng thông tin phụ trợ từ WordNet, một
CSDL từ vựng điện tử tiếng Anh trong đó các quan hệ (chẳng hạn như tính
đồng âm) được liên kết sẵn với ý nghĩa của từ [14]. Mặc dù định hướng phát
triển của đề tài là áp dụng bài toán đối sánh lược đồ cho tiếng Việt, nhưng
trong luận văn này tạm thời chúng tôi chỉ xét tiếng Anh và sử dụng WordNet
tiếng Anh. Trong tương lai khi hệ thống WordNet tiếng Việt đã được xây
dựng hoàn chỉnh (hiện nay đã có một số nghiên cứu được triển khai nhằm xây
Chương 2: Các định nghĩa hình thức
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
34
dựng một hệ thống WordNet tiếng Việt, chẳng hạn như nghiên cứu của nhóm
tác giả Đinh Điền, Nguyễn Văn Toàn tại trường ĐHBK TP.HCM) việc áp
dụng các giải pháp này cho tiếng Việt là hoàn toàn khả thi. Mặc dù có thể sử
dụng các từ điển chuyên đề khác (ví dụ các từ không thuộc WordNet), ta sẽ
không xem xét vấn đề này do chỉ quan tâm đến cách khai thác một từ điển đã
cho vì mục đích đối sánh lược đồ chứ không phải là đề xuất các từ điển riêng.
Có thể sử dụng các nghiên cứu về từ điển chuyên đề để mở rộng vấn đề này.
- Tiêu chuẩn đối sánh: Trong mục 2.1.1, chúng tôi đã chỉ ra rằng thành
phần chính để đối sánh tự động lược đồ ngữ nghĩa là hàm tương đồng (còn
gọi là tiêu chuẩn đối sánh). Hầu hết các thuật toán đối sánh lược đồ đều dựa
trên việc kết hợp nhiều dấu hiệu (ở đây chúng tôi tạm dịch từ clue hay
heuristic) khác nhau. Một ví dụ về dấu hiệu là: "các phần tử có cùng tên hoặc
cùng nghĩa thì thích hợp hơn cho sự tương đồng ngữ nghĩa". Việc lựa chọn
các dấu hiệu này sẽ ảnh hưởng đến chất lượng của tiến trình đối sánh. Ta cần
hiểu rõ các hàm dấu hiệu được sử dụng để chỉ ra tham số, đầu ra của chúng và
cách kết hợp chúng để cung cấp ánh xạ cuối cùng.
2.1.3 Thông tin đầu ra của tiến trình đối sánh
Hầu hết các hệ thống đối sánh lược đồ hiện hành đều cung cấp các ánh
xạ với độ tin cậy (còn gọi là hệ số tương đồng) trong phạm vi [0, 1]. Mục đích
của ta là không chỉ cung cấp một thuật toán đối sánh cho các lược đồ XML
mà còn phải tạo ra ánh xạ giữa các phần tử tương đồng cũng như các hàm
chuyển đổi dữ liệu. Một ví dụ cho ánh xạ này là (address, location, 0.8,
rename), trong đó phần tử address đối sánh với phần tử location với độ tin
cậy 0.8. Còn để chuyển đổi một thể hiện của phần tử address (trên lược đồ
nguồn) thành một thể hiện của phần tử location (trên lược đồ đích), ta chỉ cần
đổi tên phần tử address thành location. Ngoài các ánh xạ một-một, ta cũng
cần phát hiện được các ánh xạ phức hợp, chẳng hạn như ({FirstName,
Chương 2: Các định nghĩa hình thức
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
35
LastName}, name, 0.8, concat) cho phép ghép các phần tử nguồn FirstName
và LastName để đối sánh với phần tử đích name với độ tin cậy 0.8. Ta cũng
cần định nghĩa tập các phép toán trên các phần tử lược đồ nguồn cho phép tạo
tự động các hàm chuyển đổi.
Trong trường hợp có nhiều kết quả đối sánh, ta cần đưa ra một danh sách
các ánh xạ tốt nhất. Các kết quả ánh xạ phải được xếp thứ tự theo độ tin cậy
của chúng. Nếu số lượng ánh xạ nhỏ, người dùng có thể dễ dàng lựa chọn ánh
xạ đúng trong danh sách này. Phương pháp này đã được sử dụng trong hệ
thống LSD. Ở đó các tác giả đã chỉ ra rằng, bằng cách trả về một danh sách
nhỏ thay vì ánh xạ đơn, mức chính xác của giải pháp sẽ tăng lên mà không
làm mất nhiều công sức người dùng. Cuối cùng, kết quả ánh xạ cần được cấu
trúc hóa theo cách nào đó để sự xác nhận của người dùng và sự thích nghi của
nó (ví dụ khi lược đồ tiến hóa) là dễ dàng. Trong trường hợp này, ta sẽ không
lặp lại tiến trình đối sánh mà chỉ cần cập nhật các ánh xạ giữa các phần tử
thay đổi trong các lược đồ nguồn và đích.
2.1.4 Các định nghĩa hình thức
Ở mục trên ta đã xem xét định nghĩa phi hình thức của vấn đề đối sánh
lược đồ XML và các yêu cầu đối với một giải pháp khả thi cho vấn đề này.
Trong mục này ta sẽ cung cấp các định nghĩa hình thức cho vấn đề đối sánh
lược đồ XML. Đầu tiên ta xét một số định nghĩa cơ sở:
Định nghĩa 2.1: (Đối sánh ngữ nghĩa) Cho một biểu diễn ý thức của tập vũ
trụ U, và một hàm tương đồng ngữ nghĩa chủ quan trên các khái niệm của U,
được biểu thị bởi SU, đối sánh ngữ nghĩa là tiến trình trong đó người dùng có
thể chỉ ra hai khởi dựng cú pháp a và b là tương đồng về mặt ngữ nghĩa dựa
trên việc các ánh xạ tương ứng của chúng trong U tương đồng như thế nào
trong SU.
Chương 2: Các định nghĩa hình thức
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
36
Định nghĩa 2.2: (Đối sánh ngữ nghĩa tự động) Đối sánh ngữ nghĩa tự động
là một tiến trình trong đó một hàm tương đồng cú pháp khách quan, gọi là
tiêu chuẩn đối sánh (áp dụng cho các lược đồ cú pháp) được sử dụng để xấp
xỉ đến mức có thể các kết quả của một đối sánh ngữ nghĩa người dùng trên cơ
sở giả thiết 1.
Sau đây chúng tôi sẽ mô tả chi tiết mô hình lược đồ XML và đại số ánh
xạ nguồn–đích. Tiêu chuẩn đối sánh và phương pháp kết hợp phản hồi người
dùng sẽ được mô tả trong chương 3.
2.2 Mô hình hóa lược đồ XML
Như ta thấy, cho đến nay rất ít các thuật toán hiện hành về đối sánh lược
đồ XML (mà tập trung vào đối sánh cấu trúc) khai thác tất cả các tính năng
của lược đồ XML. Trong phần này, chúng tôi đưa ra một mô hình dữ liệu trừu
tượng nhằm biểu diễn lược đồ XML cũng như các ngôn ngữ lược đồ khác ở
mức khái niệm, đó là đồ thị lược đồ - đồ thị gán nhãn có hướng với các tập
ràng buộc. Đồ thị lược đồ bao gồm một dãy các nút liên kết với nhau qua các
cạnh gán nhãn có hướng. Thêm vào đó, các ràng buộc có thể được định nghĩa
trên các nút và các cạnh. Hình 2.1 minh họa một ví dụ về đồ thị lược đồ.
Hình 2. 1 Ví dụ về đồ thị lược đồ
c[1..1]
p[1..1] c[1..1]
c[0..N] c[0..N]
c
c[1..N] c
a
University
Location
Article Journal
Journal-ref Title
Author Name
Name Library
c
Abstract Editor
c
c
Book
Monograph
h
a
c[0..N]
Chương 2: Các định nghĩa hình thức
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
37
2.2.1 Các nút đồ thị lược đồ
Ta phân chia các nút thành hai loại: nút nguyên tố và nút phức hợp. Nút
nguyên tố không có cạnh nào đi ra (xuất phát) từ chúng. Chúng là các nút lá
trong đồ thị lược đồ. Nút phức hợp là các nút trong của đồ thị lược đồ. Mỗi
nút nguyên tố chứa một nội dung đơn, đó có thể là một giá trị nguyên tố trên
miền các kiểu dữ liệu cơ bản (ví dụ string, integer, date, v.v..) hoặc một giá
trị dạng danh sách (list value) hoặc một giá trị hợp (union value). Nội dung
của nút phức hợp được gọi là nội dung phức hợp, nó tham chiếu đến một số
nút khác qua các cạnh gán nhãn có hướng. Trong hình 2.1, các nút University
và Library là các nút phức hợp, trong khi đó các nút Name và Location là các
nút nguyên tố.
2.2.2 Các cạnh đồ thị lược đồ
Mỗi cạnh trong đồ thị lược đồ liên kết hai nút, điều này thể hiện khía
cạnh cấu trúc của lược đồ XML. Ta phân biệt ba loại cạnh thể hiện các quan
hệ chứa, thuộc tính và kết hợp:
- Quan hệ chứa, được biểu thị bởi c, là một quan hệ hợp trong đó một nút
hợp ("toàn thể" – "whole") bao gồm một số nút thành phần ("bộ phận" –
"parts").
- Quan hệ thuộc tính, được biểu thị bởi p, cho biết thuộc tính phụ trợ của
một nút.
- Quan hệ kết hợp, được biểu thị bởi a, là một quan hệ cấu trúc cho biết
cả hai nút là có cùng mức về mặt khái niệm. Về bản chất các quan hệ kết hợp
mô hình hóa các khóa/khóa tham chiếu và thay thế cho các cơ chế nhóm. Các
quan hệ này thông thường là hai chiều. Hai quan hệ kết hợp được trình bày
trong hình 2.1. Kết hợp thứ nhất giữa hai nút Book và Monograph nhằm mô
hình hóa việc thay thế quan hệ nhóm giữa hai nút. Trong khi đó quan hệ kết
Chương 2: Các định nghĩa hình thức
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
38
hợp thứ hai giữa Journal-ref và Journal chỉ ra một quan hệ khóa/khóa tham
chiếu. Trong hình vẽ các cạnh kết hợp được mô tả dưới dạng các đường nét
đứt.
2.2.3 Các ràng buộc đồ thị lược đồ
Các ràng buộc khác nhau có thể được chỉ rõ bằng ngôn ngữ lược đồ
XML. Các ràng buộc này có thể được định nghĩa trên cả nút và cạnh. Chúng
thể hiện các yêu cầu khác nhau về số yếu tố, miền, thứ tự, loại trừ, tính duy
nhất và toàn vẹn tham chiếu.
2.2.3.1 Các ràng buộc trên một cạnh
Ràng buộc điển hình trên một cạnh là ràng buộc số yếu tố. Ràng buộc số
yếu tố trên cạnh chứa chỉ ra số nút con cái đối với nút cha mẹ. Các ràng buộc
số yếu tố điển hình là "một" ([1..1]), "một-hoặc-nhiều" ([1..N]), "không-hoặc-
một" ([0..1]) và "không-hoặc-nhiều" ([0..N]). Các ràng buộc số yếu tố cũng
có thể được chỉ ra với khoảng bất kỳ theo hình thức [minOccurs, maxOccurs].
Ràng buộc số lượng trên cạnh thuộc tính cho biết một thuộc tính là tùy chọn
hay bắt buộc cho một nút đã cho.
Ví dụ mỗi University trong hình 2.1 phải có đúng một Name. Do đó ràng
buộc số yếu tố là [1..1] trên liên kết “University Æ Name”. Một University
cũng phải có một thuộc tính Location, được biểu thị bởi [1..1] trên cạnh
thuộc-tính-của “University Æ Location” tương ứng. Đặc tả số yếu tố mặc
định trong hình 2.1 là [1..1].
2.2.3.2 Các ràng buộc trên một tập cạnh
Ta cũng phân biệt ba loại ràng buộc trên tập các cạnh:
- Ràng buộc thứ tự: về bản chất ràng buộc này được định nghĩa cho một
tập các quan hệ chứa. Trong thực tế một nút "whole" có thể được kết hợp với
các nút "part" khác theo một thứ tự riêng biệt. Lấy ví dụ nút phức hợp Article,
Chương 2: Các định nghĩa hình thức
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
39
thì Title và Athour phải xuất hiện theo thứ tự này. Ràng buộc này được sử
dụng để mô hình hóa các cơ chế "sequence" của lược đồ XML. Một tập các
nút cũng có thể xuất hiện theo thứ tự bất kỳ và mỗi nút giữa chúng có thể xuất
hiện chỉ một lần hoặc không lần nào cả, điều này mô hình hóa cơ chế "all"
của lược đồ XML.
- Phân tách loại trừ: ràng buộc này trên tập các cạnh (các quan hệ) được
sử dụng để chỉ ra rằng mỗi thời điểm chỉ một trong các quan hệ duy nhất áp
dụng. Điều này được sử dụng để mô hình hóa cơ chế "choice" của lược đồ
XML. Ràng buộc phân tách loại trừ được áp dụng cho các cạnh chứa.
- Ràng buộc tham chiếu: các lược đồ XML đưa ra khả năng mô tả các
ràng buộc toàn vẹn. Đôi khi nội dung của một nút (hoặc một tập các nút) được
liên kết với nội dung của một nút (hoặc một tập các nút) khác. Ràng buộc
tham chiếu trên một nút đòi hỏi phải có nội dung nút như nhau cho nút tham
chiếu. Ràng buộc tham chiếu được áp dụng cho các cạnh kết hợp và thông
thường được mô hình hóa thông qua một vị từ nối. Ví dụ, cạnh kết hợp giữa
Article và Journal với vị từ Article/JournalRef = Journal.
2.2.3.3 Các ràng buộc trên một nút
Các ràng buộc áp dụng cho một nút bao gồm:
- Ràng buộc đơn nhất: Khi một nút có thể xuất hiện một vài lần, ràng
buộc đơn nhất yêu cầu mỗi một xuất hiện này phải có nội dung nút duy nhất.
- Ràng buộc miền: Ràng buộc miền thì rất rộng, nhưng về bản chất chúng
quan tâm đến nội dung của nút nguyên tố. Chúng có thể hạn chế phạm vi hợp
lệ của các giá trị số theo các giá trị lớn nhất/nhỏ nhất, giới hạn chiều dài của
các giá trị xâu hay ràng buộc các mẫu giá trị xâu. Ví dụ chúng có thể chỉ ra
một nút nguyên tố hoặc nút phức hợp đã cho là có kiểu bất kỳ (“any type”)
hay không, nghĩa là không có ràng buộc nào về nội dung được gắn vào nó.
Chương 2: Các định nghĩa hình thức
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
40
2.2.4 Các định nghĩa hình thức
Định nghĩa 2.3 (Đồ thị lược đồ) Một đồ thị lược đồ G là một bộ-4 (NG, EG,
Label, Const), trong đó:
- NG là tập hữu hạn các nút không rỗng,
- EG là một tập hữu hạn các cạnh biểu diễn quan hệ giữa các nút,
- Label là tập hữu hạn các nhãn biểu thị các quan hệ khác nhau giữa các
nút,
- Const là tập các ràng buộc trên nút và cạnh.
Định nghĩa 2.4 (Nút) Một nút n ∈NG là bộ-3 (nname, ncategory, ncontent) bao gồm
một tên nút nname kết hợp với một không gian tên, một thư mục nút ncategory cho
biết nút n là nguyên tố hay phức hợp và một nội dung nút ncontent chỉ rõ nội
dung đơn giản cho các nút đơn giản và nội dung phức hợp cho các nút phức
hợp. Cho NA và NC lần lượt là tập các nút nguyên tố và các nút phức hợp, NA
và NC tạo thành một phân hoạch trên NG, tức là NA∩NC = ∅ và NA∪NC =
NG.
Định nghĩa 2.5 (Cạnh) Một cạnh e ∈EG là bộ-3 (elabel, esource, etarget), bao
gồm một nhãn elabel ∈Label cho biết kiểu đường dẫn, nút nguồn của cạnh esource
∈NG và nút đích của cạnh etarget ∈NG. Ta phân biệt ba loại cạnh: cho Ec, Ep
và Ea lần lượt là tập các cạnh chứa, cạnh thuộc-tính-của và cạnh kết hợp. Ec,
Ep và Ea tạo thành một phân hoạch trên EG, tức là Ec∩Ep∩Ea = ∅ và
Ec∪Ep∪Ea = EG.
Định nghĩa 2.6 (Ràng buộc) Một ràng buộc c ∈Const là bộ-4 (Cname, Ccategory,
Capply-to, Cvalue) trong đó Cname là một tên ràng buộc (chẳng hạn như ràng buộc
duy nhất, số yếu tố), Ccategory là một danh mục ràng buộc (ràng buộc trên nút,
Chương 2: Các định nghĩa hình thức
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
41
ràng buộc trên cạnh, ràng buộc trên tập cạnh), Capply-to định nghĩa các thành
phần áp dụng ràng buộc (ví dụ tên nút trong trường hợp ràng buộc trên nút) và
Cvalue là giá trị của ràng buộc (nếu nó tồn tại, nếu không thì lấy giá trị mặc
định ∅).
Ta không cần kiểm tra tính hợp khuôn dạng của đồ thị lược đồ (ví dụ nếu
nhãn cạnh là thuộc tính thì kiểm tra rằng nút nguồn là một nút phức hợp và
nút đích là một nút nguyên tố). Điều này là do ta xây dựng đồ thị lược đồ trên
cơ sở các lược đồ XML hợp lệ đã có. Dựa trên các khái niệm nút và cạnh, ta
đưa ra thêm các khái niệm đường dẫn, đường dẫn nguyên thủy như sau:
Định nghĩa 2.7 (Đường dẫn) Một đường dẫn từ một nút n1 tới nút nk là một
dãy n1, n2, … , nk, trong đó n1, n2, … , nk ∈NG, và với bất kỳ hai nút liên tiếp
ni and ni+1 (1 ≤ i ≤ k-1), tồn tại một cạnh ei (l, ni , ni+1) ∈ EG – {Ea}. Một
đường dẫn chỉ bao gồm các cạnh chứa và cạnh thuộc-tính-của. Ta gọi n1 và nk
lần lượt là nút bắt đầu và nút kết thúc của đường dẫn. Đường dẫn được xem là
đi qua nút ni (1 ≤ i ≤ k). Độ dài của đường dẫn là tổng số nút mà đường dẫn đi
qua, tức là, k với đường dẫn P = (n1, n2, … , nk), biểu thị như length(P)= k.
Định nghĩa 2.8 (Đường dẫn nguyên thủy) Một đường dẫn từ nút n1 tới nút
nk, là một đường dẫn nguyên thủy khi và chỉ khi nút bắt đầu n1 không có cạnh
vào (nghĩa là nút bắt đầu là gốc của đồ thị lược đồ).
Khái niệm đồ thị lược đồ được mô tả ở trên không bao gồm các tính năng
như thừa kế kiểu và kiểu trừu tượng. Các vấn đề này sẽ được xem xét trong
chương 3. Chú ý rằng đồ thị lược đồ được xây dựng bằng cách mở rộng các
kiểu chia sẻ trong lược đồ XML. Dựa trên việc hình thức hóa đồ thị lược đồ,
ta đưa ra thêm một số định nghĩa về việc chuyển đổi khởi dựng nguồn thành
khởi dựng đích (khái niệm khởi dựng ở đây nhằm nói đến nút và cạnh trong
đồ thị lược đồ). Một phần tử ánh xạ liên kết một khởi dựng từ S tới một khởi
Chương 2: Các định nghĩa hình thức
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
42
dựng tương đồng ngữ nghĩa từ T (lần lượt là các đồ thị lược đồ nguồn và
đích). Mặc dù một nguồn có thể không có một khởi dựng tương ứng trực tiếp
tới một khởi dựng đích, các khởi dựng đích có thể được dẫn xuất từ các khởi
dựng nguồn bằng cách áp dụng một tập các phép toán đã định nghĩa trước. Cơ
chế này có những điểm tương đồng với việc tạo khung nhìn ảo trong tích hợp
dữ liệu, ở đó một khung nhìn ảo trên nguồn phải đối sánh với một lược đồ
trung gian (ví dụ ghép nối của các phần tử nguồn FirstName và LastName
thành một phần tử ảo Name mà đối sánh với phần tử đích Name). Khung nhìn
ảo cũng áp dụng được cho cạnh (ví dụ hai cạnh Author→FirstName và
Author→LastName được hợp nhất với nhau thành một cạnh ảo
Author→Name đối sánh với cạnh Author→Name trong lược đồ đích). Dựa
trên các định nghĩa trong [20] cho vấn đề tạo khung nhìn ảo, ta có thể đưa ra
các định nghĩa hình thức ánh xạ giữa các lược đồ nguồn và đích như sau:
Định nghĩa 2.9 (Bảng ký tự lược đồ) Cho một lược đồ K (tuân theo hình
thức đồ thị lược đồ), ta gọi bảng ký tự lược đồ của K hay ΣK là hợp của các
nút và các cạnh trong đồ thị lược đồ của K: ΣK = NK ∪EK.
Định nghĩa 2.10 (Khung nhìn ảo) Cho một lược đồ nguồn S và bảng ký tự
ΣS của nó, một khung nhìn ảo υS trên S là một dẫn xuất từ bảng ký tự ΣS áp
dụng một tập các phép toán đã định nghĩa trước O ={o1,…on.}.
Định nghĩa 2.11 (Phần tử ánh xạ, ánh xạ trực tiếp, ánh xạ phức hợp) Cho
VS là tập các khung nhìn ảo có thể được xây dựng trên ΣS. Một phần tử ánh xạ
là một hàm mst: ΣS∪VS → ΣT, nối kết một phần tử s trong ΣS∪VS tới một
phần tử t trong ΣT. Một phần tử ánh xạ là một ánh xạ trực tiếp nếu nó nối kết
một phần tử trong ΣS (⊆VS) tới một phần tử trong ΣT và là một ánh xạ phức
hợp nếu nó nối kết một phần tử ảo υS ∈VS tới một phần tử đích trong ΣT qua
một biểu thức ánh xạ đã định nghĩa trên O.
Chương 2: Các định nghĩa hình thức
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
43
2.3 Ánh xạ nguồn–đích
Một trong những ứng dụng cơ bản của đối sánh lược đồ là vấn đề chuyển
đổi giữa các nguồn dữ liệu có cấu trúc tuân theo các lược đồ tương đồng. Vấn
đề này đòi hỏi ta phải thiết lập các ánh xạ thích hợp giữa các phần tử tương
đồng trong hai lược đồ nguồn và đích đã cho, hay còn gọi là ánh xạ nguồn–
đích. Các nghiên cứu trong lĩnh vực CSDL đã đưa ra mô hình đại số quan hệ
khá hoàn chỉnh, do vậy ta có thể mở rộng mô hình này cho vấn đề ánh xạ
nguồn–đích trong đối sánh lược đồ. Nhiều nghiên cứu khác nhau (chủ yếu
trong lĩnh vực tích hợp dữ liệu) đã mô tả các phép toán tạo khung nhìn ảo trên
các lược đồ. Để giải quyết vấn đề này, họ chỉ ra một tập các phép toán sử
dụng như là các chuyển đổi truy vấn để tích hợp thông tin nguồn vào khung
nhìn đích. Một mở rộng của nghiên cứu này đã được đề xuất trong [20] nhằm
công thức hóa lại các truy vấn trong hệ thống tích hợp dữ liệu. Tuy vậy, các
nghiên cứu này chỉ quan tâm đến các lược đồ quan hệ và chúng không hoàn
toàn áp dụng được cho lược đồ XML. Các nghiên cứu về đối sánh cây, chẳng
hạn như [19] lại chú ý đến vấn đề phát hiện thay đổi cho cây gán nhãn. Họ
đưa ra ba phép toán trong đối sánh cây: delete, insert, relabel. Kịch bản thao
tác "rẻ nhất" cho việc chuyển đổi cây nguồn thành một cây đích là kết hợp các
phép toán này. Tuy vậy, trong các tiếp cận này, nhãn của nút không quan
trọng. Phép toán gán lại nhãn được xem là “rẻ” hơn phép xóa theo sau là một
phép toán chèn. Trong thực tế, nhãn là tên tổng quát của thẻ XML mang
thông tin ngữ nghĩa nên việc gán lại nhãn một nút thành một nút khác không
liên quan về ngữ nghĩa có thể cho ra một kết quả không mong muốn trong đối
sánh lược đồ XML.
Dựa vào các nghiên cứu trên và xuất phát từ các phép toán cơ bản đã
được mô tả trong đại số quan hệ chuẩn, ta có thể đưa ra các phép toán ánh xạ
nguồn–đích áp dụng cho đối sánh lược đồ XML. Sau đây chúng tôi sẽ xem
Chương 2: Các định nghĩa hình thức
Võ Sỹ Nam. Luận văn cao học – ngành công nghệ thông tin
44
xét những vấn đề cần phải giải quyết trong đối sánh lược đồ
Các file đính kèm theo tài liệu này:
- Luận văn- Đối sánh tự động lược đồ XML.pdf