TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG



BÀI TẬP LỚN TÍCH HỢP DỮ LIỆU VÀ XML

Đề tài: Tìm hiểu
XPEDIA: XML Processing for Data Integration

Giảng viên hướng dẫn:
ThS. Nguyễn Hồng Phương

Nhóm 16


Sinh viên thực hiện:
Nguyễn Việt Anh
20101108

Đinh Ngọc Nam
20101903

Lưu Văn Dũng
20101277

Nguyễn Bá Chường
20101178


HÀ NỘI 2014

MỤC LỤC

TÓM TẮT 3
PHẦN I: GIỚI THIỆU SƠ LƯỢC VỀ PHƯƠNG PHÁP XỬ LÝ TÍCH HỢP XML
(XPEDIA) 4
1.1 Hệ thống XPEDIA 4
1.2 Những đóng góp của XPEDIA 6
PHẦN II: MÔ HÌNH TÍNH TOÁN 7
2.1 Toán tử XML 8
PHẦN III: KỊCH BẢN ĐẶC TRƯNG CỦA ETL VỚI XML 12
PHẦN IV: TỐI ƯU HÓA ELT TRONG XPEDIA 15
4.1 Viết lại các flow ETL thành các Operator đơn giản 15
4.2 Truy vấn Generating và Merging 18
4.3 Tạo ra các định nghĩa công việc ELT 19
PHẦN V: XỬ LÝ SONG SONG CỦA DỮ LIỆU XML 21
5.1 Xác định các phân vùng tối ưu 21
5.2 Tạo phân vùng tối ưu 24
5.2.1 Phân tích cú pháp cạn 24
5.2.2 Tạo phân vùng cân bằng 26
5.3 Sư xác nhận giản đồ song song 27
PHẦN VI: THỰC HIỆN ĐÁNH GIÁ 29
6.1 Thiết lập thử nghiệm 29
6.2 Tác động của tối ưu hóa ELT 30
6.3 Ảnh hưởng của song song 30
PHẦN VII: CÔNG TÁC LIÊN QUAN 34
KẾT LUẬN 35
TÀI LIỆU THAM KHẢO 36

TÓM TẮT


Các công cụ tích hợp dữ liệu ngày càng cần phải cung cấp những tùy chọn xử lý phức
tạp cho dữ liệu XML . Trong quá khứ, nó phù hợp cho các máy để hỗ trợ cơ bản trong việc
tích hợp XML . Tuy nhiên , với sự tăng trưởng ổn định của XML trong các ứng dụng và
cơ sở dữ liệu , nền tảng tích hợp cần phải cung cấp các hoạt động trực tiếp trên XML cũng
như cải thiện khả năng mở rộng và hiệu quả của các hoạt động này . Trong bài báo này ,
chúng tôi mô tả một cách linh hoạt và toàn diện về framework để thực hiện Trích xuất –
Chuyển đổi- xử lý ( ETL) của XML. Điều này bao gồm:
i. Đầy đủ mô hình tính toán và khả năng của công cụ để thực hiện các hoạt động
trong một dòng chảy ETL
ii. Một cách tiếp cận thông qua các thao tác với XML để thành một công cụ cơ sở
dữ liệu có khả năng hỗ trợ xử lý XML
iii. Phương pháp để áp dụng kỹ thuật phân vùng nhằm cung cấp khả năng mở rộng
, xử lý song song tài liệu XML lớn. Chúng tôi mô tả kết quả thực nghiệm cho
thấy hiệu quả của các kỹ thuật này.












PHẦN I: GIỚI THIỆU SƠ LƯỢC VỀ PHƯƠNG PHÁP XỬ LÝ
TÍCH HỢP XML (XPEDIA)

XML được giới thiệu vào giữa những năm 1990 như là một đơn giản và mở rộng ngôn

ngữ dữ liệu đánh dấu . Nó đã đạt được vị trí vững chắc ngay lập tức như một định dạng dữ
liệu trao đổi . Theo thời gian, đạt được từ nhiều nghiên cứu , XML đã trở thành một định
dạng dữ liệu có giá trị bên trong và ngoài doanh nghiệp để thay thế cho dữ liệu trong nhất
thời và lâu dài của các ứng dụng . Có một số nghiên cứu lừng lẫy trong XML về việc xử
lý phân tích, chuyển đổi, xử lý cơ sở dữ liệu, lập chỉ mục và tìm kiếm. Cơ sở dữ liệu và
ứng dụng của các nhà cung cấp đã sử dụng kết quả nghiên cứu này hỗ trợ cho XML như
một kiểu dữ liệu lớp đầu tiên trong cơ sở dữ liệu như DB2 [9] , Oracle [10] , và SQL Server
[11] cũng như trong nhiều ngôn ngữ như Java , C + + , và ngôn ngữ kịch bản . Do đó, nó
không chỉ là tích hợp dữ liệu tự nhiên mà còn cần cung cấp hiệu quả kỹ thuật, khả năng
mở rộng để xử lý XML.
Các công cụ tích hợp dữ liệu như IBM Information Server , Informatica của
PowerCenter , vv, cung cấp khả năng để Trích xuất – chuyển đồi- xử lý ( ETL) từ các
nguồn dữ liệu khác nhau vào mục tiêu dữ liệu khác nhau . Đối với XML , các công cụ
ETL hiện nay cung cấp khả năng cơ bản để thực hiện XPath dựa biến đổi các định dạng
thành bộ dữ liệu hoặc ngược lại . Tuy nhiên, với tiến độ ổn định thông qua XML, cần có
công cụ tích hợp các dữ liệu nhanh chóng , khả năng mở rộng " thế hệ tiếp theo ", Khả
năng xử lý XML. Trong khi có một nền văn học phong phú trong các lĩnh vực khác nhau
của xử lý XML , đáng ngạc nhiên đã có việc hạn chế về chủ đề tích hợp dữ liệu XML. ban
đầu làm việc trong lĩnh vực này đã tập trung vào các thuật toán băm nhỏ XML thành một
giản đồ quan hệ tự nhiên. Công việc chính nằm trên XML Stylesheet Transformation
(XSLT) có thể được coi như ngoại biên liên quan chủ đề của chúng tôi [1] . Ngoài ra còn
có khá nhiều truy vấn XML tiếp tục xử lý mà chúng ta xem xét cung cấp một số có liên
quan cơ sở nền tảng cho chủ đề của chúng tôi [ 8, 9 ] . Tuy nhiên , vẫn còn một nhiều vấn
đề mở mà cần phải được giải quyết để cho phép "bên cạnh thế hệ " tích hợp dữ liệu XML.
Trong bài báo này chúng tôi đại diện các hệ thống XPEDIA (XML ProcEssing for Data
IntegrAtion) để giải quyết các vấn đề này.
1.1 Hệ thống XPEDIA

Tích hợp dữ liệu trên dữ liệu quan hệ là một chủ đề được nghiên cứu. Tuy nhiên,
trong một thế giới XML, tích hợp dữ liệu là hoàn toàn khác nhau do tính chất phân cấp

của dữ liệu. Do đó kỹ thuật đã được phát triển cho thế giới quan hệ không thể trực tiếp
áp dụng cho dữ liệu XML. Hệ thống XPEDIA là một trong những hệ thống đầu tiên kết
hợp các kỹ thuật để hỗ trợ hiệu quả XML tích hợp dữ liệu. Bây giờ chúng tôi phác thảo
một số các tính năng chính và thách thức giải quyết bằng XPEDIA

