CHUYỂN ĐÔI DỮ LIỆU GIỮA XML

VÀ CƠ SỞ DỮ LIỆU QUAN HỆ














DANH MỤC TỪ VIẾT TẮT 2
MỘT SỐ THUẬT NGỮ 3
Mở đầu 4
Chƣơng I: KHÁI NIỆM XML VÀ MÔ HÌNH DỮ LIỆU QUAN HỆ 6
1.1 TÀI LIỆU XML 6
1.1.1 Giới thiệu XML và ngôn ngữ định dạng 6
1.1.2 Trình soạn thảo XML (XML Editors) và trình duyệt XML 10
1.1.3 Bộ phân tích XML và Bộ kiểm tra XML (XML Validator) 10
1.1.4 CSS và XSL 11
1.1.5 Xây dựng tài liệu XML hợp khuôn dạng 11

1.1.6 Định nghĩa kiểu tài liệu (DTD) 12
1.1.7 Giới thiệu về Xpath 13
1.1.8 Mô hình đối tƣợng dữ liệu DOM 16
1.1.9 XML và cơ sở dữ liệu 17
1.2 MÔ HÌNH DỮ LIỆU QUAN HỆ 18
1.2.1 Các khái niệm cơ bản [3][4][5] 18
1.2.2 Các phép toán trên quan hệ [4][5] 20
1.3 KẾT LUẬN 23
Chƣơng II:THUẬT TOÁN CHUYỂN ĐỔI DỮ LIỆU GIỮA TÀI LIỆU XML VÀ CSDL QUAN HỆ . 24
2.1 CHUYỂN ĐỔI XML SANG CSDL QUAN HỆ 24
2.1.1 Đơn giản hoá đặc tả DTD 27
2.1.2 Cơ sở của các thuật toán chuyển đổi lƣợc đồ XML sang lƣợc đồ CSDL quan hệ 28
2.1.3 Thuật toán gộp cơ sở (Basis Inlining) 29
2.1.4 Thuật toán gộp chia sẻ (Shared Inlining) 33
2.1.5 Thuật toán gộp cải tiến 35
2.1.5.1 Đơn giản hoá DTD 36
2.1.5.2 Tạo lập và giản lƣợc đồ thị DTD 37
2.1.5.3 Sinh lƣợc đồ quan hệ 41
2.1.6 Thuật toán Xinsert-Ánh xạ dựa trên hƣớng tiếo cận DOM 46
2.1.7 Thuật toán CPI (Constraint-Preserving Inlining) 53
2.1.7.1. Ánh xạ DTD sang lƣợc đồ quan hệ 54
2.1.7.2. Các ràng buộc ngữ nghĩa trong DTD 60
2.1.7.3. Phát hiện và bảo toàn các ràng buộc ngữ nghĩa 63
2.2 CHUYỂN ĐỔI CSDL QUAN HỆ SANG XML 69
2.2.1 Chuyển đổi phẳng (Flat Translation) 73
2.2.2 Chuyển đổi lồng(Nesting base Traslation) 74
2.2.3 Thuật toán CoT (Chuyển đổi sử dụng các phụ thuộc bao hàm) 79
2.2.3.1. Một khoá ngoại giữa hai bảng 79
2.2.3.2. Hai khoá ngoại giữa ba bảng 81
2.2.3.3. Lƣợc đồ quan hệ tổng quát 82

Chƣơng III: CHƢƠNG TRÌNH ỨNG DỤNG 88
3.1 THUẬT TOÁN GỘP CẢI TIẾN VÀ XINSERT 88
3.1.1 Mô tả bài toán 88
3.1.2 Chƣơng trình DEMO 90
3.1.3 KẾT LUẬN 94
PHẦN KẾT LUẬN 96
PHỤ LỤC 99
TÀI LIỆU THAM KHẢO 99
73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91
92 93 94 95 96 97 98 99 100 99


DANH MỤC TỪ VIẾT TẮT
CSDL
Cơ sở dữ liệu
RDB
Relational Database
XML
eXtensible Markup language
HTML
HyperText Markup Language
SGML
Standard Generalized Markup Language
W3C
World Wide Web Consortium
DTD
Document Type Definition
DOM
Document Oject Model
SAX

Simple API for XML
CSS
Cascading Style Sheets
XSl
Extensible Style Sheet Language
API
Application Progaramming Interfaces
DDL
Data definition Language
DML
Data Manipulation Language
CPI
Constraint- Preserving Inlining
ID
Inclusion Dependencies
FD
Function Dependency
EGD
Equality –Generating
TGD
Tuple-generating Dependencies
FT
Flat translation
NeT
Nesting-base Translation
CoT
Constraint Translation
IND
Inclusion Defendencies







MỘT SỐ THUẬT NGỮ
Basic Inlining
Gộp cơ sở
Share Inlining
Gộp chia sẻ
New Inlining
Gộp cải tiến
Hybrid Inlining
Gộp lai ghép
DTD MAP Schema
Lược đồ ánh xạ DTD
XML Document
Tài liệu XML
Cardinality Operator
Toán tử lực lượng
XML Processor
Trình phân tích XML
Element nodes
Nút phân tử
Integrity constraint
Rằng buộc toàn vẹn
Set-value attribute
Thuộc tính có giá trị tập hợp
Relational keys
Khoá quan hệ

