Luận văn Đối sánh tự động lược đồ XML

c là duy nhất hoặc 
là khóa. 
- Sự kết hợp nội dung phần tử và các thuộc tính có thể được khai báo là duy nhất 
hoặc khóa, tức là không chỉ duy nhất mà luôn hiện diện và không rỗng. 
- Lược đồ XML phân biệt giữa duy nhất và khóa. 
- So sánh giữa các trường khóa tham chiếu và các trường khóa hoặc duy nhất là so 
sánh bằng nhau về giá trị mà không phải bằng nhau về xâu. 
Phụ lục 
Võ Sỹ Nam. Luận văn cao học – chuyên ngành công nghệ thông tin 
100
Phụ lục C: Thuật toán của Hirst và St-Onge 
1. Quan hệ từ 
Kỹ thuật đối sánh thuật ngữ đã đề xuất trong chương 3 sử dụng ba loại quan hệ: quan 
hệ rất mạnh (extra-strong) giữa một từ và sự nhắc lại nguyên thể của nó, quan hệ mạnh 
(strong): gồm một trong ba kịch bản đã giải thích trong mục 3.2.2 của chương 3 và quan 
hệ trung bình (medium), xảy ra khi có một đường dẫn được phép kết nối các synset liên kết 
với mỗi từ. Các định nghĩa của đường dẫn được phép sử dụng một phân loại các quan hệ 
synset WordNet thành các liên kết lên, xuống và ngang. 
Bảng C.1 sau đưa ra các ví dụ về các quan hệ synset WordNet và các hướng tương 
ứng của chúng. Còn hình C.1 sau các ví dụ về đường dẫn được phép cũng như không được 
phép. Dựa trên định nghĩa các đường dẫn được phép và lấy chiều dài lớn nhất của đường 
dẫn được phép bằng 4, ta phân biệt bảy trường hợp như minh họa trong hình C.2. 
Quan hệ Hướng 
Also see Horizontal 
Attribute Horizontal 
Cause Down 
Entailment Down 
Holonymy Down 
Hypernymy Up 
Hyponymy Down 
Meronymy Up 
Pertinence Horizontal 
Similarity Horizontal 
Bảng C.1 Phân loại các quan hệ trong WordNet thành các hướng 
Phụ lục 
Võ Sỹ Nam. Luận văn cao học – chuyên ngành công nghệ thông tin 
101
Hình C.1 Đường dẫn được phép và không được phép trong thuật toán của Hirst và St-Onge 
Hình C.2: Phân loại các quan hệ ngữ nghĩa trong WordNet 
0 
1 
1 
1 
1
5 
5 5 
5 5 5 
4 4 4 
3 3 3 3 
7 7 7 
2 
6 6 6 
2 
6 6 
2 
2
6 
Các nút trong đồ thị này mô tả các synset của 
các từ (word). Các quan hệ ngữ nghĩa giữa các 
từ được chai thành bốn loại: 
Tương đương (Equivalent): tồn tại một hay 
nhiều liên kết ngang giữa các synset của các từ 
(trường hợp 3). 
Rộng hơn (Broader than): tồn tại một hay 
nhiều liên kết lên giữa hai synset (trường hợp 
1) hoặc các liên kết lên theo sau là các liên kết 
ngang (trường hợp 5). 
Liên quan tới (Related-to): tồn tại một liên 
kết lên theo sau là một liên kết xuống và có thể 
là các liên kết ngang (hai từ có một từ bao 
(hypernym) chung) (trường hợp 4). 
Hẹp hơn (Narrower than): tồn tại một (hoặc 
nhiều) liên kết xuống giữa hai synset (trường 
hợp 2) hoặc một liên kết xuống theo sau bởi 
các liên kết ngang (trường hợp 6 và 7). 
Phụ lục 
Võ Sỹ Nam. Luận văn cao học – chuyên ngành công nghệ thông tin 
102
2. Thuật toán đối sánh thuật ngữ 
// Quan hệ rất mạnh 
if (word1=word2) return 24; 
else 
// Quan hệ mạnh 
S1=synsetsOf(word1); 
S2=synsetsOf(word2); 
foreach s1 in S1 
H1=horizontalSynsets(word1); 
U1=UpwardSynsets(word1); 
D1=DownwardSynsets(word1); 
foreach s2 in S2 
H2=horizontalSynsets(word2); 
U2=UpwardSynsets(word2); 
D2=DownwardSynsets(word2); 
if s1=s2 then return 16; 
if (s1 is In(H2) or s2 is In(H1)) return 16; 
if (s1 is In(U2) or s1 is In(D2)) return 16; 
if (s2 is In(U1) or s2 is In(D1)) return 16; 
endif 
// Quan hệ trung bình 
listOfWeight=medStrong(0,0,0,s1,S2); 
return (max(listOfWeight)); 
MedStrong (state, distance, chdir, from, To) 
if ((from is In(To) and (distance > 1)) 
// tìm thấy đường dẫn 
listOfWeigth.add(8-distance-chdir); 
return true; 
endif 
if (distance >= 5) 
// đường dẫn quá dài 
return false; 
endif 
if (state = 0) 
H=horizontalSynsets(from); 
U=UpwardSynsets(from); 
D=DownwardSynsets(from); 
retU=retD=retH=false; 
foreach u in U 
retU=retU or medStrong(1,distance+1,0,h, To); 
// thử đi lên (state =1) 
foreach d in D 
retD=retD or medStrong(2,distance+1,0,d, To); 
// thử đi xuống (state =2) 
foreach h in H 
retH=retH or medStrong(3,distance+1,0,d, To); 
// thử đi ngang (state =3) 
return (retU or retD or retH); 
endif 
if (state = 1) 
// thay đổi hướng đầu tiên là lên, sau đó có thể chuyển sang lên hoặc ngang 
H=horizontalSynsets(from); 
U=UpwardSynsets(from); 
D=DownwardSynsets(from); 
retU=retD=retH=false; 
foreach u in U 
retU=retU or medStrong(1,distance+1,0,h, To); 
// thử đi lên (state =1) 
foreach d in D 
retD=retD or medStrong(4,distance+1,1,d, To); 
// thử đi xuống (state =4) 
foreach h in H 
retH=retH or medStrong(5,distance+1,1,d, To); 
// thử đi ngang (state =5) 
return (retU or retD or retH); 
endif 
Phụ lục 
Võ Sỹ Nam. Luận văn cao học – chuyên ngành công nghệ thông tin 
103
if (state = 2) // đi xuống 
H=horizontalSynsets(from); 
D=DownwardSynsets(from); 
retD=retH=false; 
foreach d in D 
retD=retD or medStrong(2,distance+1,0,d, To); 
// thử đi xuống (state =2) 
foreach h in H 
retH=retH or medStrong(6,distance+1,0,d, To); 
// thử đi ngang (state =6) 
return (retD or retH); 
endif 
if (state = 3) // đi ngang 
H=horizontalSynsets(from); 
D=DownwardSynsets(from); 
retD=retH=false; 
foreach d in D 
retD=retD or medStrong(7,distance+1,0,d, To); 
// thử đi xuống (state =7) 
foreach h in H 
retH=retH or medStrong(3,distance+1,0,d, To); 
// thử đi ngang (state =3) 
return (retD or retH); 
endif 
if (state = 4) // đi lên hoặc xuống 
D=horizontalSynsets(from); 
retD=false; 
foreach d in D 
retD=retD or medStrong(4,distance+1,0,d, To); 
// thử đi ngang (state =4) 
return (retD); 
endif 
if (state = 5) // đi lên hoặc ngang 
H=horizontalSynsets(from); 
D=DownwardSynsets(from); 
retD=retH=false; 
foreach d in D 
retD=retD or medStrong(4,distance+1,2,d, To); 
// thử đi xuống (state =4) 
foreach h in H 
retH=retH or medStrong(5,distance+1,1,d, To); 
// thử đi ngang (state =5) 
return (retD or retH); 
endif 
if (state = 6) // đi xuống và ngang 
H=horizontalSynsets(from); 
retH=false; 
foreach h in H 
retH=retH or medStrong(6,distance+1,1,d, To); 
// thử đi ngang (state =6) 
return (retH); 
endif 
if (state = 7) // đi ngang và xuống 
D=horizontalSynsets(from); 
retD=false; 
foreach d in D 
retD=retD or medStrong(7,distance+1,1,d, To); 
// thử đi ngang (state =7) 
return (retD); 
endif 
 Danh mục tài liệu tham khảo 
[1] S. Amer-Yahia, S. Cho, D. Srivastava. Tree Pattern Relaxation, EDBT, 2002. 
[2] A. Budanitsky, G. Hirst. Semantic distance in WordNet: An experimental, 
application oriented evaluation of five measures, 2003. 
[3] D. Carmel, N. Efraty, G.M. Landau, Y.S. Maarek, Y. Mass. An Extension of 
the vector space model for querying XML documents via XML fragments. 
Second Edition of the XML and IR Workshop, In SIGIR Forum, Volume 36 
Number 2, Fall 2002. 
[4] G. Cobena, S. Abiteboul, A. Marian. Detecting changes in XML Documents. In 
ICDE, 2002. 
[5] H.H. Do, S. Melnik, E. Rahm. Comparison of schema matching evaluations. In 
Proceedings of the second International Workshop on Web Databases, 2002. 
[6] A.H. Doan. Learning to map between structured representations of data. PhD 
thesis, University of Washington, 2002. 
[7] Lexical chains as representations of context for the detection and correction of 
malapropisms. In: Christiane Fellbaum (editor), WordNet: An electronic 
lexical database, Cambridge, MA: The MIT Press, 1998. 
[8] ISO, Information Processing- Text and Office systems- Standard 
Generalization Markup Language (SGML), (ISO 8879:1986), International 
Organisation for Standardisation, Geneva, 1986. 
[9] P. Leinonen. Automating XML Document Structure Transformations. In 
Proceedings of the ACM Symposium on Document Engineering, France, 
2003. 
[10] G. Linden. Structured document transformations. Report A-1997-2. CS 
Department of University of Helsinki, Finland, 1997. 
[11] J. Madhavan, P.A. Bernstein, E. Rahm. Generic schema matching with Cupid. 
In Proceedings of the International Conference on Very Large Databases 
(VLDB), 2001. 
[12] S. Melnik, H. Garcia-Molina, E. Rahm. Similarity Flooding: A versatile Graph 
Matching Algorithm and its Application to Schema Matching. In Proceedings 
of the 18th International Conference on Data Engineering, 2002. 
[13] R. Miller. The Clio Project: managing heterogeneity. ACM SIGMOD Record 
30(1): 78-83, 2001. 
[14] A. G. Miller (1995). WordNet: A lexical Database for English. ACM 38 (11), 
pages 39-41, 1995. 
[15] Mong Li Lee, Liang Huai Yang, Wynne Hsu, Xia Yang. XClust: Clustering 
XML Schemas for Effective Integration, in 11th ACM International Conference 
on Information and Knowledge Management, McLean, Virginia, November 
2002. 
[16] E. Pietriga, J-Y. Vion-Dury, V. Quint. Vxt: a visual approach to XML 
transformations. In Proceedings of the ACM Symposium on Document 
Engineering, 2001. 
[17] E. Rahm and P.A. Bernstein. A survey of approaches to automatic schema 
matching. In VLDB Journal, pages 10: 334-350, 2001. 
[18] N. Routledge, L. Bird, A. Goodchild. UML and XML Schema, ADC, 2002. 
[19] D. Shasha, J. Wang, K. Zhang, and F. Shih. Fast algorithms for the unit cost 
editing distance between trees. In Journal of Algorithms, pages 581-621, 1990. 
[20] L. Xu. Source Discovery and Schema Mapping for Data Integration, PhD 
thesis, 2003. 
[21] L. Zamboulis. XML Schema Matching & XML Data Migration & Integration: 
A Step Towards The Semantic Web Vision. Technical Report, 2003. 
[22] A. Boukottaya. Schema Matching for Transforming Structured Documents. In 
DocEng'05, 2-4, 2005. 
[23] A. Vernet. XML transformation languages. Có thể xem tại: 
[24] XML Schema, W3C Recommendation, 2004. Có thể xem tại: 
[25] XML Schema Part 0: Primer, W3C Recommendation, 2004. Có thể xem tại: 
[26] XML Schema Part 1: Structures, W3C Recommendation, 2004. Có thể xem tại: 
[27] XML Schema Part 2: Datatypes, W3C Recommendation 2004. Có thể xem tại: 
[28] XSL Transformations (XSLT), W3C Recommendation, 2004. Có thể xem tại: