ĐẠI HỌC QUỐC GIA TP. HCM
TRƯỜNG ĐẠI HỌC BÁCH KHOA
---------------------

NGUYỄN NGỌC THIÊN AN

BẢO VỆ TÍNH RIÊNG TƯ
TRONG XỬ LÝ CÂU TRUY VẤN
TRÊN DỊNG DỮ LIỆU

Chun ngành: Khoa Học Máy Tính
Mã số:

604801

LUẬN VĂN THẠC SĨ

TP. HỒ CHÍ MINH, tháng 12 năm 2012


CƠNG TRÌNH ĐƯỢC HỒN THÀNH TẠI
TRƯỜNG ĐẠI HỌC BÁCH KHOA - ĐHQG - HCM
Cán bộ hướng dẫn khoa học: PGS. TS. ĐẶNG TRẦN KHÁNH . . . . . . . . . . . . . . . . . .
(Ghi rõ họ, tên, học hàm, học vị và chữ ký)
Cán bộ chấm nhận xét 1:

TS. NGUYỄN CHÁNH THÀNH . . . . . . . . . . . . . . . . . .

(Ghi rõ họ, tên, học hàm, học vị và chữ ký)
Cán bộ chấm nhận xét 2:

PGS. TS. VŨ THANH NGUYÊN . . . . . . . . . . . . . . . . .

(Ghi rõ họ, tên, học hàm, học vị và chữ ký)
Luận văn Thạc sĩ được bảo vệ tại Trường Đại học Bách Khoa, ĐHQG TP. HCM, ngày
24 tháng 12 năm 2012.
Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm:
(Ghi rõ họ, tên, học hàm, học vị của Hội đồng chấm bảo vệ luận văn thạc sĩ)
1. PGS. TS. THOẠI NAM, CT
2. TS. NGUYỄN CHÁNH THÀNH, PB 1
3. PGS. TS. VŨ THANH NGUYÊN, PB 2
4. PGS. TS. ĐẶNG TRẦN KHÁNH, UV
5. TS. HUỲNH TƯỜNG NGUYÊN, TK
Xác nhận của Chủ tịch Hội đồng đánh giá LV và Trưởng Khoa quản lý chuyên ngành
sau khi luận văn đã được sửa chữa (nếu có).
CHỦ TỊCH HỘI ĐỒNG

TRƯỞNG KHOA KH&KTMT

PGS. TS. Thoại Nam

PGS. TS. Thoại Nam


ĐẠI HỌC QUỐC GIA TP.HCM

CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM

TRƯỜNG ĐẠI HỌC BÁCH KHOA

Độc lập - Tự do - Hạnh phúc


NHIỆM VỤ LUẬN VĂN THẠC SĨ
Họ tên học viên:

NGUYỄN NGỌC THIÊN AN

MSHV:

10071046

Ngày sinh:

10 – 02 – 1987

Nơi sinh:

TP.HCM

Chuyên ngành:

Khoa Học Máy Tính

Mã số :

604801

I. TÊN ĐỀ TÀI: Bảo Vệ Tính Riêng Tư Trong Xử Lý Câu Truy Vấn Trên Dòng Dữ
Liệu
II. NHIỆM VỤ VÀ NỘI DUNG: Xây dựng giải pháp bảo vệ tính riêng tư cho dữ liệu
cá nhân trong xử lý câu truy vấn trên Dòng Dữ Liệu.

III. NGÀY GIAO NHIỆM VỤ:

04 – 07 – 2011

IV. NGÀY HOÀN THÀNH NHIỆM VỤ:

23 – 11 – 2012

V. CÁN BỘ HƯỚNG DẪN:

PGS. TS. ĐẶNG TRẦN KHÁNH
Tp. HCM, ngày 08 tháng 03 năm 2013

CÁN BỘ HƯỚNG DẪN

CHỦ NHIỆM BỘ MÔN ĐÀO TẠO

PGS. TS. Đặng Trần Khánh

PGS. TS. Đặng Trần Khánh

TRƯỞNG KHOA KH&KTMT

PGS. TS. Thoại Nam


Bảo vệ tính riêng tư trong xử lý câu truy vấn trên dịng dữ liệu

LỜI CẢM ƠN
Trước hết, tơi xin gửi lời cảm ơn đến giảng viên hướng dẫn luận văn của minh –

PGS. TS. Đặng Trần Khánh - đã tận tình hướng dẫn, động viên và giúp đỡ tơi rất
nhiều trong thời gian thực hiện luận văn này.
Tôi cũng xin cảm ơn tổ chức JICA đã tạo điều kiện cho tôi tham gia dự án nghiên
cứu liên quan đến đề tài luận văn và hỗ trợ kinh phí đi dự hội nghị trong q trình
tơi thực hiện luận văn này.
Cuối cùng, tơi xin chân thành cảm ơn gia đình, bạn bè và các thành viên trong
DSTAR-Lab đã hỗ trợ tôi trong suốt thời gian qua.
25 – 11 – 2012

Nguyễn Ngọc Thiên An

i


Bảo vệ tính riêng tư trong xử lý câu truy vấn trên dịng dữ liệu

