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

TÌM HIỂU VỀ ĐỐI SÁNH LƯỢC ĐỒ VÀ
XÂY DỰNG ỨNG DỤNG VNMATCH
NGÀNH: CÔNG NGHỆ THÔNG TIN
NGÔ VĂN QUÂN
quá trình học tập và nghiên cứu.
Tôi cũng muốn gửi lời cảm ơn tới TS. Đỗ Hồng Hải
1
, tác giả của hệ thống
COMA++; anh Lê Hồng Phương
2
tác giả của vnTokenizer, vnLTag; Enrico May,
sinh viên nghiên cứu về dự án Cupid. Tôi cũng xin bày tỏ lòng biết ơn đến gia
đình và những người bạn thân đã giúp đỡ, động viên tôi rất nhiều trong suốt quá
trình học tập và làm luân văn tốt nghiệp.
Do thời gian thực hiện có hạn, kiến thức chuyên môn còn nhiều hạn chế
nên đồ án tôi thực hiện chắc chắn không tránh khỏi những thiếu sót nhất định.
Tôi rất mong nhận được ý kiế
n đóng góp của thầy, cô giáo và các bạn.
Xin chân thành cảm ơn !

Hà Nội, ngày 09 tháng 10 năm 2006 1

2
Lê Hồng Phương, công tác tại trường Đại Học Quốc Gia Hà Nội, hiện đang làm nghiên
cứu sinh tại Pháp
ii
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004 Chương 1

2.2.2 Phương pháp tiếp cận dựa trên ràng buộc 23
2.2.3 Phương pháp tiếp cận dựa trên cấu trúc 23
2.3 Đối sánh dựa trên dữ liệu 23
2.4 Đối sánh kết hợp 24
2.5 Match Cardinality 24
2.6 Các hệ số mặc định trong bài toán đối sánh 25
3 Các phương pháp đánh giá hệ thống đối sánh 26
Chương 3 Thiết kế hệ thống đối sánh lược đồ. 30
1 Khảo sát 30
2 Giới thiệu 33
2.1 Giới thiệu bài toán đối sánh lược đồ. 33
2.2 Xử lý schema trong tiếng Việt 33
3 Thiết kế 35
iii
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004

3.1 Kiến trúc hệ thống 35
3.2 Input 36
3.2.1 Schema Error! Bookmark not defined.
3.2.2 WordNet 39
3.2.3 Output 40
3.3 Mức ngôn ngữ (linguistic matching) 41
3.3.1 Các thuật toán đối sánh cơ bản 42
3.3.2 Thuật toán đối sánh kết hợp 44
3.4 Mức cấu trúc 51
3.5 Chọn lựa ánh xạ 55
4 Cài đặt và kết quả 56
4.1 Cài đặt 56
4.2 Kết quả thử ngiệm 60

Hình 3-6: Loại bỏ nút có kiểu đơn giản 38
Hình 3-7: Tái sử dụng các định nghĩa 39
Hình 3-8:Sơ đồ đối sánh mức ngôn ngữ (linguistic matching) 41
Hình 3-9: Sơ đồ thuật toán đối sánh kết hợp 45
Hình 3-10: Phân tích phần tử đầu vào 46
Hình 3-11: Thực hiện bước Direction và Selection 48
Hình 3-12: Tổng hợp kết quả 49
Hình 3-13: SimCube theo phương pháp đối sánh kết hợp 50
Hình 3-14: Kết quả sau khi thực hiện Aggregation 50
Hình 3-15: Kết quả sau khi thực hiện Direction và Selection 50
Hình 3-16:Kết quả sau khi tổng hợp 51
Hình 3-17: Hệ số tương tự của 2 node lá 52
Hình 3-18: Hệ số tương tự của 2 node trong 52
Hình 3-19: Sự phụ thuộc của hệ số tương tự vào ngữ cảnh 55
Hình 3-20:Cấu trúc VNMatch 57
Hình 3-21: MatchLib, phần core của VNMatch 57
Hình 3-22: Lớp HybridMatcher 58
Hình 3-23: VNMatch Framework (đề xuất) 73 v
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004

Mục lục các công thức

Công thức 1: Cupid, hệ số tương tự của hai tập hợp 19

Công thức 3 19
Công thức 4 19

Meronym Ngược với Holonym “Thân cây” là bộ phận
của cây
Ontology Đặc tả của khái niệm
OWL Web Ontology Language
Schema Lược đồ dữ liệu
Schema integration Tích hợp lược đồ
vii
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004

Semantic integration Tích hợp ngữ nghĩa
Schema mapping Ánh xạ lược đồ, tương tự
đối sánh lược đồ

