Chương 1 Mở đầu. 1
1 Đối sánh lược đồ.2
2 Sựhỗn tạp ngữnghĩa.3
3 Định nghĩa bài toán.6
3.1 Schemas.6
3.2 Đầu vào bài toán (Input).7
3.3 Đầu ra bài toán (Output).7
3.4 Kiến trúc chung .8
4 Ứng dụng của bài toán đối sánh lược đồ.9
4.1 Các ứng dụng tích hợp dữliệu và data warehouse.9
4.2 E-Business . 11
4.3 Semantic Web . 12
5 Các vấn đềmở. 13
5.1 Khảnăng biểu diễn của ngôn ngữ. 13
5.2 Làm việc với các lược đồcó kích thước lớn . 13
5.3 Sựkết hợp của các phương pháp đối sánh . 14
Chương 2 Các phương pháp tiếp cận . 15
1 Các dựán liên quan . 15
1.1 COMA++ . 15
1.2 SEMINT . 16
1.3 LSD . 16
1.4 SKAT. 16
1.5 TransScm . 16
1.6 DIKE . 17
1.7 SIMILARITY FLOODING. 17
1.8 Cupid . 17
2 Các phương pháp đối sánh lược đồ. 20
2.1 Tiêu chuẩn phân loại . 20
2.2 Đối sánh dựa trên schema (schema-based) . 21
2.2.1 Phương pháp tiếp cận dựa trên ngôn ngữ(linguistic). 22
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
3.1 Kiến trúc hệthống . 35
3.2 Input . 36
3.2.1 Schema .
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
5 Kết luận và hướng phát triển . 71
5.1 Kết luận . 71
5.2 Hướng phát triển . 72
Tài liệu tham khảo . 75
Sách, bài báo, luận văn. 75
Website .
85 trang |
Chia sẻ: maiphuongdc | Lượt xem: 1959 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Luận văn Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng vnmatch, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
), đối
sánh từng cặp của các phần tử đầu vào. Số cạnh của của đường dẫn ngắn nhất
giữa các phần tử được sử dụng như khoảng cách để xác định các phần tử liên
quan.
• Thuật toán tự động xác định quan hệ ngữ nghĩa
(synonymy,hypernymy,homonymy) giữa các phần tử của các lược đồ
ER.
1.7 SIMILARITY FLOODING
SIMILARITYFLOODING[10] chuyển đổi các lược đồ (Rational, RDF, XML)
vào trong một đồ thị gán nhãn và tính toán theo kiểu fix-point để xác định tương
ứng địa phương 1:1 và m:n giữa các node của đồ thị. Thuật toán sử dụng phương
pháp đối sánh hybrid với một bộ đối sánh đơn giản cho các thuộc tính name.
Không giống các phương pháp đối sánh dựa trên lược đồ khác,
SIMILARITYFLOODING không khai thác các quan hệ thuật ngữ trong các từ điển
ngoài như (synonym, wordnet …) mà chỉ dựa trên thuộc tính name. Thuật toán
chính được sử dụng trong SIMILARITYFLOODING là đối sánh dựa trên cấu trúc.
1.8 Cupid
Cupid [3] là hệ thống đối sánh kết hợp (hybrid) bao gồm kỹ thuật đối sánh
trên mức ngôn ngữ và cấu trúc. Thuật toán đối sánh lược đồ ánh xạ giữa các
phần tử của lược đồ dựa trên tên, kiểu dữ liệu, các ràng buộc, cấu trúc của lược
đồ và sự trợ giúp của từ điển đồng nghĩa. Cupid nhắm vào việc tính toán hệ số
tương tự giữa các các phần tử của 2 lược đồ và đưa ra sự ánh xạ từ các hệ số
này.
18
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ự động đối sánh dựa trên ngôn ngữ
• Đối sánh dựa trên cả phần tử và cấu trúc
• Hướng tới sự tương tự của các phần tủ nguyên tố (Ví dụ như các lá),
vì vậy ngữ nghĩa của lược đồ sẽ được thu nhận nhiều hơn
• Khai thác các khóa (key), các ràng buộn và các view
Đối sánh mức ngôn ngữ sẽ so sánh các phần tử của lược đồ một các độc
lập dựa trên tên, kiểu dữ liệu, lĩnh vực.. Chúng ta sẽ sử dụng một từ điển gần
nghĩa (thesaurus) để trợ giúp việc so sánh các name bằng cách xác định các từ
rút gọn, các từ viết tắt, và các từ đồng nghĩa.
Đối sánh ngôn ngữ trong Cupid được chia thành 3 bước sau:
1. Chuẩn hoá (Normalization): Trong bước này chúng ta chuẩn hoá phần tử,
phân tích phần tử bằng cách tokenization (phân tích các phần tử dựa trên
dấu chấm câu, chữ hoa, chữ thường ...). Trong bước này ta sử dụng từ
điển đồng nghĩa
2. Phân loại theo các phần tử (Categorization): Các phần tử của lược đồ được
phân loại thành các nhóm khác nhau, sự phân loại này được dựa trên kiểu
của dữ liệu (datatype), tên của thuộc tính (name). Một phần tử có thể
thuộc nhiều loại.
3. So sánh (Comparison): Trong bước này sẽ tính toán một hệ số gọi là hệ số
tương tự về ngôn ngữ giữa các phần tử (linguistic similarity-ls).
Kết quả của pha này là một bảng các hệ số lsim của các phần tử giữa hai
lược đồ. Hệ số lsim nằm trong khoảng [0,1]. Nếu lsim = 1 thì hai phần tử
hoàn toàn tương đương nhau.
Để so sánh độ tương tự của hai chuỗi đầu vào dựa trên phân tích token,
Cupid sử dụng công thức sau.
19
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
Công thức 1: Cupid, hệ số tương tự của hai tập hợp
21
)2,1(*)11(22
max)2,1(*)22(11
max
)2,1( TT
ttsimTtTtttsimTtTt
TTns +
∈∑ ∈+∈∑ ∈=
Chú thích:
Các thuộc tính được phân tích thành các từ (word) hay token, ta có một
tập các token để biểu diễn các phần tử của lược đồ
1.Chọn một token từ phần tử thứ nhất
2.Tìm kiếm token giống nhất với token đã cho.
3.Thực hiện 1) và 2) đối với mọi token của phần tử thứ nhất và
tính tổng độ giống nhau.
4. Thực hiện 1) 2) 3) cho phần tử thứ 2
5.Chuẩn hóa 2 tổng với tổng số token của phần tử thứ nhất và
thứ hai
Đánh giá theo category
Cho w1 … w2 là hệ số ưu tiên theo category với 1=∑ iw
Công thức 2: Cupid, đánh giá theo Category
∑
∈
=
TokenTypei
iTiTnsiwAAns )2,1(.)2,1(
Cuối cùng ta có công thức tính hệ số tương tự giữa hai thuộc tính
Công thức 3: Cupid, công thức tính lsim
),(max).,(),( 21,2121 21
TTnsAAnsAAlsim
CTT ∈
=
Đây là công thức cho ra kết quả cuối cùng của đối sánh dựa trên ngôn ngữ.
20
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
2 Các phương pháp đối sánh lược đồ
Đã có rất nhiều các nghiên cứu trong nhiều lĩnh vực khác nhau như chuyển
đổi và tích hợp lược đồ (schema translation, schema integration), biểu diễn tri
thức, học máy và các hệ thống thu thập thông tin nhắm tới mục đích tự động quá
trình đối sánh lược đồ nhiều nhất có thể. Mục đích của phần này giới thiệu các
phương pháp tiếp cận trong các lĩnh vực đó, các đặc điểm chung và ứng dụng của
nó.
Trong phần tiếp theo, tôi trình bày các tiêu chí phân loại cho bài toán đối
sánh lược đồ được tham khảo trong [6].
2.1 Tiêu chuẩn phân loại
Bài toán đối sánh lược đồ đã được nghiên cứu trong một thời gian dài, và
đã có nhiều ứng dụng cụ thể áp dụng bài toán này.
Hình 3 minh họa các phương pháp đối sánh lược đồ đã được nghiên cứu và phát
triển trong các ứng dụng cụ thể.
Hình 2-2: Các phương pháp đối sánh lược đồ
21
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 ta 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
• Schema-based ›‹ Instance-based: Schema-based chỉ sử dụng các
thông tin chứa trong lược đồ như metadata, name, type, description... Còn
Instance-based sử dụng dữ liệu để trích lọc ngữ nghĩa (contents)
• Element-based ›‹ Structural-based: Element-based là quá trình đối
sánh có thể thực hiện trên từng phần tử trong lược đồ một cách độc lập, ví
dụ như các thuộc tính (attributes). Structural-based thực hiện đối sánh có
sự kết hợp các phần tử lại với nhau.
• Linguistic ›‹ Constraint: Đối sánh có thể sử dụng cách tiếp cận ngôn ngữ
như so sánh các thuộc tính name, description .. hoặc sử dụng cách tiếp cận
ràng buộc như xem xét cả ràng buộc định nghĩa trên các phần tử như kiểu
dữ liệu, unique, key…
• Hybrid ›‹ Composite: Để có một kết quả đối sánh tốt hơn người ta
thường kết hợp một vài cách tiếp cận 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 hybrid hoặc kết hợp các kết quả
đối sánh của các cách tiếp cận độc lập (composite)
2.2 Đối sánh dựa trên lược đồ (schema-based)
Phương pháp đối sánh dựa trên lược đồ chỉ xem xét các thông tin về lược
đồ, tùy thuộc vào việc sử dụng ngôn ngữ định nghĩa lược đồ các ta có các thuộc
tính khác nhau của phần tử lược đồ như name, description, data type,
constraints, .. và các quan hệ giữa chúng. Tiếp theo tôi trình bày về bộ đối sánh
dựa trên ngôn ngữ và ràng buộc, phương pháp tiếp cập chung đối với mức
element để so sánh các thuộc tính của các phần tử lược đồ để xác định độ tương
đồng giữa chúng.
22
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
2.2.1 Phương pháp tiếp cận dựa trên ngôn ngữ (linguistic)
Phương pháp này chủ yếu xem xét các thuộc tính dạng chuỗi ký tự của các
phần tử lược đồ như name, description.Thuộc tính name có thể được so sánh qua
2 dạng là cú pháp (syntactic) và ngữ nghĩa (semantic).
Đối sánh thuật ngữ name dựa trên cú pháp là tính toán độ tương đồng chỉ
dựa trên các chuỗi biểu diễn name. Có nhiều thuật toán đã được phát triển ứng
dụng cho các lĩnh vực khác như sửa lỗi chính tả (spelling correction), thu thập
thông tin … Trong đó đặc biệt 3 thuật toán sau: EditDistance, N-Gram, SoundEx
đã được áp dụng vào bài toán đối sánh lược đồ.
• EditDistance (Levenstein):Sử dụng kỹ thuật quy hoạch động, độ tương
đồng của 2 chuỗi được tính từ số lần thực hiện các thao tác: xóa, thêm,
thay thế của một ký tự cần thiết để chuyển một chuỗi này thành chuỗi kia.
• N-Gram: Chuỗi được so sánh theo tập n-gram của nó. Ví dụ chuỗi doc và
document là tương tự theo tập tri-gram, {doc} và
{doc,ocu,cum,ume,men,ent} chia sẻ phần tử doc.
• SoundEx: Phương pháp này tính độ tương đồng âm giữa các name tương
ứng với mã SoundEx. Phương pháp này hiệu quả cho các từ được viết khác
nhau có khả năng giống nhau,ví dụ document, documentation.
Đối sánh dựa trên ngữ nghĩa sử dụng các quan hệ về mặt thuật ngữ để ước
lượng độ tương đồng giữa các name như synonymy, hypernymy, hyponymy. ví dụ
từ Car và automobile là đồng nghĩa nên tương tự nhau. Cách tiếp cận này cần trợ
giúp của các thông tin hỗ trợ như từ điển, thesaurus, ontology hoặc các bảng định
nghĩa từ đồng nghĩa cho các ngôn ngữ khác nhau.
Ngoài ra trên thực tế các lược đồ còn có nhiều sự hỗn tạp mà chúng thường gặp
như:
• Từ được ghép bởi nhiều từ khác: Ví dụ Org_Sender.
• Từ được viết gọn lại: Ví dụ Org có nghĩa là Organization.
• Từ có nhiều nghĩa.
23
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
2.2.2 Phương pháp tiếp cận dựa trên ràng buộc
Các lược đồ thường chứa các thông tin ràng buộc như size, data type, key,
range, unique… cho mỗi phần tử. Nếu các thông tin này xuất hiện trong cả hai
lược đồ thì nó sẽ được khai thác để ước lượng độ tương đồng. Ví dụ có thể tính
toán độ tương đồng giữa hai phần tử dựa trên data type, key…
Đối với các thông tin này, cách tiếp cận chung là tạo một bảng trong đó chứa hệ
số tương tự của các ràng buộc. Ví dụ như kiểu String và kiểu varchar là hoàn toàn
tương tự nhau.
2.2.3 Phương pháp tiếp cận dựa trên cấu trúc
Phương pháp tiếp cận này khai thác các quan hệ giữa các phần tử và đối
sánh kết hợp các phần tử xuất hiện trong cùng một cấu trúc. Phụ thuộc vào các
ngôn ngữ mô tả lược đồ khác nhau mà có các kiểu quan hệ giữa các phần tử khác
nhau. Ví dụ như các quan hệ is-a/part-of, hoặc các ràng buộc tham chiếu. Thông
thường lược đồ được biểu diễn dưới dạng đồ thị (có hướng hoặc vô hướng). Để
xác định độ tương đồng giữa các phần tử người ta thường sử dụng khái niệm
phần tử hàng xóm (element neighborhood) để hạn chế phạm vi khi so sánh các
phần tử.
2.3 Đối sánh dựa trên dữ liệu
Phương pháp này duyệt qua các bản ghi dữ liệu để xác định sự tương ứng
và được chọn khi các thông tin trong lược đồ bị giới hạn hoặc trong trường hợp dữ
liệu được biểu diễn dưới dạng bán cấu trúc. Trong trường hợp đặc biệt không có
lược đồ người ta phải xây dựng nó từ các dữ liệu đã có, trường hợp này người ta
phải sử dụng các kỹ thuật được gọi là trích lọc lược đồ. Ngay cả khi có lược đồ thì
thông tin về dữ liệu cũng có thể được xem xét để tăng khả năng khai thác ngữ
nghĩa trong lược đồ
Đối với phương pháp này, kích thước dữ liệu đầu vào bài toán lớn hơn
nhiều so với lược đồ nên thời gian thực hiện đối sánh cũng là một trong những
vấn đề cần quan tâm.
24
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
2.4 Đối sánh kết hợp
Đối sánh chỉ sử dụng một phương pháp tiếp cận sẽ không thích hợp để cho
ra một kết quả tốt với sự đa dạng của lược đồ. Vì vậy hầu hết các hệ thống đối
sánh lược đồ hiện tại đều kết hợp sử dụng nhiều phương pháp đối sánh. Đối sánh
kết hợp có thể được thực hiện theo hai cách khác nhau là hybrid hoặc composite.
Hybrid tích hợp nhiều cách tiếp cận vào trong engine trong khi composite kết hợp
kết quả của nhiều cách tiếp cận độc lập lại với nhau. Trong hầu hết các hệ thống
có sử dụng đối sánh lược đồ đều sử dụng đối sánh kết hợp (Cupid)
2.5 Match Cardinality
Kết quả đối sánh giữa hai lược đồ S1 và S2 là tập các co-element giữa các
phần tử của nó, một phần tử S1 (S2) có thể tồn tại trong nhiều co-element. Hơn
nưa, một hay nhiều phần tử S1 có thể tương đương với một hoặc nhiều phần tử
của S2. Vì vậy chúng ta có các quan hệ về số lượng 1:1. 1:n, n:1, m:n .
Cardinality s (S1) t (S2)
1:1 Price Cost Price=Cost
n:1 FirstName,
LastName
Name Concat(FirstName,
LastName) = Name
1:n Name FirstName,
LastName
Split(Name) =
{FirstName, LastName}
m:n P.PersName,
P.DeptNoD.DeptNo,
D.DeptName
A.Person,
A.Department
SELECT P.PersName,
D.DeptNameFROM P, D
WHERE
P.DeptNo=D.DeptNo =
{A.Person,
A.Department}
Bảng 1: Đối sánh dựa trên số lượng phần tử
25
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
2.6 Các hệ số mặc định trong bài toán đối sánh
Trong các phương pháp đối sánh đã trình bày ở trên trong các dự án cụ thể
đều có sử dụng các hệ số mặc định để chỉ ra sự tương tự giữa các phần tử theo
các tiêu chí đặc biệt. Ví dụ bảng hệ số tương tự giữa các phần tử khi so sánh các
kiểu dữ liệu của chúng với nhau, với tiêu chí này người ta không xây dựng bất cứ
thuật toán nào mà thường sử dụng các hệ số được định nghĩa sẵn. Ngoài ra còn
các hệ số mặc định để chỉ ra độ ưu tiên của một thuật toán so với thuật toán
khác, ví dụ độ ưu tiên của mức ngôn ngữ so với độ ưu tiên của mức cấu trúc.
Type(s) Type(t) Datatype_match(s,t)
string string 1.0
string date 0.2
decimal float 0.8
float float 1.0
float integer 0.9
… … …
Có một số phương pháp để xây dựng bảng hệ số như trên nhưng phương
pháp thường được các chuyên gia sử dụng là dựa vào thực nghiệm. Quá trình xây
dựng các hệ số được thực hiện theo các bước sau:
1. Thực hiện đối sánh bằng tri thức chuyên gia, được kết quả là một tập hợp
các ánh xạ giữa các phần tử của hai lược đồ Sexp kết quả thực tế mà bài
toán cần hướng tới).
2. Thực hiện đối sánh tự động với hai lược đồ và cũng thu được tập hợp các
ánh xạ giữa các phần tử của hai lược đồ Sauto.
3. Sẽ có sự khác nhau giữa tập hợp ánh xạ do chuyên gia và tập ánh xạ do
máy thực hiện. Các hệ số Wdefault sẽ được điều chỉnh sao cho tập Sauto giống
với tập Sexp nhất có thể.
26
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
Hình 2-3: Xây dựng các hệ số ưu tiên
Các hệ số thu được có thể được áp dụng cho nhiều bài toán khác nhau,
thuật toán khác nhau.
3 Các phương pháp đánh giá hệ thống đối sánh
Để đánh giá kết quả của các hệ thống đối sánh lược đồ chúng ta có thể sử
dụng các phương pháp sau đây
1. So sánh kết quả đối với kết quả đối sánh của các chuyên gia. Đây là một
phương pháp khá hiệu quả và nó thường được sử dụng để xây dựng các hệ
số ưu tiên trong các thuật toán đối sánh. Các hệ số được điều chỉnh sao
cho kết quả tự động bằng máy với kết quả của chuyên gia giống nhau
nhất. Thực hiện với nhiều lược đồ sẽ thu được các hệ số thực nghiệm tối ưu
nhất.
2. So sánh kết quả đối sánh với kết quả của các hệ thống khác.
3. Đánh giá tự động: Ký hiệu B là tập các ánh xạ đúng (ánh xạ đúng là ánh
xạ do chuyên gia thực hiện), C: Tập các ánh xạ sai, A tập ánh xạ đúng
27
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
nhưng không được thuật toán tìm thấy và D là tập ánh xạ sai được thuật
toán loại bỏ
Hình 2-4: Đánh giá hệ thống đối sánh
Ta có hai công thức sau để ước lượng hiệu quả của thuật toán đối sánh
• Cho biết sự tin cậy của thuật toán đối sánh
Precision=
CB
B
+ ,
• Cho biết phần trăm của các ánh xạ hợp lệ (có giá trị)
Recall=
AB
B
+
Khi tập A và tập C không tồn tại thì Precision và Recall có giá trị 1. Tuy
nhiên một giá trị Recall hoặc Precision thì không thể ấn định được chất lượng của
thuật toán đối sánh.
Như vậy cần phải xem xét các phương pháp kết hợp hai giá trị trên đối lại
với nhau. Có một số phương pháp kết hợp đã được xây dựng sau
1. FMeasure(α ) được mô tả trong [9]:
FMeasure(α )=
recallprecision
recallprecision
CBA
B
**)1(
*
**)1( αααα +−=++−
Trong đó 0<α <1 cho phép các giá trị thể hiện sự quan trọng khác nhau
đối với Precision và Recall. FMeasure(α ) hội tụ về Precision khi α =1 và hội tụ về
Recall khi α =0
28
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
2. FMeasure : Khi Precision và Recall được xem có độ quan trọng bằng nhau
ta có công thức sau
FMeasure=
recallprecision
recallprecision
CBBA
B
+=+++
**2
*2
3. Overall: Đây là công thức được nêu trong [10] và công thức này được
nhắm vào chính các ứng dụng đối sánh lược đồ
Overall= )12(*1
precision
recall
BA
CB
BA
CA −=+
−=+
+−
Để so sánh hai phương pháp FMeasure và Overall ta có hình sau. Nhìn vào
đồ thị ta thấy FMeasure tối ưu hơn so với Overall. Với cùng giá trị của Precision
và Recall thì FMeasure cao hơn so với Overall. Overall nhạy cảm với biến
Precision hơn. Khi Precision=0,5 thì Overall=0;
Hình 2-5: So sánh F-Measure và Overall
29
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
30
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 3 Thiết kế hệ thống đối sánh lược đồ.
1 Khảo sát
Hiện nay các công ty, tổ chức đều có các cơ sở dữ liệu chưa các thông tin
quản lý, tác nghiệp điều hành. Đối với các công ty, hoặc các tổ chức có qui mô
lớn, dữ liệu phân tán trên cả mặt logic và vật lý. Các tổ chức này thường dùng
các hệ quản trị cơ sở dữ liệu và hệ thống phần mềm khác nhau để quản lý cơ sở
dữ liệu, điều này dẫn đến việc tích hợp dữ liệu các cơ sở dữ liệu này thành một
thể thống nhất gặp rất nhiều khó khăn vì sự hỗn tạp của dữ liệu.
Các hệ thống cơ sở dữ liệu thường được dùng bao gồm: Lotus notes, MS
SQL Server, Oracle, MySQL. Trong hình dưới đây minh họa sự hỗn tạp của các
nguồn dữ liệu văn bản, đây là một mô hình đang được áp dụng trong các tổ chức
ở Việt Nam hiện nay.
31
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
Organization 3Organization 2Organization 1
Domino SQL server Oracle
Schema1 Schema2 Schema3
E-docman
App
E-docman
App
E-docman
App
Mediator
Local schemaLocal schema
Global schema
Query Result
Hình 3-1: Sự hỗn tạp của các nguồn dữ liệu
Hiện tại nhu cầu về bài toán tích hợp dữ liệu (Data integration) hoặc
chuyển đổi dữ liệu (Data translation) một cách tự động hoặc bán tự động là thực
sự cần thiết. Trên thực tế các công ty hay tổ chức hiện nay khi xây dựng các ứng
dụng có sử dụng dữ liệu đã có sẵn thì thường phải xây dựng một công cụ với các
thao tác thủ công (manual) để tiến hành chuyển đổi hoặc tích hợp dữ liệu cũ vào
ứng dụng mới. Những thao tác thủ công sẽ không lợi ích về mặt kinh tế cũng như
32
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
quá trình xử lý sẽ xuật hiện các lỗi thao tác bằng tay. Như vậy người ta cần phải
xây dựng các mô hình tự động hoặc bán tự động cho bài toán này để giảm thiểu
tối đa các thao tác thủ công.
33
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
2 Giới thiệu
Trong hình dưới đây là hai lược đồ về cơ sở dữ liệu văn bản. chúng ta có
thể nhận ngay ra các xung đột trong hai lược đồ này. Vấn đề đặt ra bây giờ là xử
lý các xung đột đó một cách tự động nhiều nhất các thao tác có thể.
Hình 3-2:Lược đồ văn bản
2.1 Giới thiệu bài toán đối sánh lược đồ.
Đối sánh (Match) là thao tác xử lý 2 lược đồ đầu vào và cho đầu ra một
ánh xạ các phần tử phù hợp giữa hai lược đồ. Đối sánh lược đồ là bước khó trong
nhiều ứng dụng: Trong Thương mại điện tử, trợ giúp ánh xạ các message giữa
các định dạng XML khác nhau, trong Datawarehouse, giúp ánh xạ dữ liệu nguồn
vào trong các lược đồ của Warehouse…
2.2 Xử lý lược đồ trong tiếng Việt
Trên thực tế trong các ứng dụng về cơ sở dữ liệu ở Việt Nam hiện nay, có
rất nhiều các lược đồ được thiết kế sử dụng tiếng Việt, các thuộc tính định danh
(identify name) thường sử dụng tiếng Việt không dấu để biểu diễn, còn các các
mô tả thuộc tính có thể là tiếng Việt có dấu hoặc không có dấu. Ngoài ra các lược
đồ này còn kết hợp cả tiếng Anh, như vậy việc xử lý các lược đồ này còn gặp rất
34
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
nhiều khó khăn do có quá nhiều các xung đột về ngữ nghĩa, từ vựng, sự hạn chế
của các giải thuật xử lý ngôn ngữ cho tiếng Việt …
Dựa trên những thuật toán xử lý cho các thứ tiếng khác ta cũng hoàn toàn có thể
xây dựng được thuật toán xử lý cho tiếng Việt, nếu ta có được các bộ từ điển như
tiếng Anh.
Tôi đề xuất một vài phương pháp tiếp cận cho tiếng Việt trong bài toán đối sánh
lược đồ có thể sử dụng trong đối sánh ngôn ngữ
1. Nếu ta xây dựng được một từ điển phân loại (taxonomy) giống như
Wordnet3 cho tiếng Việt, chúng ta hoàn toàn có thể thực hiện các thuật
toán đối sánh như trong tiếng Anh. Có thể xem một trong những thuật
toán này tại đây4
2. Ngoài ra ta cũng có thể xây dựng một thuật toán kết nối đến từ điển Việt
– Anh để xử lý. Quá trình sẽ được thực hiện như sau: Kết nối đến từ điển
và tìm các từ tiếng Anh tương ứng và sau đó sử dụng các thuật toán cho
tiếng Anh.
Sử dụng các phương pháp trên tất nhiên chúng ta phải có một bộ phân tích
cú pháp cho tiếng Việt, nghiên cứu sinh Lê Hồng Phương 5 đang phát triển dự án
vnLTAG6 cho tiếng Việt mục đích để xây dựng một văn phạm LTAG cho tiếng Việt.
Trước đó tác giả này đã xây dựng công cụ vnTokenizer để xử lý ngôn ngữ tiếng
Viêt có chức năng tact từ tiếng Việt tự động và phân loại chúng.
3
4
5 Doctorant, Equipe Langue et Dialogue, LORIA,INRIA Lorraine, 615 rue du Jardin
Botanique, lehong@loria.fr
6
35
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 Thiết kế
Trong phần này tôi trình bày về kiến trúc của hệ thống đối sánh lược đồ và
các bước thực hiện. Ý tưởng của hệ thống này là sử dụng đối sánh kết hợp
(compostion), sử dụng tổng hợp
3.1 Kiến trúc hệ thống
Kiến trúc của hệ thống đối sánh lược đồ của DocMatcher được mô tả trong
hình sau. Hệ thống bao gồm các module sau với sự hỗ trợ của giao diện đồ hoạ
trên nền Window:
• Xử lý thông tin đầu vào (input)
• Đối sánh với các thuật toán
• Tổng hợp kết quả
• Kết xuất thông tin ra
36
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
Hình 3-3: Kiến trúc hệ thống
3.2 Input
Đầu vào của hệ thống bao gồm các lược đồ cần đối sánh và các nguồn
thông tin hỗ trợ việc đối sánh.
3.2.1 Lược đồ
XSD là một trong những ngôn ngữ biểu diến lược đồ mạnh nhất và được
ứng dụng rộng rãi trong nhiều lĩnh vực. Vì vậy XSD được lấy làm ví dụ để minh
hoạ cho đầu vào của hệ thống đối sánh. Các tài liệu XML schema (XSD) được
phân tích và xử lý để chuyển đổi sang dạng đồ thị có hướng. Các ngôn ngữ biểu
diễn lược đồ khác như XML DTD hay SQL (ví dụ SQL-92) cũng có thể áp dụng
phương pháp mô hình hoá với XSD.
XSD có nhiều cách thiết kế mà chúng ta cần xem xét để phân tích các vấn
đề xung đột.
37
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. XSD Schema có thể được thiết kế theo kiểu phân tán hoặc nguyên khối,
thường thì các lược đồ được thiết kế theo cách truyền thống là tất cả các
thành phần được gộp vào chung một tài liệu. Tuy nhiên đối với các lược đồ
có kích thước lớn, đặc biệt là trong các ứng dụng Web Lược đồ được tách
thành nhiều tài liệu và các namespace khác nhau. Ví dụ các tài liệu XSD có
thể sử dụng các cú pháp include, redefine, import để tích hợp các tài liệu
với nhau.
2. Kiểu thiết kế Composition và Deviration: Một vài ngôn ngữ như XSD và
ngôn ngữ SQL mở rộng cho hướng đối tượng hỗ trợ việc định nghĩa kiểu rất
linh hoạt (user-defined types) cho các phần tử và thuộc tính. Các kiểu mới
có thể xây dựng dựa theo phương pháp composition hoặc derivation. Theo
phương pháp composition thì kiểu mới có thể xây dựng dựa trên các phần
tử và thuộc tính đã tồn tại. Theo phương pháp derivation thì các kiểu mới
được xây dựng bằng cách thừa kế các một kiểu cơ sở và các thuộc tính của
nó.
3. Phương pháp khai báo inline và khai báo chia sẻ: Khai báo inline là các
phần tử được khai báo kiểu ngay trong phạm vi khai báo của phần tử đó,
còn khai báo theo kiểu chia sẻ là định nghĩa ra các kiểu chung rồi các phần
tử có chung một kiểu sử dụng các kiểu chung đó.
Phân tích lược đồ đầu vào là một trong những bước quan trọng của bài
toán đối sánh.Các bước chuyển đổi từ lược đồ đầu vào thành đồ thị có hướng bao
gồm các bước sau:
1. Hợp nhất các thiết kế: Để dễ dàng điều khiển, các lược đồ được phân tích
và hợp nhất thành một lược đồ.
38
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
Hình 3-4: Hợp nhất các lược đồ phân tán
2. Hợp nhất các các kiểu thiết kế: Composition là phương pháp chung để xây
dựng kiểu, kiểu thừa kế (derivation) được chuyển thành kiểu composition
Hình 3-5: Hợp nhất các kiểu thiết kế lược đồ
Các file đính kèm theo tài liệu này:
- 000000208321R.pdf