TĨM TẮT
Tốc độ phát triển nhanh chóng của cơng nghệ thiết bị cảm biến, sự mở rộng của hệ
thống mạng thông tin và sự bùng nổ của ứng dụng thương mại điện tử là những
động lực thúc đẩy cho sự phát triển vượt bậc của ứng dụng dịng dữ liệu. Tương tự
các loại hệ thống thơng tin khác, vấn đề bảo vệ tính riêng tư cho các cá nhân có
thơng tin xuất hiện trong dịng dữ liệu là rất cần thiết. Tuy nhiên, các yêu cầu về
thời gian và lượng tài nguyên cần có cho việc xử lý truy vấn trong thời gian thực
vẫn là những thách thức đối với các giải pháp bảo vệ tính riêng tư cho dòng dữ
liệu. Trong luận văn này, chúng tơi trình bày một giải pháp cải tiến được tích hợp
kỹ thuật lấy mẫu theo reservoir có kích thước thay đổi với một giải thuật làm mờ
để bảo vệ tính riêng tư cho dòng dữ liệu. Giải pháp đề xuất của chúng tôi cung cấp
dữ liệu đã làm mờ để đưa ra kết quả truy vấn gần đúng trong thời gian xử lý hợp
lý. Loại kết quả gần đúng này thích hợp cho các ứng dụng dạng thống kê, tổng hợp.
Đặc biệt, giải pháp mới đạt được kết quả tốt hơn về mặt thời gian xử lý câu truy

vấn so với giải thuật làm mờ gốc khi được đánh giá về mặt lý thuyết và thực
nghiệm.

ii


Bảo vệ tính riêng tư trong xử lý câu truy vấn trên dòng dữ liệu

ABSTRACT
The rapid development of sensor technologies, the broadening of information
networks and the evolution of e-commerce applications are motivations for the
prominent growth of data stream applications. In a similar way to other kinds of
information systems, it is essential to protect privacy for owners of the
information in those streams. However, requirements of huge amounts of time
and resources for query processing in real-time are challenging issues for privacy
preserving solutions in data streams. In this thesis, we present a modified method
integrating a variable reservoir sampling technique with a k-anonymizing
algorithm to protect privacy on data streams. Our suggestion provides
anonymized data to give approximate query answers which are possible to accept
and as good as the exact ones in many contexts such as aggregation and statistics
applications. Moreover, the new solution has faster query processing time than
the one of the original k-anonymizing algorithm in both theory and experiment
results.

iii


Bảo vệ tính riêng tư trong xử lý câu truy vấn trên dịng dữ liệu

LỜI CAM ĐOAN

Tơi xin cam đoan đây là cơng trình nghiên cứu của bản thân. Các số liệu, kết quả
trình bày trong luận văn là trung thực và chưa từng được ai công bố trong bất kỳ
cơng trình nào trước đây.
25 – 11 – 2012

Nguyễn Ngọc Thiên An

iv


Bảo vệ tính riêng tư trong xử lý câu truy vấn trên dịng dữ liệu

MỤC LỤC
LỜI CẢM ƠN ............................................................................................................................................... i
TĨM TẮT ..................................................................................................................................................... ii
ABSTRACT .................................................................................................................................................iii
LỜI CAM ĐOAN ....................................................................................................................................... iv
MỤC LỤC ..................................................................................................................................................... v
DANH MỤC BẢNG ............................................................................................................................... viii
DANH MỤC HÌNH ẢNH ........................................................................................................................ ix
DANH MỤC CHỮ VIẾT TẮT ................................................................................................................ x
CHƯƠNG 1 GIỚI THIỆU ....................................................................................................................... 1
1.1.

Giới thiệu đề tài ..................................................................................................................... 1

1.2.

Mục đích nghiên cứu ........................................................................................................... 3


1.3.

Ý nghĩa khoa học và thực tiễn của đề tài .................................................................... 3

CHƯƠNG 2 TỔNG QUAN VỀ DÒNG DỮ LIỆU.............................................................................. 5
2.1.

Định nghĩa ................................................................................................................................ 5

2.2.

Cấu trúc ..................................................................................................................................... 5

2.3.

Đặc tính ..................................................................................................................................... 7

2.4.

Phân loại ................................................................................................................................... 8

2.5.

Ngơn ngữ truy vấn trên dịng dữ liệu .......................................................................... 8

2.6.

Hệ quản trị dòng dữ liệu .................................................................................................... 9

2.7.


Lĩnh vực ứng dụng ............................................................................................................ 11

2.8.

Các bài tốn của dịng dữ liệu....................................................................................... 12

2.9.

Một ứng dụng minh họa.................................................................................................. 13

CHƯƠNG 3 XỬ LÝ CÂU TRUY VẤN TRÊN DÒNG DỮ LIỆU ................................................ 15
v


Bảo vệ tính riêng tư trong xử lý câu truy vấn trên dòng dữ liệu
3.1.

Thách thức ............................................................................................................................ 15

3.2.

Kỹ thuật xử lý ...................................................................................................................... 16

3.2.1.

Stream Filtering [5].................................................................................................... 16

3.2.1.1. Precise Filtering .................................................................................................. 16
3.2.1.2. Data Merging ........................................................................................................ 17

3.2.1.3. Data Dropping (Load Shedding) .................................................................. 17
3.2.2.

Punctuations [5] .......................................................................................................... 19

3.2.3.

Windowing [5] ............................................................................................................. 22

3.2.4.

Synopses ......................................................................................................................... 23

3.2.4.1. Sampling (Phương pháp lấy mẫu) .............................................................. 24
3.2.4.2. Histograms ............................................................................................................ 24
3.2.4.3. Wavelets ................................................................................................................. 25
3.2.4.4. Sketches .................................................................................................................. 25
3.2.4.5. Micro-cluster based summarization .......................................................... 25
3.2.5.
3.3.

Tổng kết .......................................................................................................................... 26

Kiến trúc hệ thống xử lý truy vấn trên dòng dữ liệu ......................................... 28

CHƯƠNG 4 VẤN ĐỀ BẢO VỆ TÍNH RIÊNG TƯ ........................................................................ 30
4.1.

Bảo mật thơng tin .............................................................................................................. 30


4.1.1.

Định nghĩa ...................................................................................................................... 30

4.1.2.

CIA triad .......................................................................................................................... 31

4.2.

Bảo vệ tính riêng tư .......................................................................................................... 33

4.3.

Bảo vệ tính riêng tư trong dịng dữ liệu .................................................................. 36

4.4.

Tấn công liên kết ................................................................................................................ 38

4.5.

K – Anonymity ..................................................................................................................... 40

vi


Bảo vệ tính riêng tư trong xử lý câu truy vấn trên dịng dữ liệu
4.6.


Mức độ mất thơng tin ....................................................................................................... 42

4.7.

Các giải thuật bảo vệ tính riêng tư trên dịng dữ liệu ........................................ 43

CHƯƠNG 5 GIẢI PHÁP ĐỀ XUẤT................................................................................................... 45
5.1.

Tổng quan về giải pháp ................................................................................................... 45

5.2.

Phương pháp lấy mẫu ...................................................................................................... 47

5.2.1.

Phương pháp lấy mẫu theo reservoir có kích thước cố định .................. 48

5.2.2.

Phương pháp lấy mẫu theo reservoir có kích thước thay đổi ................ 50

5.3.

Phương pháp làm mờ dữ liệu SKY ............................................................................. 51

5.4.

Phương pháp bảo vệ tính riêng tư cho dòng dữ liệu ......................................... 52


CHƯƠNG 6 ĐÁNH GIÁ và KẾT LUẬN .......................................................................................... 62
6.1.

Đánh giá theo lý thuyết ................................................................................................... 62

6.1.1.

Hiệu quả của việc xử lý câu truy vấn .................................................................. 62

6.1.1.1. Thời gian xử lý ..................................................................................................... 62
6.1.1.2. Tài nguyên sử dụng ........................................................................................... 65
6.1.2.

Chất lượng của kết quả truy vấn .......................................................................... 66

6.2.

Đánh giá theo thực nghiệm ........................................................................................... 66

6.3.

Tổng kết ................................................................................................................................. 74

6.3.1.

Ưu điểm ........................................................................................................................... 74

6.3.2.


Khuyết điểm .................................................................................................................. 75

6.3.3.

Hướng phát triển ........................................................................................................ 75

DANH MỤC CÁC CƠNG TRÌNH KHOA HỌC ............................................................................... 76
TÀI LIỆU THAM KHẢO ....................................................................................................................... 77
PHỤ LỤC ................................................................................................................................................... 80
LÝ LỊCH TRÍCH NGANG .................................................................................................................. 109
vii


Bảo vệ tính riêng tư trong xử lý câu truy vấn trên dòng dữ liệu

DANH MỤC BẢNG
Bảng 2.1 – Dòng dữ liệu ghi nhận thông số của một hệ thống điện ................................. 6
Bảng 2.2 – Dòng dữ liệu ghi nhận thông tin của một router ............................................... 6
Bảng 2.3 – So sánh DSMS và DBMS ................................................................................................. 9
Bảng 3.1 – Một số mẫu để tạo phần tử dấu ngắt .................................................................... 20
Bảng 3.2 – Tổng quan về các kỹ thuật xử lý truy vấn trên Dòng dữ liệu..................... 27
Bảng 4.1 – Dữ liệu thống kê thu nhập (đã được bỏ định danh) ...................................... 40
Bảng 4.2 – Dữ liệu được làm mờ trên bộ quasi-identifier ................................................. 41
Bảng 5.1 – Mã giả của giải thuật lấy mẫu................................................................................... 55
Bảng 5.2 – Mã giả của thủ tục ADD() trong giải thuật làm mờ ........................................ 59
Bảng 5.3 – Mã giả của thủ tục REMOVE() trong giải thuật làm mờ ............................... 60
Bảng 6.1 – Bảng tổng kết về kết quả chạy hai giải thuật .................................................... 70

viii



Bảo vệ tính riêng tư trong xử lý câu truy vấn trên dịng dữ liệu

DANH MỤC HÌNH ẢNH
Hình 2.1 – Một kế hoạch truy vấn trên hệ thống Aurora ................................................... 10
Hình 2.2 – Ứng dụng quản lý hệ thống mạng .......................................................................... 13
Hình 3.1 – Ví dụ minh họa cho phương pháp Data Dropping .......................................... 18
Hình 3.2 – Kiến trúc tổng quan của hệ thống .......................................................................... 28
Hình 4.1 – CIA triad ............................................................................................................................. 31
Hình 4.2 – Nguy hiểm từ việc rị rỉ thơng tin cá nhân .......................................................... 34
Hình 4.3 – Bạn có biết ai đang theo dõi mình khơng?.......................................................... 35
Hình 4.4 – Các sân bay quốc tế với vài trăm ngàn lượt khách mỗi ngày ..................... 37
Hình 4.5 – Ví dụ về “Cây phân cấp tổng quát hóa miền dữ liệu” (DGH Tree) ........... 41
Hình 5.1 – Kiến trúc tổng quan cho giải pháp đề xuất......................................................... 53
Hình 5.2 – Ví dụ về “Cây phân cấp đặc trưng hóa dữ liệu” (SP Tree) .......................... 57
Hình 6.1 – Màn hình Console khi bắt đầu chạy giải thuật SKY ........................................ 67
Hình 6.2 – Màn hình Console khi kết thúc chạy giải thuật SKY ....................................... 67
Hình 6.3 – Màn hình Console khi bắt đầu chạy giải thuật sử dụng Synopses ........... 68
Hình 6.4 – Màn hình Console khi kết thúc chạy giải thuật sử dụng Synopses .......... 68
Hình 6.5 – Kết quả xử lý truy vấn tại các thời điểm ............................................................. 69
Hình 6.6 – Lần chạy thứ nhất .......................................................................................................... 71
Hình 6.7 – Lần chạy thứ hai ............................................................................................................. 72
Hình 6.8 – Lần chạy thứ ba .............................................................................................................. 73

ix


Bảo vệ tính riêng tư trong xử lý câu truy vấn trên dòng dữ liệu

DANH MỤC CHỮ VIẾT TẮT

DGH

Domain Generalization Hierachies
(Cây phân cấp tổng quát hóa miền dữ liệu)

DBMS

Database Management Systems
(Hệ Quản Trị Cơ Sở Dữ Liệu Truyền Thống)

DSMS

Data Stream Management Systems
(Hệ Quản Trị Dòng Dữ Liệu)

SP

Specialization Tree
(Cây phân cấp đặc trưng hóa dữ liệu)

x


Bảo vệ tính riêng tư trong xử lý câu truy vấn trên dòng dữ liệu

CHƯƠNG 1

GIỚI THIỆU
1.1. Giới thiệu đề tài
Những năm gần đây, một lớp ứng dụng mới đã xuất hiện với nhiều thách thức về

chức năng quản lý dữ liệu được đặt ra. Đó là các ứng dụng của Dịng dữ liệu. Một
vài ví dụ điển hình như hệ thống Tradebot dùng trong lĩnh vực tài chính, hệ thống
Hancock của AT&T theo dõi các mẫu cuộc gọi (calling patterns) của khoảng 100
triệu người gọi và đưa ra những cảnh báo gian lận theo thời gian thực.
Dòng dữ liệu là một chuỗi các đối tượng dữ liệu tuần tự, liên tục, khơng có giới hạn
và có tính chất thời gian thực. Những ứng dụng dữ liệu dạng chuỗi này ngày càng
phổ biến vì nhiều lý do khác nhau, cả về mặt kỹ thuật và thương mại. Sự phát triển
như vũ bão của khoa học công nghệ đã dẫn đến việc những thiết bị cảm ứng tinh vi
được sản xuất với chất lượng cao và giá thành thấp, kéo theo sự phát triển của
những hệ thống sử dụng thiết bị cảm ứng nói riêng và các hệ thống quản lý nói
chung. Dữ liệu trong những hệ thống này được thu thập một cách tự động, thành
dịng liên tục, vơ hạn và cần được xử lý trong thời gian thực để cung cấp thông tin
cho hệ thống đưa ra quyết định phản ứng kịp thời với các tình huống thực tế. Ví dụ
như hệ thống phát hiện gian lận trong giao dịch của các thẻ tín dụng giúp ngân
hàng ngăn chặn các cuộc tấn công ngay thời điểm mà những giao dịch bất thường
đó xảy ra. Hoặc mạng các thiết bị cảm ứng thu nhận các tín hiệu thời tiết, mơi
trường và xử lý tự động các thông số thu được để đưa ra những dự báo thời tiết và
thiên tai một cách kịp thời. Nói chung, các hệ thống Dịng dữ liệu được ứng dụng

1


Bảo vệ tính riêng tư trong xử lý câu truy vấn trên dòng dữ liệu
đa dạng trong rất nhiều lĩnh vực quan trọng: quân sự, tài chính, quản lý bảo mật,
mạng cảm ứng, hệ thống mạng, thương mại điện tử, v.v.
Tuy nhiên, những hệ thống quản trị cơ sở dữ liệu hiện tại được xây dựng với mục
đích ban đầu là hỗ trợ cho các ứng dụng dữ liệu tĩnh. Dữ liệu trong những ứng
dụng loại này được thay đổi hoặc truy vấn bởi các thao tác do người dùng kích
hoạt. Nói cách khác, các hệ thống quản trị cơ sở dữ liệu hiện tại chỉ làm nhiệm vụ
của một nơi lưu trữ dữ liệu tĩnh một cách thụ động nên không thể đáp ứng được

các yêu cầu đặc biệt của ứng dụng dịng dữ liệu, đó là: phản ứng chủ động trong
thời gian thực dựa trên thông tin được thu thập và phân tích từ các dịng dữ liệu
khổng lồ, tốc độ cao. Để đáp ứng được các thách thức của lớp ứng dụng mới, nhiều
cơng trình nghiên cứu đã và đang được thực hiện ngày càng nhiều trên thế giới.
Đây là một hướng nghiên cứu trọng tâm ngày càng được quan tâm nhiều hơn
trong lĩnh vực khoa học máy tính.
Cũng như bao vấn đề khác, các ứng dụng bao giờ cũng phải đi kèm những yêu cầu
bảo mật mà bảo vệ tính riêng tư là một phần quan trọng không thể thiếu. Những
thông tin cá nhân nhạy cảm của khách hàng hoặc của các đối tượng bị theo dõi bởi
hệ thống thu thập thông tin trong các ứng dụng dòng dữ liệu cần phải được bảo vệ
để tránh bị rò rỉ và bị sử dụng cho các mục đích xấu ảnh hưởng đến đời sống riêng
tư và sự an tồn của họ.
Trong số các bài tốn cần được nghiên cứu của ứng dụng dòng dữ liệu, đề tài của
chúng tôi đi vào hướng nghiên cứu một giải pháp cho việc xử lý câu truy vấn trên
dòng dữ liệu nhưng vẫn bảo vệ được tính riêng tư cho dữ liệu cá nhân xuất hiện
trong dòng dữ liệu.

2


Bảo vệ tính riêng tư trong xử lý câu truy vấn trên dịng dữ liệu

1.2. Mục đích nghiên cứu
Hiện nay đã có một số bài báo, bài nghiên cứu xây dựng các giải thuật để bảo vệ
danh tính của khách hàng-người chủ sở hữu của thông tin chứa bên trong dữ liệu.
Tuy nhiên, những giải thuật này vẫn chưa hiệu quả lắm và chưa chú trọng vào vấn
đề xử lý câu truy vấn cũng như những đặc trưng của loại dịng dữ liệu mà trên đó
câu truy vấn sẽ được thực hiện, mà chỉ tập trung vào việc che giấu thông tin trước
khi dữ liệu được đưa đi xử lý. Vấn đề nghiên cứu này ở Việt Nam cũng còn rất mới
mẻ, hầu như chưa được quan tâm.

Luận văn này hướng tới việc nghiên cứu kết hợp kỹ thuật xử lý truy vấn trên loại
dòng dữ liệu với kỹ thuật che giấu, làm mờ dữ liệu, nhờ đó bảo vệ được tính riêng
tư cho khách hàng trong xử lý câu truy vấn trên dòng dữ liệu. Trong bối cảnh các
ứng dụng dòng dữ liệu ngày càng được áp dụng rộng rãi, ngay cả ở Việt Nam, đề
tài nghiên cứu này giúp đưa ra một phương pháp bảo vệ tính riêng tư cho người
dùng hệ thống, tạo niềm tin và thu hút người dân sử dụng các hệ thống này.

1.3. Ý nghĩa khoa học và thực tiễn của đề tài
Khoa học kỹ thuật ngày càng phát triển và chi phối hầu như tất cả các mặt của xã
hội hiện đại. Các hệ thống dịng dữ liệu là một phần khơng thể thiếu trong sự bùng
nổ đó. Đã có rất nhiều nghiên cứu về việc xử lý và sử dụng các dòng dữ liệu sao
cho hiệu quả cả về mặt nội dung thông tin cũng như tài nguyên của hệ thống. Rất
nhiều nghiên cứu khai thác các khía cạnh tính năng của lớp ứng dụng mới mẻ này.
Tuy nhiên, vấn đề bảo vệ thông tin riêng tư của các đối tượng trong hệ thống vẫn
còn là một hướng nghiên cứu mở, tương đối mới và chưa được quan tâm đúng
mức. Thiết nghĩ đây cũng là một vấn đề cấp thiết cần được đầu tư nghiên cứu
nhiều hơn để có thể phát triển song hành cùng chất lượng các dịch vụ trên dòng

3


Bảo vệ tính riêng tư trong xử lý câu truy vấn trên dịng dữ liệu
dữ liệu. Có như vậy mới bảo đảm được tính đúng đắn về mặt pháp lý trong việc sử
dụng thông tin cá nhân của các đối tượng hệ thống và đảm bảo được sự an toàn,
tạo tâm trạng yên tâm, tin tưởng cho khách hàng khi sử dụng các hệ thống này.
Kết quả nghiên cứu của đề tài có thể được áp dụng cho các hệ thống có sử dụng
dịng dữ liệu như: hệ thống phát hiện giao dịch bất thường cho các thẻ tín dụng, hệ
thống điều phối mạng điện thoại di động, các hệ thống mua bán/giao dịch trên
mạng,... Đồng thời đây cũng sẽ là một đóng góp cho sự phát triển của lĩnh vực bảo
vệ thông tin cá nhân (user privacy preserving).


4