Mô hình tính toán: Mô hình tính toán sử dụng để đại diện cho các quá trình ETL
trên dữ liệu quan hệ giả định trong hình thức hàng gồm nhiều cột. tính toán như vậy mô
hình đại diện cho mỗi tài liệu XML như là một hàng duy nhất của một cột duy nhất.
Một đại diện đơn giản của dữ liệu XML như vậy là một trở ngại lớn trong việc hỗ trợ
hoạt động XML phức tạp. Do đó yêu cầu cho một kỹ thuật để xử lý dữ liệu phức tạp
thay đổi, trong khi duy trì dễ dàng đặc điểm kỹ thuật vốn có trong các mô hình tính toán
quan hệ.
First Class Data Type: Hầu hết các công cụ tích hợp dữ liệu có sẵn trong thị trường
hiện nay, đều coi XML như một CLOB (chuỗi ký tự). Tuy nhiên, chìa khóa để xử lý
hiệu quả dữ liệu XML là đối xử với nó như một đối tượng lớp dữ liệu đầu tiên trong
quá trình chuyển đổi. Một đại diện như vậy cho phép XPEDIA hỗ trợ các hoạt động
đó như đẳng cấp bậc-tham gia, xml-tổng hợp, vv là nhà khai thác chuyên ngành để
đối phó với dữ liệu XML (chi tiết trong Phần 3). Các nhà khai thác cho phép người
dùng dễ dàng xác định độ phức tạp của luồng chuyển đổi XML, mà cho đến nay vẫn
chưa có khả năng.
ETL Support: Nếu nguồn (hoặc mục tiêu trong một số trường hợp ) của một luồng
ETL là một cơ sở dữ liệu có hỗ trợ xử lý XML , XPEDIA áp dụng kỹ thuật viết lại để
chuyển đổi các bộ phận của luồng công việc ETL vào các truy vấn SQL / XML để thúc
đẩy một số đáng kể những thứ quan trọng thành các cơ sở dữ liệu. Này được gọi là ELT
(Extract, Load, Tranform) và là một kỹ thuật có giá trị để đạt được hiệu quả và hiệu
suất bằng cách tận dụng khả năng của cơ sở dữ liệu.
Khả năng mở rộng : Kích thước của một hàng / bản ghi trong dữ liệu quan hệ là
hiếm khi lớn hơn một vài Kb . Tuy nhiên , chúng tôi đã quan sát thấy từ một số khách
hàng, tích hợp dữ liệu XML đầu vào hướng đến mở rộng, đầu vào tổng hợp bao gồm
nhiều đối tượng nhỏ hơn. Do đó chúng tôi cần kỹ thuật chuyên ngành để xử lý tài liệu

XML lớn (> 2-3 GB). XPEDIA chuyển qua sử dụng một phân vùng duy nhất và kỹ
thuật xử lý song song cho các đối tượng XML. Bản chất trình bày theo thứ bậc của dữ
liệu XML là thách thức duy nhất cho thực hiện công việc biến đổi đơn đang gồm có
một loạt những thao tác trong một môi trường thực hiện song song. Trong bài báo này,
chúng tôi phương pháp tiếp cận khác nhau hiện nay được hỗ trợ bởi XPEDIA cho phân
vùng các đối tượng XML đầu vào để thực hiện phần còn lại của quá trình xử lý sử dụng
dòng song song trước khi kết hợp các kết quả. chúng tôi cũng cung cấp kết quả thử
nghiệm cho tất cả các kỹ thuật để hiển thị khả năng mở rộng và hiệu suất có thể đạt
được.

1.2 Những đóng góp của XPEDIA
Những đóng góp nghiên cứu của công việc của chúng tôi có thể được tóm tắt như
sau:
 Chúng tôi đề xuất một mô hình tính toán cho các ứng dụng ETL trên Dữ liệu XML.
Các mô hình mới được thiết kế đặc biệt để xử lý dữ liệu thứ bậc XML và xử lý dữ
liệu XML như là First Class Data Type(kiểu lớp dữ liệu đầu tiên).
 XPEDIA là hệ thống đầu tiên có hỗ trợ kỹ thuật truy vấn viết lại để chuyển đổi một
luồng ETL qua dữ liệu XML.
 Chúng tôi trình bày lý thuyết kỹ thuật xử lý song song để xử lý các tài liệu XML
lớn. Chúng tôi tin rằng thông qua duy nhất của chúng tôi kỹ thuật là nỗ lực đầu tiên
hỗ trợ hiệu quả song song trong luồng ELT trên dữ liệu XML.
 Chúng tôi trình bày kết quả thí nghiệm để xác nhận rằng cả kỹ thuật và kết quả đạt
được có ý nghĩa cải thiện hiệu suất cho một luồng ETL điển hình.

















PHẦN II: MÔ HÌNH TÍNH TOÁN
Một mô hình tính toán được sử dụng để thể hiện quá trình ETL di chuyển và chuyển
đổi dữ liệu từ các nguồn đến đích . Nhiều công cụ ETL sử dụng mô hình tính toán luồng
dữ liệu để mô tả các quá trình này .Trong mô hình luồng dữ liệu , các quy trình được thể
hiện qua một dòng chảy hướng đồ thị, nơi các đỉnh của đồ thị được coi là các thao tác và
các cạnh đại diện cho dòng chảy của dữ liệu. Các thao tác trong một mô hình luồng dữ liệu
có thể thực hiện một hoặc nhiều hơn các hoạt động sau đây:
i. Đọc dữ liệu từ các nguồn
ii. Ghi dữ liệu vào các mục tiêu
iii. Thực hiện biến đổi trên dữ liệu đầu vào để sản xuất dữ liệu đầu ra mới . Các
thuật toán của thao tác được xác định bởi các kiểu thao tác. cho ví dụ, một thao
tác tham gia sử dụng các thuật toán tham gia cho việc nhập dữ liệu đầu vào .
Luồng dữ liệu hiện tại dựa trên công cụ ELT giả định có quan hệ với mô hình dữ liệu,
luồng mà nằm giữa các thao tác , bản ghi giữa các luồng và thao tác gồm có nhiều
hàng/cột. Để xử lý dữ liệu XML, các công cụ này xem mỗi tài liệu XML là một hàng duy
nhất với một (XML) cột. Tuy nhiên , như là điều hiển nhiên, một sự trình bày quá đơn giản
như vậy là một sự bất lợi chính trong việc hỗ trợ những thao tác phức tạp qua dữ liệu XML. Do
đó, XPEDIA sử dụng một mô hình tính toán mới mở rộng mô hình luồng dữ liệu quan hệ
để hỗ trợ dữ liệu phân cấp . Một phần mở rộng như vậy, khi chúng tôi giải thích tiếp theo,
đòi hỏi một sự thay đổi lớn trong phương pháp trình bày.
XPEDIA sử dụng một mô hình luồng dữ liệu bao gồm các thao tác và cạnh . Tuy nhiên