Relational recurive processing
Tiến trình đệ quy quan hệ
Element graph
Đồ thị các phần tự
Inlinable tree
Cây có thể gộp
Singteton constraint
Ràng buộc đơn
Equality- generating dependencies
Phụ thuộc sinh đồng nhất
Child constraint
Ràng buộc con
Parent constraint
Ràng buộc cha







Mở đầu
Hầu hết các dữ liệu thương mại được lưu trữ và duy trì trong
các hệ quản trị dữ liệu quan hệ và được dự báo vẫn là phương thức
lưu trữ dữ liệu trong tương lai. Các hệ thống này cung cấp cho người
sử dụng cách truy cập dữ liệu hiệu quả và đáng tin cậy trong một tổ
chức. Tuy nhiên, tốc độ phát triển mạnh mẽ của thương maị điện tử
và nhu cầu chuyển và nhận dữ liệu từ khách hàng cũng như các tổ
chức khác qua Internet đồng nghĩa với việc một số dữ liệu cần được
giải thoát khỏi mô hình giới hạn này. XML[1][2][10] đang nổi lên

như một tiêu chuẩn vượt trội để mô tả và trao đổi dữ liệu, do vậy các
cơ chế để chuyển đổi dữ liệu đuợc lưu trữ trong hệ quản trị cơ sở dữ
liệu quan hệ sang XML và ngược lại là lĩnh vực quan trọng cần
nghiên cứu.
Sự thành công của bất kỳ công cụ nào kết nối giữa XML và hệ quản trị
cơ sở dữ liệu quan hệ trực tiếp hay thông qua ngôn ngữ thứ cấp hơn đều phụ
thuộc nặng nề vào chất lượng giản đồ định rõ cấu trúc của dữ liệu được chuyển
đổi. Một giản đồ mơ hồ và chưa hoàn thiện có thế dẫn tới việc kết nối thiếu
chính xác hoặc mất dữ liệu. Các cơ chế suy luận các giản đồ quan hệ từ các
giản đồ không quan hệ đều được chứng minh tốt bằng tài liệu nhưng các
phương thức để suy luận một giản đồ XML thì khó hiểu hơn rất nhiều.
Cho tới hiện nay, việc chọn lựa một dạng thức để mô tả giản đồ XML
còn hết sức khó khăn. Gần đây, giản đồ XML nổi lên như một tiêu chuẩn phổ
biến nhưng không chính thức để định dạng giản đồ XML. Đó là một tiêu
chuẩn có ưu thế lớn và toàn diện giúp hỗ trợ các kiểu đánh máy được cài đặt


sẵn phong phú và cho phép tạo ra các kiểu phức tạp hơn dựa trên những kiểu
được cài đặt sẵn cũng như nhiều tính năng hữu dụng khác.
Luận văn trình bày phương pháp chuyển đổi dữ liệu giữa XML sang cơ
sở dữ liệu quan hệ và ngược lại dựa trên lược đồ XML và lược đồ quan hệ. Cụ
thể, luận văn đi sâu nghiên cứu một số thuật toán chuyển đổi cơ bản hướng cấu
trúc và một thuật toán chuyển đổi hướng dữ liệu. Đồng thời, dựa trên các thuật
toán cơ bản đó, luận văn nghiên cứu việc chuyển đổi có thể đảm bảo được các
ràng buộc, giảm dư thừa dữ liệu, và có thể khai thác tối đa khả năng, lợi ích
của hướng tiếp cận này.
Luận văn đƣợc trình bày trong 3 chƣơng
Chƣơng I: trình bày một số khái niệm cơ bản về XML như định nghĩa
DTD, lược đồ XML, trình phân tích tài liệu, mô hình DOM … và mô hình
CSDL quan hệ như các khái niệm về quan hệ, thuộc tính, bộ, khoá ….

Chƣơng II: Giới thiệu một số thuật toán chuyển đổi dữ liệu giữa XML
và mô hình quan hệ. Các thuật toán cơ bản như gộp cơ sở, gộp chia sẻ, gộp cải
tiến giửi quyết sự phức tạp của đặc tả DTD, sự xung đột giữa kiến trúc có thứ
bậc tự nhiện cảu mô hình dữ liệu XML và bản chất hai mức của mô hình quan
hệ. Ba thuật toán CPI, NeT và CoT không chỉ thực hiện tốt việc chuyển đổi
cấu trúc của lược đồ gốc mà còn bảo toàn về mặt ngữ nghĩa của lược đồ trong
quá trình chuyển đổi. Ngoài các thuật toán chuyển đổi lược đồ, luận văn giới
thiệu một thuật toán chuyển đổi dữ liệu Xinsert, thuật toán có khả năng chuyển
đổi dữ liệu của tài liệu XML sang dữ liệu quan hệ theo hướng tiếp cận DOM.
Chƣơng III: Nghiên cứu cài đặt ứng dụng minh hoạ cho một số thuật
toán chuyển đổi dữ liệu như thuật toán gộp cải tiến và Xinsert.