Bảo vệ tính riêng tư trong xử lý câu truy vấn trên dịng dữ liệu

CHƯƠNG 2

TỔNG QUAN VỀ DỊNG DỮ LIỆU
2.1. Định nghĩa
Theo định nghĩa của Golab & Oszu (2003) [1]:
Dòng dữ liệu (Data Stream) là một chuỗi các phần tử dữ liệu có thứ tự (một
cách ngầm định bằng thời gian đến hoặc một cách tường minh theo nhãn thời
gian), liên tục và theo thời gian thực. Không thể điều khiển thứ tự đến của các
phần tử, cũng như khơng thể lưu trữ một cách cục bộ tồn bộ chuỗi phần tử
đó.

2.2. Cấu trúc
Một dịng dữ liệu là một chuỗi bất định (tức là không thể biết trước được khi nào
dòng dữ liệu sẽ kết thúc) bao gồm nhiều phần tử. Tất cả các phần tử trong chuỗi
đều có cùng một cấu trúc. Mỗi phần tử sẽ ở dạng thơng tin có cấu trúc, ví dụ một
hàng dữ liệu bảng hoặc một đối tượng. Bên cạnh đó, mỗi phần tử cũng chứa một
nhãn định thời (timestamp) để xác định thứ tự của chúng. Chúng ta có thể xác
định thứ tự các phần tử một cách tường minh hoặc ngầm định. Theo cách tường
minh, bản thân mỗi phần tử sẽ có thuộc tính chứa thơng tin thời gian được sử
dụng làm nhãn định thời. Ngược lại, thời điểm đến của các phần tử sẽ được sử
dụng làm nhãn định thời. Việc biểu diễn các nhãn định thời có thể theo hình thức
biểu diễn thời gian cụ thể hoặc được đại diện bởi một số nguyên tương ứng.

5



Bảo vệ tính riêng tư trong xử lý câu truy vấn trên dịng dữ liệu
Bảng 2.1 là một ví dụ minh họa cho dòng dữ liệu. Dòng dữ liệu trong bảng này ghi
nhận các thông số của một hệ thống điện theo từng phút. Nhãn định thời của các
phần tử trong ví dụ này được biểu diễn bởi các mốc thời gian cụ thể.
Bảng 2.1 – Dòng dữ liệu ghi nhận thông số của một hệ thống điện
Nhãn định thời

Puis. A (kW)

Puis. R (kVAR)

U 1 (V)

I 1 (A)

…

…

…

…

…

16/12/2006-17:26

5,374


0,498

233,29

23

16/12/2006-17:27

5,388

0,502

233,74

23

16/12/2006-17:28

3,666

0,528

235,68

15,8

16/12/2006-17:29

3,52


0,522

235,02

15

…

…

…

…

…

Bảng 2.2 là một ví dụ khác của dịng dữ liệu. Dịng dữ liệu trong bảng này là thông
tin được ghi nhận tại một router trong một hệ thống mạng. Nhãn định thời của
dòng được biểu diễn bởi các số nguyên dương.
Bảng 2.2 – Dịng dữ liệu ghi nhận thơng tin của một router
Nhãn định thời

IP Nguồn

IP Đích

Thời lượng

Bytes


Giao thức

…

…

…

…

…

…

12342

10.1.0.2

16.2.3.7

12

20K

http

12343

18.6.7.1


12.4.0.3

16

24K

http

12344

12.4.3.8

14.8.7.4

26

58K

http

12345

19.7.1.2

16.5.5.8

18

80K


ftp

…

…

…

…

6

…

…


Bảo vệ tính riêng tư trong xử lý câu truy vấn trên dịng dữ liệu

2.3. Đặc tính
Một dịng dữ liệu có các đặc tính cơ bản sau:
 Liên tục (Continuous): Các phần tử dữ liệu xuất phát từ các hệ thống thu thập
thông tin, ghi nhận sự kiện, mạng cảm biến,… và được chuyển đến hệ thống xử
lý một cách liên tục với tốc độ cao, có thể lên đến vài triệu phần tử mỗi giây.
 Khơng có giới hạn (Unbounded): Dòng dữ liệu được gửi tới bộ phận xử lý liên
tục khơng ngừng, khơng có giới hạn về thời gian, khơng biết trước khi nào việc
gửi dữ liệu hồn tất.
 Thay đổi theo thời gian (Time-varying): Bởi vì dịng dữ liệu đến liên tục, khơng
có giới hạn nên dữ liệu dùng để trả lời câu truy vấn thay đổi liên tục theo thời

gian, dẫn đến kết quả cho các câu truy vấn cũng thay đổi liên tục theo thời gian.
Đặc biệt, bản chất thống kê của dòng dữ liệu cũng có thể thay đổi theo thời gian
để thể hiện xu hướng thay đổi của dịng thơng tin.
 Thời gian thực (Real-time): Đa phần các hệ thống dòng dữ liệu được dùng cho
các ứng dụng thu thập thông tin xảy ra thực tế, ghi nhận và đánh giá thơng tin
đó theo một số tiêu chí định sẵn và có những phản ứng thích hợp cho từng sự
kiện xảy ra. Do đây là các hệ thống thời gian thực, nên các phản ứng cũng phải
xảy ra theo thời gian thực để đáp ứng được các sự kiện.
 Cần bản kế hoạch những câu truy vấn (Require persistent long-running queries):