, sự khác biệt chính từ mô hình luồng dữ liệu hiện tại là các dữ liệu chảy giữa hai thao thác
là một danh sách đặt hàng của các tài liệu XML tuân thủ một XML đơn định nghĩa yếu tố
giản đồ [2] . Chú ý rằng mỗi tài liệu có thể tự bản thân nó đa chiều hay trong thuật ngữ
XML tài liệu có thể có nhiều yếu tố lặp đi lặp lại với maxOccurs > 1 hoặc maxOccurs = "
vô cùng " . Ví dụ , hãy xem xét một tài liệu XML với nút gốc " High_Value_Customers "
mà lần lượt có 100 nút con " Customer ". Trong tài liệu này nếu chúng ta đặt nút " Customer
" trong quan hệ thì tài liệu XML sẽ được đặt vào một bảng bao gồm 100 dòng . Trong một
ví dụ thiết lập các tài liệu XML sẽ đại diện cho hai chiều dữ liệu . Để nắm bắt bản chất đa
chiều này của XML dữ liệu , mỗi tài liệu XML trong mô hình tính toán của chúng tôi bao
gồm nhiều " Vectors " - cho mỗi kiểu thành phần lặp đi lặp lại . Trong ví dụ "
High_Value_Customers ", tài liệu sẽ bao gồm một Vector ( kích thước 100) vì nó có một
yếu tố lặp đi lặp lại là nút " Customer ".
Các khái niệm về vector cũng lên khác biệt trong cách dữ liệu được xử lý bởi một toán
tử . Trong mô hình luồng dữ liệu của chúng tôi , các toán tử (trừ các toán tử nguồn mà chỉ
đơn giản là đọc dữ liệu từ các nguồn ) lặp qua danh sách các đối tượng ( các tài liệu XML
) trong đầu vào dữ liệu của chúng. Mỗi đối tượng ( tài liệu ) có thể bao gồm nhiều vector
con , các toán tử cũng có thể lặp qua một vector lớp dưới của dữ liệu đầu vào . Vector lặp
được định nghĩa như là " phạm vi " của các toán tử vector . Đối với mỗi phạm vi, các toán
tử xử lý dữ liệu đầu vào được chứa trong scope instance và tạo ra một kết quả cũng được
chứa trong scope instance. Ví dụ, trong các " High_Value_Customers " dụ phạm vi của
một toán tử sẽ là " / High_Value_Customers / Customers ". Mỗi toán tử của cây con "
Customer " sẽ độc lập với cây con " Customer" dưới nút gốc khác . Do đó các toán tử
không được phép duy trì trạng thái giữa các trường của phạm vi vector . Mỗi phạm vi thể
hiện (tức là , mỗi cây con " Customer " ) có thể coi như là tương tự như một hàng trong thế
giới quan hệ. Các khái niệm về vector và phạm vi giúp chúng tôi hỗ trợ một tập hợp phong
phú của toán tử trên dữ liệu XML và cũng giúp chúng tôi hỗ trợ song song dòng ETL ( chi
tiết trong Section5 ).
Một khác biệt quan trọng từ hệ thống luồng dữ liệu quan hệ là mô hình tính toán của
chúng tôi chỉ hỗ trợ tuyến dưới đồ thị. Hệ thống luồng quan hệ, mặt khác , thường cho
các bộ phận của các dữ liệu được tách ra và xử lý trong đồ thị con khác nhau ( của dòng

ETL) . Trong lĩnh vực XML , điều này sẽ sắp xếp để tách nội dung của một vector (của
một XmlDocument duy nhất) thành các đồ thị con khác nhau và sau đó sáp nhập chúng
vào một hoặc nhiều vectơ. Vì điều này có thể khá phức tạp, mô hình tính toán của chúng
tôi chỉ cho phép các đồ thị tuyến tính do đó đơn giản hóa công việc của quá trình thiết kế
và tăng tính khả dụng của nó. Để bù đắp cho những hạn chế của mô hình trong một đồ thị
tuyến tính, mỗi toán tử trong mô hình của chúng tôi tạo ra một kết quả cũng chứa đầu vào
ban đầu của nó. Sau đó chúng tôi sử dụng tối ưu hóa thời gian chạy, viết lại đồ thị và loại
bỏ lĩnh vực phụ thuộc không cần thiết để tối ưu hóa luồng XPEDIA ELT.
Vì vậy, các mô hình tính toán của XPEDIA kết hợp một gốc thay đổi trong phương
pháp biểu diễn bằng cách hỗ trợ cho dữ liệu XML phân cấp bao gồm việc sử dụng các tính
năng như: Phạm vi, Vector và đồ thị tuyến tính. Sử dụng các khái niệm, Hình 1 mô tả thuật
toán của một toán tử trong mô hình tính toán của chúng tôi trong luật của một báo cáo cập
nhật XQuery.

Hình 1: Thuật toán của một toán tử
op_algin hình trên là viết tắt của toán tử truy cập các dữ liệu chứa trong $ scopeand đưa
ra một kết quả duy nhất sử dụng dữ liệu này.
2.1 Toán tử XML
Bộ lọc toán tử: Các bộ lọc toán tử có thể lọc một trong các vectơ chứa trong phạm vi
thể hiện và sản xuất một vector mới đã vượt qua các bộ lọc vị. Mệnh đề SQL / XML dưới
đây minh họa các nhà điều hành lọc thuật toán:

Toán tử định hướng: Các toán tử định hướng trên cùng một vector trong đầu vào của
nó và tạo ra một vector mới đó là dựa trên một tập hợp của biểu thức được chọn. Tập hợp
các biểu thức được chọn cho phép người dùng chỉnh sửa đầu vào bằng cách loại bỏ một
phần tử hay một cây phụ, đổi tên một phần tử, hoặc làm phong phú thêm các tài liệu với
một mới thuộc tính bằng cách tính toán một biểu thức vô hướng. Mệnh đề SQL / XML sau
minh họa các thuật toán định hướng toán tử:

Toán tử kết hợp: Các toán tử kết hợp có thể tạo ra số liệu thống kê bằng cách tập hợp

một trong các vectơ chứa trong phạm vi thể hiện. Tương tự như một tập hợp cơ sở dữ liệu,
toán tử kết hợp có một tập hợp các chức năng tập hợp và một nhóm trong đó xác định tập
hợp các cột quan trọng. Kết quả của các toán tử kết hợp là một vector mới với một bản ghi
tóm lược cho mỗi khóa duy nhất mà được tìm thấy trong vectơ được nhập vào. Nhận thấy
rằng các kết hợp tạo lại cho mỗi mục phạm vi. Mệnh đề SQL / XML sau minh họa các
thuật toán điều hành tổng hợp:


Sự tham gia của các toán tử cùng bậc: Sự liên kết của các toán tử cùng bậc thể hiện
sự bình đẳng dựa trên liên kết giữa hai vectơ mà được chứa trong cùng một phạm vi thể
hiện. Tương tự như một quan hệ liên kết cùng bậc, toán tử liên kết có một tập hợp các vị
trí bình đẳng giữa các thuộc tính từ một vector và các thuộc tính của thứ hai vector. Kết
quả của sự tham gia bao gồm hai vectơ lồng nhau, trong đó mỗi thể hiện của các đầu vào
vector trái chứa tất cả các trường hợp kết hợp của các vector đầu vào phải. Mệnh đề SQL
/ XML sau minh họa sự tham gia của các toán tử cùng bậc:



Bảng đọc toán tử: Các bảng toán tử đọc tất cả các hàng của một bảng và kết quả đầu ra là
bản ghi quan hệ duy nhất hoặc một tài liệu XML. Toán tử này như một tham số của truy vấn SQL
hoặc SQL / XML thực thi trên bảng đầu vào để sinh ra đầu ra được yêu cầu.
Bảng ghi toán tử: Bảng ghi toán tử được sử dụng cho việc ghi quan hệ hoặc viết dữ liệu XML
vào một bảng. Đối với mỗi phạm vi thể hiện của vector hiện diện trong đầu vào, các toán tử tạo
ra một bản ghi mới trong bảng đầu ra.
Giai đoạn đầu ra toán tử : Toán tử đầu ra biến đổi một đầu vào quan hệ vào một tài liệu
XML . Các toán tử có đầu vào là một ánh xạ từ mỗi thuộc tính quan hệ có trong đầu vào của một
XPath trong tài liệu XML đầu ra (đó là được tạo ra ). Một phần của XPaths được chỉ định là đường
dẫn. Điều này thường quyết định cấu trúc của các tài liệu XML. Một ví dụ về chức năng của
OutputStage được đưa ra trong hình 2. Trong ví dụ này, lập bản đồ từ thuộc tính quan hệ để XPath
như sau:

Department  /Company/Country/Dept (2) Project  /Company/Country/Employee/PName
and (3) Emp ID /Company/Country/Employee/EInfo/EmpID

Luật 1: Một sự thay đổi giá trị của cột input gây nên sự đóng hoặc mở ra của 1 phần tử
nhỏ nhất.
Luật 2: Khi chỉ có 1 cột input được thay đổi giá trị, sự lặp lại của đường dẫn áp dụng
như sau: Mỗi phần tử mở được đóng bao gồm cả các phần tử đầu tiên là 1 phần của sự
lặp lại đường dẫn.
Ví dụ:
Đặt đường dẫn bị lặp lại là :/w/x/y/z và để các Xpath của cột bị ảnh hưởng là :/w/x/y/a/b
.Sau đó các phần tử y được đóng lại và các phần tử mới được mở ra,xuống đến phần tử
cuối cùng của Xpath là biểu hiện của các cột đã bị thay đổi.
Luật 3: Khi có nhiều hơn 1 cột bị thay đổi giá trị, các phần tử là đã đóng hoặc mở, bắt
đầu với phần tử gốc gần nhất.

Hình 2: Hàm trạng thái đầu ra

Hình 3: Đặc trưng của luồng ETL





PHẦN III: KỊCH BẢN ĐẶC TRƯNG CỦA ETL VỚI XML

Hình 3 cho thấy có ba con đường ETL mẫu. Trong các con đường,có hai nguồn với
1 mục tiêu. Trong đó có XML vs các quan hệ khác. Mỗi con đường bao gồm 1 loạt các
cách để chuyển đổi dữ liệu đầu vào. Dòng 1 chuyển đổi dữ liệu XML tới 1 định dạng
quan hệ.
Flow 2 chuyển đổi dữ liệu XML tới XML và flow 3 chuyển dữ liệu quan hệ tới định

dạng XML.
Trong phần này, chúng ta sẽ mô tả chi tiết Flow 1. Tiến trình ETL biểu diễn Flow1
đọc 1 tập hợp các tài liệu XML được lưu trữ trong cở sở DL. Chuyển đổi các tài liệu và
với mục tiêu cuối cùng là viết chúng thành các CSDL quan hệ. Các bảng nguồn có chưa
1 cột XML giữ các nội dung nguồn của các tài liệu Documents. Tất cả các nguồn
Documents phù hợp với phần tử chứa “Company” được mô tả trong hình 4. Bây giờ
chúng ta đọc chi tiết từng bước thực hiện của một Flow.
Bước 1: Đọc các bảng điều hành XML chỉ cần đọc những tài liệu XML từ cơ sở dữ
liệu và đầu ra của những operator tiếp theo.

Hình 4: Đầu ra của bảng đọc toán tử XML