Chƣơng I: KHÁI NIỆM XML VÀ MÔ HÌNH DỮ LIỆU
QUAN HỆ
1.1 TÀI LIỆU XML
1.1.1 Giới thiệu XML và ngôn ngữ định dạng
Như tất cả chúng ta đều biết, XML là viết tắt cho chữ eXtensible
Markup Language. XML là một ngôn ngữ đánh dấu tương đối mới được sử
dụng để định nghĩa cấu trúc các dữ liệu trong một tài liêu thông qua các
thẻ[1][2].
Ngôn ngữ định dạng (Markup Language) là ngôn ngữ được dùng để
trình bày các dữ liệu trong một tài liệu.
Ngôn ngữ định dạng mà mọi người quen thuộc ngày nay là ngôn ngữ
HTML. HTML cho phép bạn tạo nội dung các trang Web tương đối đơn giản.
Ví dụ 1.1






<Html>
<Head>
<Title>Lời chào</Title>
</Head>
<Body>
<Center>
<B>
Chào tất cả các bạn học sinh thân yêu!
</B>
</Center>
</Body>
</Html>
Kết quả trang web trong trình duyệt được hiển thị như sau:











Ở đây HTML thực hiện định dạng bằng các thẻ (tags) như <Head>,
<Center>, <B>… Những thẻ này chỉ cho trình duyệt (browser) cách hiển thị

nội dung tài liệu.
Giống như HTML, XML dùng các thẻ để khai báo cấu trúc dữ liệu
trong file XML. Điểm khác biệt chính giữa HTML và XML là trong khi các
thẻ HTML chứa ý nghĩa dùng để trình bày dữ liệu thì các thẻ của XML chứa ý
nghĩa dùng để định nghĩa cấu trúc dữ liệu. Ví dụ một tài liệu đặt hàng (order)
XML dưới đây:
Ví dụ 1.2
<? Xml version="1.0" encoding="UTF-8" ?>
<Order OrderNo="1023">
<OrderDate>2002-3-27</OrderDate>
<Customer>Peter Collingwood</Customer>


<Item>
<ProductID>1</ProductID>
<Quantity>5</Quantity>
</Item>
<Item>
<ProductID>4</ProductID>
<Quantity>3</Quantity>
</Item>
</Order>
Tài liệu này chỉ chứa dữ liệu, không đề cập gì đến cách trình bày. Điều
này có nghĩa là một bộ phân tích XML (XML parser) không cần phải hiểu ý
nghĩa của các thẻ. Nó chỉ cần tìm các thẻ và xác định rằng đây là một tài liệu
XML hợp lệ. Vì trình duyệt không cần phải hiểu ý nghĩa của các thẻ, nên ta có
thể dùng bất kỳ tên nào để đặt cho thẻ cũng được, trong đó tên đặt cho thẻ bắt
đầu bằng ký tự gạch chân (_), ký tự số (1,2,3…), ký tự (a,A,b,B…), dấu chấm
(.), dấu gạch nối (-), nhưng không có khoảng trắng.
Nhìn tổng quát, một tài liệu XML bắt đầu bằng thẻ khái báo chỉ thị xử

lý XML <? Xml version="1.0" encoding="UTF-8" ?>. Tất cả các chỉ thị xử lý
XML bắt đầu bằng <? Và kết thúc bằng ?>
Chúng ta hãy quan sát kỹ hơn cấu trúc của một tài liệuXML. Trước hết
tài liệu XML được hình thành từ các phần tử (element) XML và các thuộc tính
của các phần tử đó.
Trong ví dụ trên ta thấy tài liệu XML gồm có phần tử Order được gọi
là phần tử gốc của tài liệu có thuộc tính OrderNo với giá trị 1023. Bên trong
phần tử gốc Order có chứa:
- Phần tử OrderDate với giá trị là:2002-3-27


- Phần tử Customer với giá trị là: Peter Collingwood.
- Hai phần tử Item, mỗi phần tử Item lại chứa một phần tử ProductID
và một phần tử Quantity.
Đôi khi ta còn khai báo một phần tử rỗng trong tài liệu XML (là phần tử
có tên, nhưng không chứa một giá trị), vì ta muốn dùng nó như một phần tử
tuỳ chọn, có cũng được, không có cũng không sao. Ví dụ như phẩn tử rỗng
MiddleInitial trong phần tử Customer dưới đây:
Ví dụ 1.3
<Customer>
<FirstName>Stephen</FirstName>
<MiddleInitial></MiddleInitial>
<LastName>King</LastName>
</Customer>
Có một cách khác để biểu diễn phần tử rỗng là bỏ thẻ đóng và thêm một
dấu "/" ở cuối thẻ mở. Ta có thể viết lại ví dụ customer như sau:
Ví dụ 1.4
<Customer>
<FirstName>Stephen</FirstName>
<MiddleInitial/>

<LastName>King</LastName>
</Customer>
Dĩ nhiên phần tử rỗng cũng có thể có thuộc tính như phần tử
PhoneNumber thứ nhì dưới đây:
Ví dụ 1.5