Schema matching Đối sánh lược đồ
Synonym Từ đồng nghĩa
Web Semantic Web ngữ nghĩa
XSD XML Schema Definition
viii
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004

Tóm tắt luận văn

Luận văn cao học với đề tài “
Tìm hiểu về đối sánh lược đồ và xây dựng ứng
dụng VNMatch” nghiên cứu và tìm hiểu về bài toán đối sánh lược đồ (schema
matching). Bài toán đối sánh lược đồ được áp dụng trong các ứng dụng tích hợp
dữ liệu (data integration), chuyển đổi dữ liệu (data translation), nhà kho dữ liệu
(data warehousing), các ứng dụng web ngữ nghĩa (Web Semantic).

Chương 1 Mở đầu

Mục tiêu chính của luận văn tốt nghiệp này là nghiên cứu về bài toán đối
sánh lược đồ (schema matching). Đối sánh lược đồ là quá trình xác định ngữ
nghĩa tương ứng giữa các cấu trúc siêu dữ liệu (metadata) như lược đồ của cơ sở
dữ liệu, XSD, Ontology. Đối sánh lược đồ đóng vai trò quan trọng trong các việc
tương tác giữa các dịch vụ với nhau và trong ứng dụng tích hợp dữ liệu, Data
warehouse, E-Business.

2
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004

1 Đối sánh lược đồ
Một lược đồ là một cấu trúc siêu dữ liệu để mô tả dữ liệu được lưu giữ, truy
cập, diễn dịch bởi người dùng và các ứng dụng như thế nào. Ngoài các khía cạnh
liên quan đến quản lý dữ liệu như định dạng dữ liệu, kiểu dữ liệu, lược đồ còn có
sự mở rộng liên quan đến ngữ nghĩa của dữ liệu như tậ
p các giá trị cho phép, các
yếu tố tập hợp, toàn vẹn và ràng buộc tham chiếu… Hiện tại có nhiều ngôn ngữ
biểu diễn lược đồ đã được phát triển cho các lĩnh vực ứng dụng khác nhau, ví dụ
như SQL, DTD, XSD, OWL. Mặc dù có nhiều khả năng và ngôn ngữ biểu diễn khác
nhau nhưng lược đồ đã xuất hiện có thể nói là khắp nơi trong hầu hết các ứng
dụng về quản lý dữ
liệu và xử lý dữ liệu.

category publishDate org_id
ND 22/10/1990 15
TT 22/09/1999 32
topic publishDate org_name

một cách tự động thực sự là một việc nặng nhọc và không có một phương
pháp chuẩn nào để thực hiện.

Lược đồ cung cấp nhiều thông tin mà chúng ta có thể khai thác chúng để
thu nhận được ngữ nghĩa của các phần tử chứa trong lược đồ đó. Ví d
ụ như các
thuộc tính name, description, constraints…Tuy nhiên các thông tin này có thể
khác nhau giữa các lược đồ, chúng phụ thuộc vào ngôn ngữ biểu diễn, cấu trúc
biểu diễn, Vì các lược đồ thường được thiết kế bởi những 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. Dưới
đây chúng ta tìm hiểu và phân loại những khó khăn, thách thức gặp phải khi
nghiên cứu về giải pháp cho bài toán đối sánh lượ
c đồ.
Cho 2 cơ sở dữ liệu với hai lược đồ tương ứng S , T. Chúng ta phải xử lý để
tự động để xác định được sự tương ứng giữa phần tử category trong S với topic
trong T, và name trong S với org_name trong T, nghĩa là s trong S và t trong T
cùng mô tả chung một khái niệm trong một lĩnh vực nào đó thì chúng được coi là
tương đương. Điều này là một thách thức cho chúng ta vì một số yếu tố sau:
Lược đồ
• Ngữ nghĩa của các phần tử chỉ được suy diễn từ một số ít các thông tin như
người tạo, chú thích, các lược đồ và dữ liệu liên quan. Trích lọc ngữ nghĩa
4
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004

từ các thông tin như vây thực sự là bài toán khó vì những thông tin
metadata đó thường không được đầy đủ và chính xác, chú thích không đủ,
không phù hợp, trong nhiều trường hợp xây dựng các hệ thống tích hợp dữ
liệu qua Web những thông tin metadata đó còn không thể truy cập được.
• Do các phần tử của lược đồ thường được đối sánh dựa trên các thông tin hỗ

Hình 1-2: Xung đột ngôn ngữ
6
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004