Hình 5: Đẳng cấu trúc kết nối toán tử
Bước 2: Equi-Hierarchical Join operator cho phép các thuộc tính: : {scope:
Company/Country, left vector : Department, right vector: Employee, join key :
Department/DeptCode = Employee/DeptCode, result=Dept2//Emp2 }. Cho mỗi cây con
chứa “Country” trong tài liệu đầu vào của XML ,các operator tìm kiếm các tập
employees đang làm việc trong mỗi gian hàng (department) trong country tương ứng và
tạo nên các tên mới của các phần tử (“Dept2”) cho mỗi thuộc tính gian
hàng(Department) trong đó có tất cả các employees làm việc trong department đó.
Bước 3: Các operator tập hợp các tham số sau: {scope: Dept2, aggregated vector=
Dept2/Employee, aggregate key: Dept2/DeptCode, aggregate function
=sum(Dept2/Employee/salary) result= Dept2/totalSalary }. Các operator tìm kiếm tổng
số tiền lương của tất cả các nhân viên trong 1 department và thêm vào tài liệu XML
phần tử là “TotalSlary”.

Bước 4: Cuối cùng các operator dùng máy hủy các tài liệu chứa totalSalary đã
được sửa đổi trong các tài liệu XML trogn CSDL quan hệ.Các thuộc tính của các
Operator là : {scope: Dept2vector, totalSalary=/Company/Country/Dept2/totalSalary
}.

Chú ý rằng trong mỗi bước của các ETL Flow trên,cho mỗi phạm vi (ví dụ : Mỗi
nút “Country”) có đầu ra bao gồm toàn bộ dữ liệu đầu vào (trong nút “country ”) cùng
với kết quả của chuyển đổi áp dụng cho các dữ liệu bên trong phạm vi (ví dụ :Cây con
của “Country”).XPEDIA cũng hỗ trợ tối ưu hóa khác chẳng hạn như loại bỏ giả phụ
thuộc thông qua đồ thị tuyến tính để mạch hở đồ thị viết lại, loại bỏ lĩnh vực chết
thông qua phân tích sử dụng và tài liệu trực tuyến lớn với mô hình khung ,chi tiết có
thể bỏ qua do thiếu không gian. Tiếp theo, chúng ta trình bày các chức năng ETL của
XPEDIA.










PHẦN IV: TỐI ƯU HÓA ELT TRONG XPEDIA

Thời gian gần đây đã thấy một sự gia tăng của cơ sở dữ liệu với nguồn gốc hỗ trợ
XML. Cơ sở dữ liệu như DB2 9, Oracle 11g và SQL.Tài liệu Server 2005 lưu trữ XML
trong định dạng gốc và có XQuery sẵn có và các công cụ truy vấn SQL / XML. Các tính
năng quan trọng khác của các cơ sở dữ liệu là họ cho phép người dùng xác định chỉ số
trên các tài liệu XML . Nếu một phần của quá trình xử lý liên quan đến công việc ETL
được thực hiện bên trong cơ sở dữ liệu , sau đó nó có thể sử dụng các chỉ mục XML để
làm giảm đáng kể thời gian thực hiện công việc . Do đó mục tiêu của ETL là thực hiện các
công việc với CSDL.Điều này được thực hiện bằng cách tạo 1 câu truy vấn SQL/XML mà
các công việc tương tự như trong 1 hoặc nhiều hơn 1 bước trong các Flow của ETL.Ví
dụ,dòng 1 từ XML có nguồn dữ liệu để RDBMS trong hình 3 có thể được biểu diễn bởi 1

câu truy vẫn SQL/XML.Do đó công việc sửa đổi sẽ có 1 Single Read Table điều hành sẽ
xuất trực tiếp các bản ghi quan hệ cho các WriteTable nạp.
Một ưu điểm khác của ELT là giảm kích thước của dữ liệu mà cần phải được di chuyển
giữa các nguồn và mục tiêu. Đây là đặc biệt đúng khi công việc liên quan đến việc đọc dữ
liệu XML và chuyển nó vào một định dạng quan hệ (Ví dụ flow1 trong hình 3) . Chú ý
rằng kích thước của nguồn tài liệu XML (Trong đó bao gồm 1 loạt các thẻ XML ) sẽ lớn
hơn đáng kể các bản ghi quan hệ được tạo ra trong đầu ra. Trong khi chuyển đổi 1 công
việc trong ETL (đọc dữ liệu XML và chuyển nó qua định dạng quan hệ) tới flow
ETL.XPEDIA cố gắng thúc đẩy hiệu suất xử lý tối đa bên trong CSDL.Điều này giúp giảm
chi phí I/O và đóng góp tỉ lệ của thời gian thực hiện tổng thể.
Do đó, chuyển đổi 1 công việc của ETL thành 1 flow ETL có thể cung cấp các lợi thế
đáng kể và chúng ta phải thực hiện các nhiệm vụ sau:
1. Viết lại flow ETL về các operator đơn giản.
2. Chuyển đổi mỗi một ETL vào 1 truy vấn XML/SQL.
3. Kết hợp các câu truy vấn XML/SQL của các operator thành một câu truy vấn
XML/SQL .
4. Chuyển đổi các câu truy vấn SQL/XML thành nhiệm vụ được định nghĩa trong ETL
để có thể thực hiện trên XPEDIA.
Chúng ta sẽ giải thích các bước trên trong vấn đề sau.

4.1 Viết lại các flow ETL thành các Operator đơn giản
Hầu hết các Operator trong XPEDIA có thể được chuyển đổi thành các câu truy
vấn SQL/XML . Tuy nhiên , một số các Operator như OutputStage khá phức tạp. Do
đó rất khó để tạo ra các truy vấn SQL/XML trực tiếp cho các Operator như vậy, chúng
ta vượt qua vấn đề này bằng các viết lại các Operator phức tạp bằng cách sử dụng tập
hợp đơn giản của các Operator mới. Trong phần này sẽ mô tả thuật toán để chuyển đổi
các Operator OutputStage thành 1 chuỗi các Operator đơn giản , cụ thể là (i )XMLIZE
Và (ii) Sibling Group-by.
XMLIZE Operator: Được chuyển qua bản ghi quan hệ trong 1 tài liệu XML flat,
Giản đồ của một tài liệu XML flat rất giống với các lược đồ quan hệ và được đưa ra trong

hình 6. Như đầu ra của các Operator này là một tài liệu XML flat, chúng ta cần phải thực
hiện các hoạt động khác nhau trên đầu ra để có được tài liệu XML trong định dạng phân
cấp mong muốn.Điều này đòi hỏi phải sử dụng các operator đặc biệt được giải thích tiếp
theo

Hình 6: Flat XML Documents Schema

Sibling Group-by Operator : Là một operator đặc biệt để chuyển đổi 1 tài liệu
XML flat vào 1 định dạng phân cấp . Các Sibling Group-by Operator như tên cho thấy ,
không chỉ 1 Group-by giữa các Sibling ngay trong phạm vi ví dụ, mà cho phép chúng ta
tổ chức dữ liệu đầu vào. Cho 1 yếu tố thiết lập giá trị ‘’s” và 1 tập hợp các thuộc tính
Group-by trong s.(mà phải là nguyên tử -giá trị phần tử ). Nó nhóm tất cả các bản ghi
“contigous” trong s bởi các giá trị trong thuộc tính Group-by. Do đó s được thay thế
trong output bởi 1 tập hợp có chứa :a)nhóm theo các thuộc tính.b) Cho mỗi giá trị
“contigous ” cho chúng 1 bộ lồng nhau các bản ghi “contigous ” trong s đó có cùng giá trị
của các thuộc tính Groups-by.
Hình 7 cho thấy hiệu quả của việc áp dụng Sibling Groups-by trên 1 tài liệu XML
mẫu.Trong ví dụ này, chúng ta đã áp dụng Sibling Groups-by vào nút
/Company/Country/Dept . Nút này có 2 giá trị khác nhau là CS và EE. Do đó Sibling
Groups-by operator tạo ra 2 cây con, mỗi cây cho 1 giá trị đặc biệt trong các nút liền kề
nhau.

Hình 7: Sibling Groups-by Operator
Xem xét việc chuyển đổi ví dụ được đưa ra trong hình 2 mà tạo ra một tài liệu XML
từ dữ liệu quan hệ nhất định trong này, Ví dụ path được lặp lại là
/Company/Country/Employee/Einfo/EmpID”. Để tạo ra các tài liệu XML tương ứng với
ví dụ này , bước đầu tiên là chuyển đổi dữ liệu quan hệ thành các định dạng XML sử dụng
các nhà điều hành XMLIZE. Sau đó chúng ta liên tục áp dụng Sibling Groups-by Operator
như sau:
1. Áp dụng trên nút /Company/Country với Groups của nút thiết lập

/Company/Country/Dept và thiết lập phạm vi tới /Company. Các output trong hoạt
động này được thể hiện trong hình 7.
2. Áp dụng Sibling Groups-by operator trên output của bước 1. Tập thuộc tính có giá
trị là /Company/Country/Employee và nhóm lại bằng các thuộc tính được thiết lập
tới /Company/Country/Employee/Pname. Các output trong bước này cho chúng ta
tài liệu XML Cần thiết thể hiện trong hình 2.
Do đó các operator OutputStage được đại diện bới Xmlize operator tiếp theo trong trình
tự của 1 hoặc nhiều Sibling Groups-by operator. Các thuật toán để chuyển đổi các operator
để Outputstage tập hợp các operator đơn giản được đưa ra dưới đây.
B1: Áp dụng operator XMLize trên dữ liệu quan hệ để có được tài liệu XML flat.
B2: Đối với tất cả các nút đầu ra ngoại trừ nút đầu ra lặp đi lặp lại:
 Mức độ của một nút đầu ra là mức độ mà tại đó XPath của nó giao cắt với XPath
nút đầu ra của sự lặp lại.
 Bắt đầu từ trên xuống dưới (dựa trên mức độ), áp dụng Sibling Group-By cho tất cả
các nút mà gặp nhau ở cùng một vị trí trên XPath nút đầu ra của sự lặp lại.
B3: Sử dụng operator project để thêm và thả các nút, để mang lại height của tất cả
các nút đầu ra ở đúng vị trí.
B4: Sử dụng project operator để thay đổi tên của nút.

4.2 Truy vấn Generating và Merging

XPEDIA ETL có một tập hợp các thuật toán cho tạo ra các truy vấn SQL / XML cho
mỗi operator .Như truy vấn tương ứng với mỗi operator cố định, việc sử dụng tối ưu được
xây dựng trước các kỹ thuật / quy tắc cho việc merging các truy vấn SQL / XML của
operator liền kề. Là tập hợp các operator là đầy đủ, do thiếu không gian, trong bài viết
này chúng ta chỉ phác thảo kỹ thuật để tạo ra các truy vấn SQL / XML tương ứng với các
Sibling Group-by operator và cũng trình bày các kỹ thuật cho việc merging các
truy vấn tương ứng với một chuỗi các các operator.