<Customer>
<FirstName>Stephen</FirstName>
<MiddleInitial></MiddleInitial>
<LastName>King</LastName>
<PhoneNumber Location="Home">9847 2635</PhoneNumber>
<PhoneNumber Location="Work"></PhoneNumber>
</Customer>
1.1.2 Trình soạn thảo XML (XML Editors) và trình duyệt XML
Để tạo ra các tài liệu XML ta có thẻ sử dụng các trình soạn thảo đơn
giản như: Notepad, wordpad … Có rất nhiều các trình soạn thảo đặc biệt được
dùng phục vụ cho hiệu chỉnh nội dung file dữ liệu XML. Đơn giản và dễ dùng
nhất là trình soạn thảo XML notepad của Microsoft. Các trình soạn thảo
chuyên nghiệp hơn như XML Writer.
Những phần mềm trình duyệt điển hình hỗ trợ XML (chỉ kiểm tra
khuôn dạng XML hợp lệ và cho phép kết hợp CSS, XSL) bao gồm: Internet
Explorer(IE), Netscape Navigator, Jumpo.
1.1.3 Bộ phân tích XML và Bộ kiểm tra XML (XML Validator)
Bộ phân tích là gói phần mềm được sử dụng chúng như một phần mềm
kèm theo của ứng dụng có chứa các thư viện cung cấp các hàm, cho phép phân
tích nội dung và trích xuất dữ liệu của XML khá đơn giản. Dưới đây là các
trình phân tích thướng dùng: XML cho Java (XML4J), Microsoft XML Parser,
Python XML Parse.
Bộ kiểm tra là các gói phần mềm cho phép kiểm tra một số chuẩn trên

XML. Một số bộ kiểm tra thường dùng, nếu sử dụng bộ phân tích XML4J của
IBM, bạn có thể dùng đối tượng DOM Writer để làm bộ kiểm tra, ngoài ra còn
có các bộ kiểm tra như XML Writer, Tidy, ….


1.1.4 CSS và XSL
CSS và XSL [8] là các bảng định kiểu (Style sheet). CSS thích hợp để
định dạng tài liệu hướng về HTML, ta có thể thay đổi font chữ, cỡ chữ, màu
sắc, đặt hình ảnh và yêu cầu kết hợp định dạng của CSS với dữ liệu XML. Bản
thân XML chỉ định nghĩa các cấu trúc lưu trữ dữ liệu, nó không có khả năng tự
hiển thị và trình diễn nội dung tài liệu. CSS trích rút dữ liệu từ XML và đặt
vào bảng định kiểu tạo thành một phiên bản trình diễn sau cùng tựa HTML.
XSL là một cách khác để hiển thị XML. XSL (Extensible Style
Language) là ngôn ngữ định kiểu mở rộng dựa trên cú pháp và nguyên tắc cấu
thành của XML. XSL cho phép xử lý và trình diễn dữ liệu mạnh hơn CSS.
XSL là ngôn ngữ định kiểu có khả năng điều khiển động các phần tử thẻ và dữ
liệu cần định dạng. XSL có thể sắp xếp lại các thẻ trong tài liệu, thay đổi cả
nội dung thẻ, hiển thị một phần hay toàn bộ nội dung dữ liệu.
1.1.5 Xây dựng tài liệu XML hợp khuôn dạng
Với XML bạn tự định nghĩa thẻ và tuỳ ý quyết định mục đích sử dụng
của thẻ. Mặc dù được tự do định nghĩa, nhưng các thẻ XML cần theo một quy
tắc định nghĩa bắt buộc. Nếu bạn không theo những quy tắc này khi định nghĩa
thẻ, các bộ phân tích cú pháp XML sẽ không xác định được tài liệu của bạn.
Nói chung, khi xây dựng tài liệu XML bạn phải tuân theo đúng cú pháp
khi khai báo thẻ XML và tuân theo cách đặt các thẻ XML theo một trật tự có
thể phân tích được bởi các bộ phân tích.
Các qui tắc cần tuân theo để xây dựng một tài liệu XML hợp khuôn
dạng:
- Các khai báo được đặt ở dòng đầu tiên của tài liệu
- Tài liệu XML chỉ có một phần tử gốc, các phần tử khác nếu có, phải là

con của phần tử gốc


- Mội phần tử XML khác rỗng phải bao gồm đầy đủ thẻ đóng và thẻ mở
- Đóng phần tử rỗng với chuỗi đóng />: Phần tử rỗng là phần tử chỉ có
một thẻ.
- Mọi phần tử trong tài liệu XML khác phần tử gốc đều phải nằm giữa
cặp thẻ gốc
- Các phần tử lồng nhau phải có thẻ đống, thẻ mở hợp vị trí: thẻ nào mở
trước thì đống sau.
- Sử dụng tên thuộc tính là duy nhất: bạn không được đặt trong thẻ các
thuộc tính trùng tên
- Chỉ nên sử dụng 5 tham chiếu thực thể được định nghĩa trước:
&amp;để chỉ &, &lt;để chỉ <, &gt;để chỉ >…
- Bọc các giá trị thuộc tính bằng cặp dấu nháy kép hoặc nháy đơn.
- Chỉ nên sử dụng ký tự < và & đối với thẻ mở và các thực thể.
1.1.6 Định nghĩa kiểu tài liệu (DTD)
Một định nghĩa kiểu tài liệu (DTD - Document Type Definition) [1][2]
là một bộ những qui tắc cú pháp cho các nhãn. Nó cho bạn biết những nhãn
nào bạn có thể sử dụng trong một tài liệu, chúng nên được xếp theo thứ tự nào,
những nhãn nào có thể xuất hiện bên trong các nhãn khác, những nhãn nào có
các thuộc tính, Nguồn gốc được phát triển cho việc sử dụng với SGML,
một DTD có thể là một bộ phận của một lài liệu XML, nhưng thường nó là
một tài liệu riêng biệt hoặc một loạt các tài liệu.
Bởi vì bản thân XML không phải là một ngôn ngữ, mà là một hệ thống
cho việc định nghĩa các ngôn ngữ, cho nên nó không có một DTD chung như
trong HTML. Thay vào đó, mỗi tổ chức hoặc công nghệ muốn dùng XML cho
việc trao đổi dữ liệu đều có thể định nghĩa nên những DTD sở hữu riêng. Nếu