3 Định nghĩa bài toán
Bài toán đối sánh lược đồ có thể được định nghĩa như sau: “Cho hai lược đồ
S
1
và S
2
hãy tìm sự tương đồng nhất giữa các phần tử của S
1
và S
2
bằng cách khai
thác tất cả các thông tin tồn tại như trong lược đồ, trong dữ liệu và các nguồn
thông tin hỗ trợ ”. Bài toán cần phải được giải quyết tới chừng nào có thể theo ý
nghĩa của sự tự động. Mục tiêu chính là giảm các thao tác thủ công nhiều nhất có
thể để tránh việc giải quyết bài toán đối sánh rất hỗn tạp.
3.1 Lược đồ.
Trong các thao tác đối sánh, các lược đồ đầu vào chỉ ra các phần tử cần
được đối sánh. Vì vậy ta cần xem xét một số loại lược đồ điển hình và các phần tử
của nó. Tùy thuộc vào lĩnh vực của ứng dụng lược đồ có thể tồn tại dưới nhiều
định dạng và ngôn ngữ khác nhau như SQL, UML, DTD, OWL.
• SQL (Structured Query Language): Định nghĩa lược đồ cho cơ sở dữ liệu
quan hệ
.
• XSD (XML Schema Definition): Định nghĩa cho các tài liệu có cấu trúc XML
để trao đổi qua môi trường Web.

<xsd:elementname=“firstname " type="xsd:string"/>
<xsd:elementname=“lastname" type="xsd:string"/>
<xsd:elementname=“birthday" type="xsd:string"/>
</xsd:sequence>
</xsd:complexType>
SQL
XSD

Hình 1-3: Lược đồ
3.2 Đầu vào bài toán (Input)
Bài toán đối sánh lược đồ bao gồm các loại thông tin đầu vào để có thể tính
toán mức độ tương đồng như sau.
• Thông tin lược đồ: Các thông tin như name, data type, description.
constraint
• Dữ liệu: Trong các ứng dụng tích hợp dữ liệu, chuyển đổi dữ liệu thì dữ liệu
luôn đi kèm với lược đồ và chúng cũng được khai thác để xác định ngữ
nghĩa cho các phần tử lược đồ.
• Thông tin h
ỗ trợ: Tất cả các loại thông tin khác mà chúng ta có thể khai
thác cho quá trình đối sánh lược đồ. Các thông tin hỗ trợ như từ điển đồng
nghĩa, domain …
3.3 Đầu ra bài toán (Output)
Với đầu vào là 2 lược đồ S
1
, S
2
bài toán cần đưa ra kết quả là một tập các
phần tử ánh xạ giữa 2 lược đồ đó, ta gọi các phần tử này là co-elenment. Mỗi co-
elenment được ánh xạ với một hoặc vài phần tử của S
1

Data integration/
Translation
Application/Tools
Data warehouse
Application/Tool
Sematic Web

Hình 1-4: Kiến trúc chung của bài toán đối sánh lược đồ
9
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004 Kiến trúc này tương thích với nhiều lĩnh vực ứng dụng khác nhauh cho
nhiều loại lược đồ khác nhau. Đầu vào của hệ thống là các lược đồ và các thông
tin hộ trợ việc đối sánh như: Từ điển, Ontology, Các hệ số tương tự giữa các kiểu
dữ liệu … Phần xử lý bao gồm các thao tác chuyển đổi biểu diễn của lược đồ
thành cấu trúc biểu diễn lượ
c đồ bên trong của hệ thống, có thể là dạng đồ thị.
Tiếp theo là các thuật toán đối sánh đối với các lược đồ đã được biểu diễn dưới
cấu trúc bên trong của hệ thống. Cuối cùng là kết quả đối sánh và các thao tác
xử lý kết quả đó như chuyển đổi định dạng biểu diễn, kết xuất cho các ứng dụng.
Các ứng dụng của hệ thống sau khi
đã có kết quả đối sánh bao gồm nhiều
lĩnh vực ứng dụng khác nhau như Tích hợp dữ liệu. chuyển đổi dữ liệu, Semantic
Web …
4 Ứng dụng của bài toán đối sánh lược đồ
Để nêu lên vai trò quan trọng của bài toán đối sánh lược đồ, chúng ta sẽ
xem xét một vài ứng dụng về cở sở dữ liệu để minh họa.
4.1 Các ứng dụng tích hợp dữ liệu và nhà kho dữ liệu

tổng hợp kết quả và trả lại cho nguời dùng.
Các ứng dụng chia sẻ dữ liệu trình bày ở trên đang xuất hiện rất nhiều
trong các lĩnh vưc hiện nay như thương mại điện tử, sinh học, và trong Ubicomp.
Internet đã mang lại hàng triệu nguồn dữ liệu và cần phải tạo khả năng chia sẻ
dữ liệu giữa chúng.
11
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004