Hình 8: SQL/XML for Sibling Group-By
Như đã thấy trong phần trước, một sử dụng điển hình của Sibling Group –by operator
là tổ hợp tài liệu XML đó là được tạo ra bởi các operator XMLIZE. Nhận thấy rằng tính
chất độc đáo của operator này là nó chỉ làm một Sibling Group –by operator. Do đó, chúng
ta không thể sử dụng "nhóm" điều khoản có trong SQL / XML như nó sẽ nhóm lại với
nhau ngay cả những giá trị mà có thể không được "liền kề" trong tài liệu XML đầu vào.
Để quyết vấn đề này chúng ta tạo ra một thuộc tính thêm vào dữ liệu đầu vào có giá trị có
thể được sử dụng bởi giao diện "Groups" khoản của các truy vấn SQL / XML. Điều này
có nghĩa rằng, đối với các dữ liệu thể hiện trong hình 2, giá trị của các thuộc tính mới sẽ
được nói 1 cho hai bộ đầu tiên (<CS,C++,123> và <CS,C++,253>) và 2 cho bản ghi thứ
ba. Tạo ra thuộc tính này sử dụng SQL là một khó khăn hoạt động. Chúng ta sử dụng các
chức năng OLAP trong SQL để tạo ra các thuộc tính trong một bảng tạm thời mà cũng có
chứa phần còn lại của các thuộc tính hiện tại trong bảng đầu vào.
Một khi bảng tạm thời được tạo ra, chúng ta sử dụng nhóm quy định tại khoản
trên thuộc tính 'J1' mới để tạo ra các đầu ra mong muốn. Các mẫu SQL / truy vấn XML
trong đó sử dụng một bảng tạm thời để tạo ra sản lượng tương ứng với các Sibling Group-
By đề cập trong Hình 7 thể hiện trong hình 8.
Chú ý rằng các truy vấn hoạt động trên một bảng tạm thời.Chính một l ợi thế của việc
sử dụng bảng tạm thời là chúng ta có thể định nghĩa chỉ số trên các thuộc tính của bảng.
Điều này tăng tốc xử lý lên của bất kỳ tham gia hiện diện trong các truy vấn SQL / XML.
Một khi các truy vấn SQL / XML được tạo ra cho mỗi Sibling Groups-by operator , chúng
có thể được merging với nhau cũng như các operator XMLIZE . XPEDIA ETL sử dụng
một bộ các quy tắc cho việc sáp nhập các truy vấn SQL / XML. Để cung cấp cho một cách
của quá trình hợp nhất , chúng tôi cung cấp một ví dụ của sáp nhập truy vấn SQL / XML
trong hình 9 cho công việc trong ETL được đưa ra trong hình 2.
Các sáp nhập truy vấn SQL / XML sử dụng một khoản groups-by cho mỗi Sibling
Groups-by operator.


Hình 9: Merged SQL/XML query for OutputStage


4.3 Tạo ra các định nghĩa công việc ELT

Một khi các truy vấn SQL / XML đã được tạo ra, nhiệm vụ tiếp theo là sắp xếp
chúng trở lại công việc định nghĩa XPEDIA. Đây là một quá trình đơn giản trong đó các
truy vấn SQL / XML được tạo ra là ánh xạ tới một phần tử bảng đọc và phần còn lại của
giai đoạn cũng như vậy.
Sử dụng các thủ tục trên, XPEDIA có thể tận dụng lợi thế của khả năng xử lý XML
của cơ sở dữ liệu. Tuy nhiên nhận thấy rằng chúng ta không thể tạo ra một luồng ELT khi
dữ liệu có trong một cơ sở dữ liệu mà không có XML hỗ trợ hoặc hiện diện trong cùng
một tập tin. Ngay cả trong trường hợp như vậy, XPEDIA cải thiện khả năng mở rộng
bằng cách sử dụng một kỹ thuật xử lý song song mới lạ được giải thích ở sau.




































PHẦN V: XỬ LÝ SONG SONG CỦA DỮ LIỆU XML

Kích thước của một hàng/bản ghi trong dữ liệu quan hệ hiếm khi lớn hơn một vài Kb.
Tuy nhiên, chúng tôi quan sát từ một số khách hàng rằng đầu vào XML để tích hợp dữ liệu
đầu vào có xu hướng tổng hợp lớn bao gồm một số đối tượng nhỏ hơn. Do đó các tài liệu
XML của thứ tự từ 2-3 GB là khá phổ biến trong thực tế. Trong phần này, chúng tôi trình
bày một kỹ thuật để xử lý song song như vậy như các tài liệu XML lớn.
Song song có thể đạt được theo hai cách khác nhau cụ thể là, luồng song song và song
song phân vùng. Luồng song song xảy ra khi các toán tử khác nhau làm việc trên các tài
liệu XML khác nhau cùng một lúc. Một song song như vậy được hỗ trợ bởi XPEDIA và
xảy ra bất cứ khi nào nhiều toán tử hoạt động trên một dòng XML tài liệu theo cách nối
tiếp. Tuy nhiên , hình thức này song song có thể cung cấp lợi ích hạn chế đối với các tài
liệu XML lớn như mỗi toán tử sẽ phải xử lý tất cả các tài liệu đó đòi hỏi bộ nhớ lớn và sức

mạnh xử lý . Thật không may, động cơ xử lý ETL hiện nay chỉ hỗ trợ luồng song song cho
dữ liệu XML dẫn đến hiệu suất kém hơn. Các chìa khóa để giải quyết vấn đề khả năng mở
rộng là việc sử dụng song song phân vùng - một kỹ thuật được hỗ trợ bởi XPEDIA . Phân
vùng song song đạt được khi nhiều trường hợp của công việc ETL được thực hiện song
song trên máy khác nhau / xử lý với từng trường hợp làm việc trên các phần khác nhau các
tài liệu XML . Điều này làm giảm kích thước của tài liệu XML mà cần phải được xử lý
trên mỗi bộ vi xử lý qua đó nâng cao khả năng mở rộng . Chìa khóa để đạt phân song song
, như tên cho thấy , là phân vùng lớn của tài liệu XML. Tuy nhiên , bản chất thứ bậc của
XML làm nhiệm vụ phân vùng một nhiệm vụ vốn đã phức tạp . Chúng tôi phác thảo những
thách thức khác nhau để đạt được song song phân vùng và đề xuất một kỹ thuật để xác
định đúng loại phân vùng trong phần 5.1. Sau khi phân vùng chính xác đã được xác định,
nhiệm vụ tiếp theo là để thực sự tạo ra các phân vùng một cách hiệu quả trong một tài liệu
XML và không làm một phân tích đầy đủ các tài liệu. Chúng tôi trình bày như một kỹ thuật
tạo ra các phân vùng trong phần 5.2. Một trong những hoạt động tốn kém (về thời gian)
hơn là các tài liệu XML xác nhận giản đồ của họ. Chúng tôi cho thấy trong Phần 5.3 rằng
lược đồ nhiệm vụ xác nhận cũng có thể được thực hiện song song trên nhiều máy tính do
đó làm giảm thời gian thực hiện nó đáng kể.