một tổ chức dùng XMT để gán nhãn các tài liệu chỉ cho việc sử dụng nội bộ,
thì có thể tạo nên DTD riêng cho mình.
1.1.7 Giới thiệu về Xpath
Chúng ta đã thấy cấu trúc và cú pháp của XML tương đối đơn giản.
XML cho ta một cách chuẩn để trao đổi tin tức giữa các máy tính. Bước tiếp
theo là tìm hiểu cách nào một chương trình xử lý một tài liệu XML.
Dĩ nhiên, để xử lý một tài liệu XML chương trình ứng dụng phải có
cách tham chiếu đến tài liệu để lấy ra giá trị của các phần tử hay thuộc tính. Do
đó người ta thiết kế ra ngôn ngữ XML Path language, mà ta gọi tắt là XPath.
XPath đóng một vai trò quan trọng trong công tác trao đổi dữ liệu giữa các
máy tính hay giữa các chương trình ứng dụng vì nó cho phép ta lựa chọn hay
sàng lọc ra những tin tức nào mình muốn để trao đổi hay hiển thị.
Xpath [8] là một chuẩn để xử lý XML, cũng giống như SQL là một
ngôn ngữ chuẩn để làm việc với cơ sở dữ liệu. Tiên phong trong việc triển khai
các chương trình áp dụng XPath là công tác của các công ty phần mềm lớn
như Microsoft, Oracle, Sun, IBM, v.v. Sở dĩ ta cần có một chuẩn XPath là vì
nó được áp dụng trong nhiều hoàn cảnh, nên cần phải có một lý thuyết rõ ràng,
chính xác.
XPath cho ta cú pháp để diễn tả cách tham chiếu đường dẫn trong tài
liệu XML. Ta coi mỗi tài liệu XML được biểu diễn bằng một cây có nhiều nút.
Mỗi phần tử hay thuộc tính là một nút.
Ví dụ 1.6
<?xml version="1.0"?>
<Order OrderNo="1047">
<OrderDate>2002-03-26</OrderDate>


<Customer>John Costello</Customer>
<Item>
<Product ProductID="1" UnitPrice="70">Chair</Product>

<Quantity>6</Quantity>
</Item>
<Item>
<Product ProductID="2" UnitPrice="250">Desk</Product>
<Quantity>1</Quantity>
</Item>
</Order>
Ta có thể biểu diễn XML trên bằng một Tree như dưới đây




Bạn có thể dùng biểu thức XPath để chỉ định đường dẫn đến nút nào
hay trích ra một hay nhiều nút thỏa mãn điều kiện yêu cầu. Biểu thức XPath có
thể là tuyệt đối, tức là lấy nút gốc làm chuẩn hay tương đối, tức là khởi đầu từ
nút vừa mới được chọn.
Tài liệu XML thường có một phần tử gốc. Mọi phần tử con đều nằm
bên trong phần tử gốc. Để tham chiếu đến một nút dữ liệu trong tài liệu XML
bạn chỉ ra đường dẫn tương tự như đường dẫn thư mục.


1.1.8 Mô hình đối tƣợng dữ liệu DOM
Để xử lý, W3C định nghĩa tài liệu XML theo mô hình đối tượng tài liệu
DOM (Document Object Model ). Theo nmô hình này, tài liệu XML là một
cây gồm nhiều nút. Những nút này nội dung có thể chứa phần tử, dữ liệu,
thuộc tính … và các nút con khác. Mô hình DOM có các loại nút sau đây trong
mô hình DOM:

Nút
Mô tả

Element
Phần tử XML
Attribute
Thuộc tính
Text
Dữ liệu text
CDATA section
Phân đoạn CDATA
Entity reference
Tham chiếu thực thể
Entity
Thực thể
Processing Instruction
Chỉ thị xử lý
Comment
Chú thích
Document
Tài liệu
Document type
Kiểu tư liệu
Document fragment
Đoạn tài liệu
Notation
Ghi chú
Ngoài ra DOM còn cung cấp nhiều phương thức để truy xuất và cập
nhật các đối tượng [1][2].
Các phiên bản mô hình DOM được xếp theo cấp độ hay bậc (level).
Hiện tại, bản chi tiết kĩ thuật hiện hành của DOM đang ở cấp độ 2. Tuy vậy
một số ở bản mô tả chi tiết kĩ thuật cấp độ 3 đang là khuyến khích sử dụng của
W3C.

- Cấp độ 0: Bao gồm mọi chi tiết DOM theo qui định của từng nhà phát
triển riêng biệt tồn tại trước khi DOM cấp độ 1 ra đời. Ví dụ:
document.images, document.forms, document.layers, và document.all. Chú ý:


đây là mô tả chi tiết kĩ thuật chính thức bởi W3C hơn là một tham khảo đến
những thứ tồn tại trước khi xảy ra quá trình chuẩn hóa.
- Cấp độ 1: Cách duyệt qua tài liệu (cấu trúc cây) của DOM (HTML và
XML) và thao tác nội dung (bao gồm việc thêm thành phần). Các thành phần
riêng cho HTML cũng được đưa vào.
- Cấp độ 2: Hỗ trợ không gian tên XML, khung nhìn có lọc (filtered
views) và các sự kiện DOM.
- Cấp độ 3: Nhằm năng cao các khả năng của DOM, cấp độ 3 chứa 6
bản mô tả chi tiết kĩ thuật khác nhau: 1) the DOM Level 3 Core; 2) the DOM
Level 3 Load and Save; 3) the DOM Level 3 XPath; 4) the DOM Level 3
Views and Formatting; 5) DOM Level 3 Requirements; and 6) the DOM Level
3 Validation.
1.1.9 XML và cơ sở dữ liệu
Nhìn chung XML và CSDL là những công nghệ lấy dữ liệu làm trung
tâm. XML thích hợp cho việc truyền thông dữ liệu, trong khi đó cơ sở dữ liệu
thích hợp cho việc lưu trữ và truy vấn dữ liệu. Do đó nếu kết hợp giữa những
ưu điểm của hai công nghệ này sẽ phát huy được thế mạnh của cả XML và
CSDL.
Với một ứng dụng thương mại điện tử, XML được dùng như là một
phương thức truyền thông dữ liệu tốt nhất. Nhiệm vụ quan trọng của ứng dụng
này là phải lưu trữ dữ liệu XML vào CSDL quan hệ. Do đó cần một phần mềm
chuyển đổi dữ liệu từ tài liệu XML vào CSDL hay xuất dữ liệu dưới dạng
XML.
Mặt khác, nhiệm vụ chủ yếu của dữ liêu Web la giúp tìm kiếm nội dung
trên trang Web thật hiệu quả. Do đó, các thực thể, các thành phần tạo nên cấu

trúc của tài liệu XML rất quan trọng bởi nó trở thành những phần chủ yếu của


tài liệu phục vụ cho việc tìm kiếm, hệ thống có thể duy trì được cấu trúc tài
liệu, đáp ứng được những giao dịch và xử lý những câu truy vấn XML.
1.2 MÔ HÌNH DỮ LIỆU QUAN HỆ
1.2.1 Các khái niệm cơ bản [3][4][5]
1.2.1.1 Cơ sở dữ liệu
Là một tập hợp dữ liệu có liên quan với nhau về mặt logic dùng để lưu
trữ thông tin về một tổ chức nào đó đáp ứng thế giới thực. Các tập dữ liệu đó
có cấu trúc và được lưu trữ trên các thiết bị nhớ thứ cấp để đáp ứng thông tin
của nhiều người sử dụng với nhiều mục đích khác nhau.
1.2.1.2 Hệ quản trị cơ sở dữ liệu
Là một hệ thống phần mềm cung cấp cho người dùng một môi trường
làm việc vừa thích hợp vừa hiệu quả để khai thác CSDL theo các chức năng
mô tả, lưu trữ, tìm kiếm và cập nhật dữ liệu.
Tất cả các truy cập đến CSDL đều thông qua hệ quản trị CSDL. Hệ
quản trị CSDL cung cấp một ngôn ngữ định nghĩa dữ liệu (DDL) và một ngôn
ngữ thao tác dữ liệu (DML) để người dùng định nghĩa CSDL và có thể thêm,
xoá, sửa hay truy xuất vào CSDL.
1.2.1.3 Mô hình quan hệ
Biểu diễn dữ liệu trong một CSDL như một tập các quan hệ. Một cách
không hình thức, mỗi quan hệ là một bảng giá trị gồm các hàng và các cột.
Mỗi phần tử của quan hệ được gọi là bộ. Mỗi hàng là một tập các giá trị có liên
quan đến nhau, tương ứng với một bộ. Cột tương ứng với thuộc tính, mọi giá
trị trong cột thường có cùng kiểu dữ liệu.
Ví dụ 1.7


Quan hệ nhân viên được thể hiện qua bảng sau

Masonv
Hoten
ngaysinh
quequan
001
Lê Quốc Cường
20/10/1989
Hà Nội
002
Trần Thị Hương
17/12/1988
Hà Tây
003
Nguyễn Thị Trang
05/07/1987
Hải Phòng
1.2.1.4 Quan hệ
Là một tập con của tích Decac của danh sách các miền. Một quan hệ
xác định trên tập thuộc tính {A
1
,A
2
,…,A
n
}.
Khi đó r

DOM(A
1
)


DOM(A
2
)

…

DOM(A
n
) với DOM(A
i
) là
miền của thuộc tính A
i
. Như vậy quan hệ r là một tập hợp n bộ có dạng:
r = {(a
1
,a
2
,…,a
n
)|ai DOM(A
i
), i=1,2,…,n}.
1.2.1.5 Lƣợc đồ quan hệ R
Là một cặp có thứ tự R = <