Không giống với các hệ cơ sở dữ liệu truyền thống, trong các hệ thống dữ liệu
theo dòng, việc truy vấn trong đa số các trường hợp là hồn tồn tự động. Do
đó các bản kế hoạch truy vấn (query plan) cần được xây dựng trước để hệ
thống thực hiện liên tục và lặp lại một cách tự động mỗi khi dữ liệu đến (tức dữ
liệu được cập nhật).

7


Bảo vệ tính riêng tư trong xử lý câu truy vấn trên dịng dữ liệu

2.4. Phân loại
Chúng ta có thể phân loại ứng dụng dòng dữ liệu thành 2 dạng chính, dịng dữ liệu
giao dịch và dịng dữ liệu đo lường [2].
 Dòng dữ liệu giao dịch (Transactional Data Streams): là những dữ liệu ghi nhận
lại các tương tác giữa các thực thể (thơng tin nhật ký).
Ví dụ: Dịng dữ liệu chứa thông tin các giao dịch mua hàng của các khách
hàng sử dụng thẻ tín dụng được ghi nhận và xử lý để phát hiện kịp thời các
giao dịch gian lận ngay tại thời điểm mà chúng đang diễn ra.
 Dòng dữ liệu đo lường (Measurement Data Streams): được sinh ra như là kết
quả của việc quản lý trạng thái của các thực thể mà hệ thống quan tâm.

Ví dụ: Dòng dữ liệu thu được từ hệ thống cảm biến tại các trạm quan trắc
thời tiết được dùng cho các ứng dụng dự báo thời tiết, thiên tai.

2.5. Ngôn ngữ truy vấn trên dịng dữ liệu
Có 3 mơ hình truy vấn cho dòng dữ liệu đã được đề xuất [1]:
 Mơ hình dựa trên quan hệ (Relation-based): mỗi ngơn ngữ của mơ hình này có
một cú pháp tựa SQL, có hỗ trợ cho “cửa sổ” (windows)1 và sắp xếp theo thứ tự.
 CQL
 StreaQuel
 AQuery
 Mơ hình dựa trên đối tượng (Object-based):
 Tribeca
 COUGAR
 Mơ hình thủ tục (Procedural):
 Aurora
1

Được sử dụng trong kỹ thuật xử lý câu truy vấn Windowing. Xem thêm tại mục 3.2.3.

8


Bảo vệ tính riêng tư trong xử lý câu truy vấn trên dòng dữ liệu

2.6. Hệ quản trị dòng dữ liệu
Do các đặc tính riêng biệt của dịng dữ liệu, hệ quản trị cơ sở dữ liệu truyền thống
(Database Management Systems - DBMS) cũng như các giải thuật và phương pháp
xử lý của nó khơng đáp ứng được các u cầu của các ứng dụng dòng dữ liệu. Bảng
2.3 liệt kê các điểm khác biệt về yêu cầu căn bản giữa hệ quản trị dòng dữ liệu
(Data Stream Management Systems - DSMS) với hệ quản trị cơ sở dữ liệu truyền

thống.
Bảng 2.3 – So sánh DSMS và DBMS
DSMS

DBMS

Dòng dữ liệu dễ thay đổi.

Các quan hệ cố định.

Các câu truy vấn được thực hiện liên Các câu truy vấn được thực hiện theo
tục.
từng lần.
Truy xuất tuần tự.

Truy xuất ngẫu nhiên.

Bộ nhớ chính giới hạn so với lượng dữ
liệu.
Thứ tự đến, lịch sử của dữ liệu có vai
trị quan trọng.
Lưu trữ chủ động (có phản ứng theo
điều kiện).
Tốc độ đến của dữ liệu có thể lên đến
hàng GB.

Nơi lưu trữ “khơng giới hạn”2 so với
lượng dữ liệu.

u cầu thời gian thực.


Khơng có dịch vụ thời gian thực.

Chỉ quan tâm đến trạng thái hiện tại.
Lưu trữ bị động.
Tốc độ cập nhật tương đối thấp.

Phải nhận biết dữ liệu giả, khơng chính
Giả sử là tồn bộ dữ liệu đều chính xác.
xác.
Danh sách bên dưới thống kê một số DSMS tiêu biểu hiện nay [3]:

“Không giới hạn” ở đây có ý nghĩa tương đối, ý nói nhu cầu về nơi lưu trữ dữ liệu đối với hệ thống quản trị
cơ sở dữ liệu truyền thống hầu như luôn được đáp ứng đầy đủ.
2

9


Bảo vệ tính riêng tư trong xử lý câu truy vấn trên dòng dữ liệu
 Aurora (Đại học Brandeis, Brown, MIT): là hệ thống xây dựng theo hướng dòng
chảy dữ liệu với một tập các toán tử được sử dụng thông qua giao diện đồ họa
người dùng. Người dùng đặc tả các câu truy vấn bằng cách sắp xếp các khối
vng (đại diện cho các tốn tử) và các mũi tên (đại diện cho dịng chảy dữ liệu
giữa các tốn tử). Nói cách khác, người dùng đang đặc tả các kế hoạch truy vấn
(query plans) cho hệ thống. Hình 2.1 minh họa một kế hoạch truy vấn trên
Aurora. Hệ thống Aurora tối ưu hóa dịng chảy của dữ liệu trong hệ thống bằng
cách sắp xếp lịch cho các toán tử theo thời gian thực.