5.1 Xác định các phân vùng tối ưu

Như đã đề cập trước đó, song song phân vùng liên quan đến việc phân chia nhiệm vụ
sau đây : (i) phân vùng một tài liệu XML lớn vào nhiều phần , (ii) chạy nhiều trường hợp
của một công việc ETL trên nhiều máy / xử lý , (iii) mỗi trường hợp công việc hoạt động
trên một phân vùng khác nhau của tài liệu XML và (iv ) cuối cùng, sáp nhập đầu ra của các
trường công việc. Để đạt được một song song hiệu quả, mỗi phân vùng cần phải tự cung
tự cấp , tức là , các dữ liệu theo yêu cầu của mỗi trường hợp công việc nên được chứa trong
phân vùng có sẵn cho nó và không có dữ liệu nên chia sẻ qua phân vùng. Nếu điều này
không được đảm bảo sau đó nó sẽ đòi hỏi thông tin liên lạc giữa các bộ vi xử lý hoặc cách
khác bản sao của cùng một dữ liệu sẽ phải được cung cấp cho nhiều bộ vi xử lý , do đó sẽ
làm giảm hiệu quả của các thuật toán song song . Để làm nổi bật hơn nữa này , chúng tôi

trình bày một ví dụ phân vùng XML.
Ví dụ: Hãy xem xét một công việc bao gồm hai bước đầu tiên của Công việc ETL nêu
tại mục 3. Đầu vào công việc là một tài liệu XML có lược đồ được trình bày trong hình 4.
việc nối các toán tử trong công việc ETL tham gia hiện tại dữ liệu trong cây con Employee
với hiện tại dữ liệu tại cây con Department. Cho công việc này nếu chúng ta phân vùng tài
liệu XML thành hai phần rằng tất cả các nút Department đi vào phân vùng đầu tiên và tất
cả nút Employee đi vào phân vùng thứ hai sau đó toán tử liên kết sẽ yêu cầu quyền truy
cập vào cả hai phân vùng. Do đó không song song sẽ đạt được như sẽ không có giảm kích
thước của dữ liệu được xử lý bởi mỗi toán tử. Vì vậy, các kỹ thuật phân vùng cần đảm bảo
rằng các dữ liệu theo yêu cầu của một toán tử được chứa trong phân vùng có sẵn cho nó.
Xem xét một kỹ thuật phân vùng, nơi mà chúng tôi phân vùng dữ liệu ở mức độ "
/Company/Country ". Nói cách khác, nếu có 10 cây con Country cây dưới gốc (Company)
nút, sau đó các phân vùng đầu tiên sẽ bao gồm một tài liệu XML gốc ở " Company" chỉ
với 5 cây con Country đầu tiên mà là phân vùng thứ hai sẽ bao gồm 5 cây con Country tiếp
theo. Nhớ lại rằng phạm vi của toán tử là " /Company/Country " . Điều này có nghĩa là nối
toán tử xử lý từng cây con " Country " độc lập với phần còn lại. Nói cách khác, nó nối vào
các bộ phận và các dữ liệu Departmentand Employee hiện trong mỗi cây con và không
qua các cây con . Hơn nữa kết quả của mỗi cây con được tham gia cũng chứa trong đó cây
con . Do đó một phân vùng thực hiện tại mức độ /Company/Country " (được gọi là các
phân vùng nút) sẽ đảm bảo rằng tất cả các dữ liệu theo yêu cầu của từng trường hợp của
các toán tử được chứa trong các phân vùng có sẵn với nó.
Ví dụ trên nêu bật những khó khăn trong việc phân vùng một tài liệu XML cho một
công việc bao gồm một toán tử duy nhất. Như có thể tưởng tượng, vấn đề được tiếp tục
làm trầm trọng thêm cho một công việc bao gồm nhiều toán tử. Chúng tôi trình bày tiếp
theo một số chính hiểu biết sâu sắc được sử dụng bởi các thuật toán phân vùng của XPEDIA
để tìm các nút phân vùng của một tài liệu XML lớn cho một định công việc ETL.
 Cái nhìn sâu sắc 1: Các toán tử không dùy trì bất kì trạng thái nào giữa các giai đoạn
phạm vị của họ. Vì vậy, mỗi phạm vi giai đoạn khả năng có thể thuộc về một phân
vùng khác nhau.
 Cái nhìn sâu sắc 2: Một số các toán tử (như bộ lọc) thực hiện chuyển đổi trạng thái,

tức là biến đổi mà không làm duy trì trạng thái giữa các trường vector. Ví dụ, các
bộ lọc toán tử tính toán vị lọc mỗi vector và không duy trì trạng thái bất kỳ trường
hợp trên. Do đó nếu một công việc ETL bao gồm toàn bộ các toán tử như vậy, sau
đó mỗi trường hợp vector trong các đầu vào có thể có khả năng thuộc về một phân
vùng khác nhau.
 Cái nhìn sâu sắc 3: Một số các toán tử (như tổng hợp ) duy trì thông tin trạng thái
giữa các trường khác nhau của đầu vào của họ vectơ. Ví dụ, các toán tử tổng hợp
trong công việc ETL được đưa ra trong Mục 3 phát hiện tổng số tiền lương cho mỗi
Department trong một phạm vi dụ, tức là , cho mỗi Department riêng biệt từng cây
con " Country". Chú ý rằng nó không lưu trữ bất kỳ thông tin trạng thái trên khác
nhau nút " Department " trong mỗi cây con " Country". Do đó song song có thể đạt
được bằng cách đảm bảo rằng tất cả các cây con Employee và Department mà chia
sẻ cùng mã chứa trong một phân vùng duy nhất . Toán tử đó đều tuân theo phân
vùng như vậy được gọi là trạng thái khóa tương quan của toán tử. Trong ví dụ trên,
toán tử tổng hợp là chìa khóa liên quan như các cây con Employee có tương quan
đối với mã chính với các nút Employee được gọi là các nút tương quan cho toán tử
.
Chúng tôi trình bày tiếp theo một thuật toán trong đó sử dụng những hiểu biết này để
tìm nút phân vùng tốt nhất cho một công việc ETL
Thuật toán: Tìm phân vùng Nút
1. Cho mỗi toán tử trong việc ETL
1.1 Khởi tạo một vector có chứa tất cả các trường hợp phạm vi cho toán tử này
2. Cho mỗi toán tử trong việc ETL
Nếu các toán tử là trạng thái
2.1 Không làm gì cả
Khác nếu các toán tử là trạng thái khóa liên quan sau đó
2.2 Tạo một phân vùng cho vector bằng cách sử dụng chính cho các toán tử
2.3. Nếu một vector chứa các cây bắt nguồn từ ở nút tương quan cho toán tử này sau
đó hợp nhất các vectơ với các vectơ phân vùng đã tạo khác
2.4 Liên minh tất cả các vectơ có chứa các cây bắt nguồn từ dưới đây phạm vi của các