Documents DB1
Documents DB2
Documents DB3
Data warehouse
Data transformation, data integration

Hình 1-6: Data warehouse
4.2 E-Business
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ý các giao dịch online của họ 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 (message) giữa các công ty. Thường thì mỗi một công ty phát triển một ứng
dụng với một định dạng message khác nhau như EDI (Electronic Data Exchange),
12
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004

XML hoặc bất kỳ định dạng nào. Để hệ thống trao đổi được các message đó, các
ứng dụng cần phải chuyển đổi được các message từ định dạng này sang định
dạng khác. Điều này chính là động lực cho bài toán đối sánh lược đồ phát triển để
chuyển đổi các message.

Mặc dù còn có nhiều các nghiên cứu hiệu quả trong bài toán đối sánh lược
đồ nhưng phần lớn các thao tác đối sánh vẫn được thực hiện thủ công bởi các
chuyên gia trong lĩnh vực làm việc của họ. Điều này xảy ra bởi vì các giải pháp tự
động hoặc bán tự động vẫn chưa thỏa mãn yêu cầu người dùng. Trong phần này
tôi trình bày một số vấn đề còn đang được nghiên cứu trong lĩnh vực đối sánh
lược đồ. Tuy nhiên tôi chỉ tổng hợp được một số các vấn đề qua các bài báo cũng
như các dự án nghiên cứu về lĩnh vực này. Những thông tìn tổng hợp này có thể
đủ hoặc không đủ về tất cả những nghiên cứu trước đây và hiện tại.
5.1 Khả năng biểu diễn của ngôn ngữ
Các ngôn ngữ biểu diễn lược đồ hiện đại như XML schema, SQL
(1999,2003) hỗ trợ rất nhiều khả năng mô hình hóa như các kiểu dữ liệu được
định nghĩa bởi người dùng, tổng hợp, suy diễn, tái sử dụng đối tượng, phân tán
và namespace… Các tính năng nâng cao này chính là dấu hiệu cho sự phức tạp
của bài toán đối sánh lược đồ. Hầu hết các kiểu thiết kế lược đồ có thể đượ
c sử
dụng như một sự lựa chọn để biểu diễn các khái niệm trong thế giới thực, nên
dẫn tới sự khác nhau về ngữ nghĩa, cấu trúc trong lược đồ. Vì vậy đối sánh lược
đồ với các lược đồ được biểu diễn bằng ngôn ngữ nâng cao đã trở thành một
thách thức vì nó phụ thuộc và khả năng hợp nhất của các kiểu thiết kế
khác
nhau.
5.2 Làm việc với các lược đồ có kích thước lớn
Các lược đồ trong thế giới thực ngày càng lớn về kích thước và độ phức tạp
để đương đầu với các yêu cầu về biểu diễn và quản lý dữ liệu. Hơn nữa các lược
đồ thường sử dụng các chung thành phần (shared element) để tránh các đặc tả
khác nhau và giữ cho lược đồ ở mức đơn giản nhất có thể phục vụ cho việc bảo trì
và vận hành được tốt h
ơn. Cuối cùng, các thao tác đối sánh cần kiểm tra trên một
14
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch


Hình 2-1: Kiến trúc COMA++

16
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004

1.2 SEMINT
SEMINT là hệ thống đối sánh lược đồ dựa trên dữ liệu (instance-based). 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
(content-based) đượ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 một không gian 20 chiều. Đối
sánh lược đồ bằng cách tạo các ánh xạ giữa các phần tử độc lập sử dụng mạng
neuron. SemInt không hỗ trợ đối sánh dự
a trên ngôn ngữ.
1.3 LSD
LSD (Learning source description) sử dụng phương pháp composite để kết
hợp các thuật toán đối sánh khác nhau. Nó dựa trên domain cụ thể của lược đồ
tổng thể để so sánh với các lược đồ mới được đối sánh. Học máy (machine
learning) được sử dụng cho các các thuật toán độc lập và kết hợp các kết quả.
Đối với đối sánh cho thuộc tính name, LSD sử dụng phương pháp đối sánh dựa
trên instance.
1.4 SKAT
SKAT (Semantic knowledge articulation tool) thực hiện đối sánh dựa trên
lược đồ (schema-based) sử dụng các luật. Các 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.
1.5 TransScm
TransScm sử dụng phương pháp schema-based để thực hiện việc chuyển
đổi dữ liệu. Lược đồ đầu vào (DTD hoặc OODB) được biểu diễn dưới dạng đồ thị.