,F>, trong đó

là tập hữu hạn các thuộc

tính của quan hệ, F là tập các ràng buộc toàn vẹn.
Lược đồ quan hệ R được sử dụng để mô tả cấu trúc và các ràng buộc
toán vẹn của một quan hệ. Dữ liệu của quan hệ có thể thay đổi theo thời gian
do các phép toán cập nhật nhưng lược đồ quan hệ thì tương đối không thay
đổi.
1.2.1.6 Khoá của quan hệ
Khoá của quan hệ r trên tập thuộc tính R = {A
1
,A
2
,…,A
n
} là tập con
K

R sao cho bất kỳ hai bộ khác nhau t1,t2

r luôn thoả mãn t1(K)

t2(K),
bất kỳ tập con thực sự K‟

K nào đó đều không có tính chất đó.
Ví dụ 1.8


Xét quan hệ nhân viên ở trên, khóa của quan hệ là Masonv. Khoá
ngoài của một quan hệ là một tập hợp gồm một hay nhiều thuộc tính là khoá
của một quan hệ khác.
1.2.1.7 Ràng buộc toàn vẹn

Khi định nghĩa một quan hệ chỉ với danh sách các thuộc tính thì chưa
đủ, ta phải kết hợp vào quan hệ một tập các ràng buộc toàn vẹn trên các giá trị
của thuộc tính. Tập ràng buộc này sẽ được kiểm tra trên từng bộ trước khi
kiểm tra trên toàn quan hệ. Các thao tác cập nhật cũng bị kiểm tra chặt chẽ bởi
các ràng buộc này. Ví dụ, ràng buộc về khoá nghĩa là mỗi giá trị khoá đặc tả
một bộ duy nhất trong quan hệ, ràng buộc về trị thì khoá chính hoặc tập con
của nó không được mang giá trị null, ràng buộc về tính duy nhất của thuộc
tính, ràng buộc về khoá ngoài … [5].
1.2.1.8 Các thao tác cập nhật dữ liệu
Là các phép toán làm CSDL thay đổi như phép thêm bộ dùng để thêm
các bộ vào quan hệ, phép xoá để loại bỏ các bộ nào đó ra khỏi quan hệ, phép
sửa nhằm thay đổi một số giá trị của các bộ đang tồn tại trong quan hệ. Vì vậy,
một số ràng buộc trên lược đồ CSDL có thể bị vi phạm khi thực hiện một phép
toán cập nhật.
1.2.2 Các phép toán trên quan hệ [4][5]
1.2.2.1 Các phép toán tập hợp
Các phép toán tập hợp bao gồm các phép hợp, phép giao , phép trừ, tính
Decac và phép chia. Các phép toán này bắt nguồn từ cách nhìn mỗi quan hệ là
một tập hợp các bộ và cần phải có điều kiện đảm bảo rằng quan hệ kết quả của
các phép toán phải là một quan hệ khả hợp. Hai quan hệ được gọi là khả hợp
nếu chúng cùng bậc và thuộc tính thứ i của quan hệ này có miền trùng với


miền của thuộc tính thứ i của quan hệ kia. Thứ tự của các thuộc tính phải được
tôn trọng khu thực hiện phép toán.
Giả sử r là quan hệ xác định trên tập thuộc tính  = { A
1
, A
2
,…,A

n
}, và
r là tập hữu hạn các bộ.
a. Phép hợp: Là một quan hệ gồm tất cả các bộ thuộc r hoặc thuộc s
hoặc thuộc cả hai quan hệ. Ký hiệu là r  s,
r  s = {t t  r hoặc t  s hoặc t  r và s }
b. Phép giao: Là một quan hệ gồm tất cả các bộ đồng thời thuộc cả r và
s. Ký hiệu là r  s, biểu diễn hình thức phép giao có dạng:
r  s ={t t  r và t  s }
c. Phép trừ: Là một quan hệ gồm tất cả các bộ thuộc r nhưng khong
thuộc s, ký hiệu là r - s, biểu diễn hình thức phép trừ có dạng:
r – s = { t  t  r và t  s }
d. Phép tích Decac: Gọi r là một quan hệ của lược đồ R(A
1
, A
2
, ….,
A
n
), s là một quan hệ của lược đồ S(B
1
, B
2
, …., B
m
). Tích Descartes của r và s
được ký hiệu là r x s, là tập (n + m)_ bộ sao cho mỗi bộ này có n thành phần
đầu làm thành một bộ r và m thành phần sau làm thành một bộ thuộc s. Biểu
diễn hình thức có dạng:
r


s = { t  t = (a
1
, a
2
, …, a
n
, b
1
, b
2
, …, b
m
), (a
1
, a
2
, …, a
n
)  r và
(b
1
, b
2
, …, b
m
)  s}
e. Phép chia: Gọi r là một quan hệ của lược đồ R(A
1
, A

2
, …., A
m
, A
m+1
,
A
2
, …., A
n
), s là một quan hệ của lược đồ S(A
1
, A
2
, …., A
m
). Kết quả của phép
chia hai quan hệ r và s được ký hiệu là r s, là tập các (n-m)_ bộ sao cho mỗi
bộ này khi được ghép với một bộ bất kỳ trong quan hệ s cho một bộ trong quan
hệ r. Biểu diễn hình thức có dạng:


r  s = { t  t = (a
m +1,
a
m +2,
…,a
n
) :  (a
1,

a
2,
, a
m
)  s và
(a
1
,a
2
, …,a
m,
a
m+1
,…,a
n
)  r }.
1.2.2.2 Các phép toán đặc biệt trên quan hệ
Các phép toán đặc biệt trên quan hệ là một cách tiếp cận khác trong việc
biểu diễn câu hỏi của ngôn ngữ quan hệ. Chúng liên quan chặt chẽ đến các
thao tác cơ bản làm thay đổi quan hệ như thêm, sửa, xoá.
a. Phép chọn: dùng để xây dựng một tập con các bộ của một quan hệ
đã cho, các bộ này phải thoả mãn điều kiện chọn C. Điều kiện chọn là một tổ
hợp Boolean của các toán hạng, mỗi toán hạng là một phép so sánh đơn giản
giữa hai biến là hai thuộc tính hoặc một biến là thuộc tính và một hằng. Biểu
thức logic C này sẽ cho giá trị TRUE/FASLE đối với mỗi bộ kiểm tra. Hình
thức hoá phép chọn được viết như sau:

c
(r) = { t  t  r, C (t)= TRUE}.
Trong đó, C(t) là giá trị của các thuộc tính xuất hiện trong biểu thức C

tại bội t.
b. Phép chiếu: Phép chiếu một quan hệ r trên tập thuộc tính X của r
dùng để xây dựng quan hệ mới từ quan hệ r đã cho bằng cách loại bỏ đi một
số thuộc tính của quan hệ đó. Những thuộc tính bị loại bỏ là những thuộc tính
không thuộc tập hợp X. Kết quả phép chiếu một quan hệ r trên tập thuộc tính
X được ký hiệu 
X
(r).
Giả sử r là quan hệ trên lược đồ R (), t  r, t [ A] là giá trị bộ t tại
thuộc tính A, A  , với X= {A
1
, A
2
, …, A
m
} thì t[X] = (t[A
1
], t[A
2
], …,
t[A
m
]).

x
(r) = { t[X]  t r}.


Trong thực tế , người ta kết hợp phép chọn và phép chiếu để thu gọn
trên một số cột, một số hàng.

c. Phép kết nối : Cho r là một quan hệ xác định trên tập thuộc tính {
A
1,
A
2,
…A
n
}, s là một quan hệ xác định trên tập thuộc tính {B
1
,B
2
,….B
n
} và 
là một trong các phép so sánh: = ,>,<, , , . Kết quả của phép kết nối quan
hệ r với quan hệ s theo điều kiện A
i
 B
j
được ký hiệu r 
Ai  Bj
s và được xác
định như sau:
r 
Ai  Bj
s = {(t,u)  t r,u s và t[A
i
]  u[B
j
]}.

1.3 KẾT LUẬN
Nội dung chương I đã giới thiệu những khái niệm cơ bản về XML và
mô hình CSDL quan hệ. Trong đó, định nghĩa kiểu tài liệu DTD giữ vai trò rất
quan trọng trong quá trình chuyển đổi. DTD đặc tả một tài liệu XML phức tạp
bằng các phần tử, toán tử, thuộc tính, từ khoá… Đồng thời mô hình CSDL
quan hệ đã dùng các khái niệm bảng, thuộc tính, khoá chính, khoá ngoại, ràng
buộc toàn vẹn, … Để mô tả dữ liệu trong thế giới thực.Sự khác biệt giữa hai
mô hình này là vấn đề trọng tâm trong quá trình chuyển đổi dữ liệu qua lại
giữa hai mô hình, và vấn đề đó cần được giải quyết tốt bằng các thuật toán. Do
đó, chương II sẽ trình bày những thuật toán có thể giải quyết được vấn đề
trọng tâm của việc chuyển đổi dữ liệu giữa XML và mô hình quan hệ.











Chƣơng II: THUẬT TOÁN CHUYỂN ĐỔI DỮ LIỆU GIỮA TÀI
LIỆU XML VÀ CSDL QUAN HỆ
Rất nhiều các công cụ đang tồn tại có thể chuyển đổi dữ liệu giữa XML
và CSDL quan hệ. Trong chương này sẽ giới thiệu một số thuật toán chuyển
đổi từ tài liệu XML (tương ứng là các DTD) sang CSDL quan hệ và ba thuật
toán chuyển đổi từ CSDL quan hệ sang tài liệu XML. Các thuật toán này chủ
yếu tập trung giải quyết các vấn đề về cấu trúc và một số các ràng buộc ngữ
nghĩa của lược đồ gốc.

2.1 CHUYỂN ĐỔI XML SANG CSDL QUAN HỆ
Quá trình chuyển đổi tài liệu XML sang RDB bao gồm các vấn đề sau:
- Ánh xạ mô hình: Là sinh ra lược đồ quan hệ tương ứng từ dữ liệu
DTD. Thay vì ứng với mỗi phần tử thẻ XML sẽ sinh ra một bảng quan
hệ(Theo thuật toán gộp cơ sở) thì ta sẽ gộp nhiều phần tử XML vào một bảng
để giảm đi số bảng được sinh ra và giảm cả chi phí kết nối các bảng lại với