toán tử
Kết quả: Mỗi vector có một gốc mà là một ứng cử viên cho phân vùng. Đầu ra gốc cao
nhất trong số tất cả các vectơ như nút phân vùng (s). Nếu có nhiều nút ở cùng một mức độ,
đầu ra nhiều nút phân vùng
Có thể là các nút phân vùng tìm thấy bởi các thuật toán ở trên là gốc của tài liệu, tức
là, không có phân vùng của tài liệu là có thể. Trong trường hợp này chúng ta vẫn có thể
phân chia một tập hợp con của toán tử trong luồng ETL. Mở rộng XPEDIA để xử lý như
vậy trường hợp là một phần của công việc tương lai của chúng tôi. Một khi nút phân vùng
đã được xác định, XPEDIA sử dụng nút phân vùng để tạo ra các phân vùng như sau:
 Kỹ thuật phân vùng Round-robin: Trong kỹ thuật này, mỗi phân vùng được các cây
con có gốc là nút phân vùng trong một vòng robin cách. Nói cách khác, ví dụ đầu
tiên của nút phân vùng đi vào phân vùng đầu tiên, phân vùng thứ hai nút thể hiện đi
vào phân vùng thứ hai và vv và vvv….
 Lược đồ lớn : Kỹ thuật phân vùng này tạo ra phân vùng dựa trên kích thước của tài
liệu XML . đưa ra một tài liệu XML mà chúng ta phải tạo ra phân vùng , sau đó kỹ
thuật phân vùng này cố gắng để tạo ra mỗi phân vùng có kích thước 1 GB. Lưu ý
chúng mà không thể tạo ra phân vùng thứ hai bằng cách trực tiếp tìm cách vị trí 1
GB trong tài liệu XML và sau đó tìm kiếm xuất hiện đầu tiên của nút phân vùng.
Điều này là do nút phân vùng gặp phải có thể xảy ra tại nhiều địa điểm trong tài liệu
XML hoặc có thể là trong một phần CDATA . Do đó kỹ thuật này tạo ra phân vùng
bằng cách lặp lại hơn các cây con bắt nguồn từ tại nút phân vùng cho đến khi nó đạt
đến vị trí 1 GB trong tập tin XML. Sau đó phân vùng thứ hai bắt đầu và cây con bắt
nguồn tại nút phân vùng tạo thành thứ hai phân vùng cho đến khi chúng ta đạt được
sự khởi đầu của thứ 3 GB vị trí trong các tập tin XML. Kỹ thuật này cũng đảm bảo
rằng mỗi phân vùng là một tài liệu XML cũng được hình thành bằng cách thêm các
nút các tài liệu gốc đến nút phân vùng vào đầu mỗi phân vùng.

5.2 Tạo phân vùng tối ưu

Sau khi tập hợp các nút phân vùng và chiến lược phân vùng đã được xác định, nhiệm

vụ tiếp theo là làm cho phân vùng đúng có sẵn để mỗi trường hợp công việc ETL. Chú ý
rằng mỗi trường hợp công việc sẽ có toàn bộ tài liệu XML có sẵn cho nó. Quá trình tạo
phân vùng liên quan đến việc phân tích cú pháp của toàn bộ tài liệu XML phân vùng đúng
cho các trường hợp công việc. Nếu chúng ta làm một phân tích đầy đủ các tài liệu XML
sau đó nó sẽ không cung cấp cho chúng tôi hiệu suất lần nữa. Do đó, khi chúng tôi giải
thích tiếp theo, XPEDIA sử dụng một "phân tích cạn" kỹ thuật để tạo ra các phân vùng.
5.2.1 Phân tích cú pháp cạn
Ý tưởng cơ bản phân tích cạn là nó phân tích chỉ những nút xảy ra giữa các nút gốc và
nút phân vùng , tức là , các nút xuất hiện trong các nút phân vùng XPath. Các quá trình
phân tích cú pháp cạn bỏ qua tất cả các nút khác do đó tránh chi phí cao liên kết với một
phân tích đầy đủ của tài liệu XML. Ví dụ , hãy xem xét một kịch bản mà chúng ta có một
tài liệu XML 4 GB phù hợp với sơ đồ được đưa ra trong hình 4. Hãy để cho nút phân vùng
được \Company\ Country và chúng ta phải tạo ra phân vùng thứ hai (trong số các phân
vùng 4) bằng cách sử dụng lược đồ lớn. Trong trường hợp này XPEDIA hiện một phân
tích cú pháp nông của tài liệu XML cho đến khi nó đạt đến GB thứ hai của tập tin XML.
Trong phân tích cạn , XPEDIA chỉ trông cho sự khởi đầu và kết thúc của nút " Company "
và " Country ". Tất cả các nút khác bỏ qua. Một khi nó đạt đến GB thứ hai nó xuất ra các
cây con bắt nguồn từ các nút " Country" cho đến khi nó đạt đến sự khởi đầu của GB thứ
ba. Tại thời điểm này nó cho biết thêm một đóng " Company " và phân vùng thứ hai này
tạo ra như đầu ra. Chiến lược này giúp XPERIA để tạo ra các phân vùng trong một lần duy
nhất trên tài liệu XML đầu vào.
Tuy nhiên , quá trình phân tích cú pháp nông có thể trở nên phức tạp khi có nhiều nút
phân vùng. Trường hợp này được xử lý bởi XPEDIA bằng cách tìm kiếm các nút xuất hiện
trong XPaths của tất cả các nút phân vùng. Chúng tôi giải thích chi tiết của phân tích cạn
thuật toán được sử dụng bởi XPEDIA với sự giúp đỡ của ví dụ được đưa ra trong Hình 10
. Các tài liệu XML trong con số có ba các nút phân vùng /A/ B/C/D# , /A/B/C/E#, /A/B/F#
. XPEDIA duy trì một bộ gọi là ValidExtension cho mỗi nút mà xuất hiện trong XPath của
một hay nhiều hạch phân vùng. Các ValidExtensionset cho một nút B nên chứa các thiết
lập của tất cả các nút xuất hiện sau khi B trong bất kỳ XPaths nút phân vùng. Do đó,
ValidExtension cho B sẽ là tập { C , F # } . XPEDIA cũng duy trì một stack được gọi là

PathStack . Bất cứ khi nào chúng ta gặp phải một nút đó là một phần của XPath ít nhất một
nút phân vùng của , nút đó được đẩy sang PathStack . Nếu nút B là ở đầu PathStack sau đó
phân tích cú pháp nông được thực hiện bằng cách tìm kiếm (i) đóng các nút B hoặc (ii) tìm
kiếm các nút có trong ValidExtension bộ B. XPEDIA bỏ qua tất cả các nút khác giúp nó
để tránh chi phí cao liên kết với một phân tích đầy đủ . Nếu chúng ta thấy việc đóng của
các nút đó là ở trên cùng của ngăn xếp, chúng tôi bật nó từ PathStack . Để minh họa cho
thuật toán thêm , xem xét một kịch bản mà chúng ta đang ở nút B trong hình 9. Trong
trường hợp này, chúng ta có thể đẩy một nút C , hoặc nút F # trên stack. Tất cả các nút
khác được bỏ qua vì họ không phải là một phần của bất kỳ XPath dẫn đến các nút phân
vùng.
Bất cứ khi nào một nút phân vùng được tìm thấy, nếu chúng tôi đã không đạt được cần
phân vùng trong tài liệu XML, chúng ta bỏ qua các cây con XML bắt nguồn tại nút phân
vùng. Nếu mặt khác, chúng tôi có đạt các phân vùng cần thiết (ví dụ, GB thứ hai trước đó
của ví dụ chúng tôi) đầu ra chúng tôi phụ cây bắt nguồn từ tại nút phân vùng.