Hình 2.1 – Một kế hoạch truy vấn trên hệ thống Aurora

 COUGAR (Đại học Cornell, Northeastern): Hệ thống này được phát triển để
quản lý dữ liệu cảm biến (sensor data). Thay vì các hàng dữ liệu thơng thường,
dữ liệu trong hệ thống này được mơ hình thông qua các kiểu dữ liệu trừu
tượng (Abstract data types). Việc đặc tả và thực thi các câu truy vấn tận dụng
các hàm được định nghĩa trên các kiểu dữ liệu trừu tượng.
 Gigascope (AT&T): là một hệ thống dòng dữ liệu chuyên dụng cho các ứng dụng
hệ thống mạng. Hệ thống cung cấp một ngôn ngữ truy vấn khai báo được gọi là
GSQL.
 Hancock (AT&T): hệ thống cung cấp một ngôn ngữ thủ tục dựa trên C cho việc
truy vấn trên các dòng dữ liệu giao dịch. Ứng dụng mục tiêu của hệ thống là
10


Bảo vệ tính riêng tư trong xử lý câu truy vấn trên dòng dữ liệu
theo dõi các mẫu cuộc gọi (calling patterns) của khoảng 100 triệu người gọi và
đưa ra những cảnh báo gian lận theo thời gian thực.
 NiagaraCQ (Đại học Wisconsin-Madison): là một hệ thống dành cho việc xử lý
câu truy vấn liên tục trên các tập dữ liệu động trên mạng. Mơ hình dữ liệu và
ngơn ngữ truy vấn của hệ thống dựa trên XML và XML-QL thay vì các quan hệ
và SQL.
 StatStream: hệ thống hướng tới việc tính tốn trực tuyến các thống kê trên các
dịng dữ liệu. Hệ thống có khả năng tính tốn thống kê trên các dòng dữ liệu
đơn, cũng như trên các mối tương quan giữa các dòng dữ liệu.
 STREAM (Đại học Stanford): đây là hệ thống quản lý dòng dữ liệu với ngôn ngữ
truy vấn khai báo tựa SQL được gọi là CQL. Hệ thống quản lý một cách thơng
minh các nguồn tài ngun và có khả năng xấp xỉ động các kết quả dựa trên tải
và nguồn tài nguyên sẵn có.
 TelegraphCQ (Đại học Berkeley): là hệ thống để xử lý liên tục các câu truy vấn
trên dòng dữ liệu. Hệ thống có các kỹ thuật tối ưu hóa câu truy vấn có khả năng
thích ứng cao để sử dụng cho việc đánh giá các câu truy vấn phức hợp trên các

dịng dữ liệu.
Ngồi các DSMS nêu trên cịn một số DSMS khác như: Tradebot (dùng cho tài
chính), Streambase, Aminsight, Aleri, TinyDB, Cayuga, Sase.

2.7. Lĩnh vực ứng dụng
Hệ thống xử lý dòng dữ liệu được ứng dụng trong nhiều lĩnh vực như quân sự, hệ
thống bảo vệ nhà riêng tự động (homeland security), mạng cảm biến, ghi nhận các
cuộc gọi điện thoại, các hệ thống tài chính, quản lý mạng, kỹ thuật giao thông, theo
dõi hoạt động website, phát hiện gian lận thẻ tín dụng thời gian thực.

11


Bảo vệ tính riêng tư trong xử lý câu truy vấn trên dịng dữ liệu

2.8. Các bài tốn của dịng dữ liệu
Do có nhiều điểm khác biệt về bản chất giữa dữ liệu truyền thống và dòng dữ liệu,
rất nhiều bài toán cần được nghiên cứu và giải quyết. Danh sách dưới đây liệt kê
những vấn đề chính của lĩnh vực nghiên cứu này [4]:
 Gom cụm trên dòng dữ liệu (Data stream clustering).
 Phân lớp trên dòng dữ liệu (Data stream classification).
 Khai phá các mẫu thường xuyên (Frequent pattern mining).
 Phát hiện những thay đổi trong các dòng dữ liệu (Change detection in data
streams).
 Phân tích khối dịng dữ liệu đa chiều (Stream cube analysis of multi-dimensional
streams).
 Cắt giảm tải trên dòng dữ liệu (Loadshedding in data streams).
 Tính tốn cửa sổ trượt cho dịng dữ liệu (Sliding window computation in data
streams).
 Xây dựng cấu trúc tóm lược cho dòng dữ liệu (Synopsis construction in data

streams).
 Xử lý phép kết trên dòng dữ liệu (Join processing in data streams).
 Đánh chỉ mục trên dòng dữ liệu (Indexing data streams).
 Dự đốn trên dịng dữ liệu (Forecasting in data streams).
 Khai phá dữ liệu phân bố trên dòng dữ liệu (Distributed mining of data
streams).
 Khai phá dòng dữ liệu trong các mạng cảm biến (Stream mining in sensor
networks).

12