Nhận dạng Key Player trên Twitter
ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CƠ SỞ DỮ LIỆU
NÂNG CAO
Nhận Dạng Key Player
trên Mạng Xã Hội Twitter
Giáng viên hướng dẫn
PGS.TS. Đỗ Phúc
Học viên: Huỳnh Lê Quốc Vương MHV: CH1101158
08 – 2012
ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CƠ SỞ DỮ LIỆU
NÂNG CAO
Nhận Dạng Key Player
trên Mạng Xã Hội Twitter
Giáng viên hướng dẫn
PGS.TS. Đỗ Phúc
Học viên: Huỳnh Lê Quốc Vương MHV: CH1101158
08 – 2012
Nhận dạng Key Player trên Twitter
MỤC LỤC
GIỚI THIỆU
Hiện nay, mạng xã hội là một đề tài hết sức được quan tâm. Thông qua
mạng xã hội với hàng triệu người sử dụng thì các tin tức sự kiện được lan
truyền đi rất nhanh. Tất nhiên giới kinh doanh không thể nào bỏ qua cơ hội
này, đặc biệt là việc marketing trên mạng xã hội. Các công ty lớn như Dell,
Starbucks hay Comcast đã tận dụng rất tốt Twitter để quảng bá sản phẩm và
giải đáp thắc mắc khách hàng. Nhưng hiện nay, trên các dịch vụ tiểu blog miễn
phí, có thể thấy rằng số lượng các doạnh nghiệp nhỏ đã vượt trội so với các

- Tagging – nhóm các dữ liệu liên quan lại với nhau
- RDF (Resource Description Framework) – mô tả dữ liệu được kết nối
như thế nào)
- GGG (Giant Global Graph) – nội dung + các liên kết + các mối quan hệ
+ mô tả
- …
Xu hướng kết nối dữ liệu
Dữ liệu trở nên bán cấu trúc (dữ liệu không được mô tả riêng biệt thành về
kiểu và cấu trúc – không có lược đồ)
- Nếu bạn muốn thu thập tất cả dữ liệu cho mỗi bộ phim được sản xuất từ
trước đến giờ, bạn sẽ phải mô hình nó như thế nào?
- Có quá nhiều thứ để bạn phải suy nghĩ như đạo diễn, nhân vật, địa điểm,
ngày, chi phí, đánh giá, trình chiếu, giá vé, …
Nhận dạng Key Player trên Twitter
Hình trên cho thấy performance của cơ sở dữ liệu quan hệ giảm đáng kể khi
độ phức tạp dữ liệu (kết nối dữ liệu) ngày càng tăng.
Vì thế đã có sự ra đời của NO SQL. Ban đầu NO SQL có nghĩa là Non-
Relational (NoRel) - không ràng buộc. Nhưng sau này người ta thường dịch
NO SQL thành Not Only SQL, ám chỉ đến những cơ sở dữ liệu không dùng mô
hình dữ liệu quan hệ để quản lý dữ liệu trong lĩnh vực phần mềm.
Với NO SQL là một thế hệ cơ sở dữ liệu non-relational (không ràng buộc),
distributed (phân tán), open source, horizontal scalable (khả năng mở rộng theo
chiều ngang) có thể lưu trữ, xử lý từ một lượng rất nhỏ cho tới hàng petabytes
dữ liệu trong hệ thống có độ chịu tải, lỗi cao với những đòi hỏi về tài nguyên
phần cứng thấp.
Một số đặc điểm nhận dạng cho thế hệ database mới này bao gồm: schema-
free, hỗ trợ mở rộng dễ dàng, API đơn giản, eventual consistency (nhất quán
cuối) và/hoặc transactions hạn chế trên các thành phần dữ liệu đơn lẻ, không
giới hạn không gian dữ liệu,
Hiện nay có 4 loại cơ sở dữ liệu NO SQL như sau:

sản phẩm thông dụng: Hadoop/HBase – Apache, BigTable – Google,
Cassandra - Facebook/Apache, Hypertable - Zvents Inc/Baidu, Cloudera,
SciDB, Mnesia, Tablets,…
• Điểm mạnh:
o Hỗ trợ dữ liệu nửa cấu trúc
o Đánh chỉ mục tự động theo cột
o Khả năng mở rộng cao
• Điểm yếu:
o Khó khăn trong interconnected data
2.3. Document Store
Thực chất là các document-oriented database - một thiết kế riêng biệt cho
việc lưu trữ document. Các cài đặt có thể là giả lập tương tác trên relational
database, object database hay key-value store. Một số sản phẩm tiêu biểu:
Apache Jackrabbit, CouchDB, IBM Lotus Notes Storage Format (NSF),
MongoDB, Terrastore, ThruDB, OrientDB, RavenDB,
• Điểm mạnh:
o Đơn giản, mô hình dữ liệu mạnh mẽ
o Khả năng mở rộng cao
• Điểm yếu:
o Khó khăn trong interconnected data
o Mô hình truy vấn bị giới hạn các khóa và chỉ mục
o Thiếu map reduct cho các truy vấn lớn
2.4. Graph Database
Graph database là một dạng cơ sở dữ liệu được thiết kế riêng cho việc lưu
trữ thông tin trong đồ thị như cạnh, nút, thuộc tính. Một số sản phẩm tiêu biểu:
Neo4J, Sones, AllegroGraph, Core Data, DEX, FlockDB, InfoGrid, OpenLink
Virtuoso,
• Điểm mạnh:
o mô hình dữ liệu đầy sức mạnh
o Truy vấn nhanh cho các dữ liệu có kết nối

do đó có thể dễ dàng biểu diễn trong cây. Với graph database, thì các mối quan
hệ giữa các document dễ dàng được duyệt hơn. Như hình sau:
D=Document, S=Subdocument, V=Value, D2/S2 = tham chiếu tới
subdocument trong document khác
Nhận dạng Key Player trên Twitter
Graph database từ Document Store
Ta đã thấy được ưu điểm của graph database trong dữ liệu phức tạp có kết
nối, xem phần sau để tìm hiểu kỹ hơn về graph database và neo4j, một hiện
thực của graph database mà ta sẽ sử dụng cho chương trình.
II. Khái quát graph database và Neo4j
1. Graph database
1.1. Nút và mối quan hệ
Một graph lưu trữ record trong các nút (đỉnh) và các nút có các thuộc tính.
Một graph đơn giản nhất là một nút đơn lẻ, một record mà có các giá trị
(được đặt tên) thì được xem như là các thuộc tính. Một nút có thể bắt đầu với
một thuộc tính và phát triển dần thành vài triệu thuộc tính. Tuy nhiên, vài triệu
thuộc tính có thể bất tiện, do đó, nó có thể được phân tán thành nhiều nút, với
các mối quan hệ (cạnh) với nhau.
Các nút được tổ chức bởi các mối quan hệ, các mối quan hệ này cũng có
các thuộc tính.
Các mối quan hệ tổ chức các nút thành các cấu trúc bất kỳ, cho phép một
graph giống như một List, một Tree, một Map, một Entity hỗn hợp nào đó –
bất kỳ cái nào có thể kết hợp thành phức tạp hơn, đa dạng về cấu trúc liên kết.
Sự tương quan giữa độ phức tạp của dữ liệu
và kích thước trong các loại NO SQL
Ta có thể hình dung một graph database như thế này
Nhận dạng Key Player trên Twitter
Tổng quan một graph database
1.2. Truy vấn đồ thị
Một truy vấn đồ thị được thực hiện với một traversal. Một Traversal điều

Các mối quan hệ giữa các nút là một phần quan trọng của một cơ sở dữ liệu
đồ thị.
Chúng cho phép tìm dữ liệu có liên quan nhau. Cũng giống như nút, các
mối quan hệ có thể có các thuộc tính
Tổ chức của một mối quan hệ
Một mối quan hệ kết nối giữa hai nút, một nút bắt đầu và một nút kết thúc.
Một mối quan hệ luôn luôn có hướng, chúng có thể được xem như là một
mối quan hệ “đi” hoặc “đến” tới một nút, được sử dụng để duyệt đồ thị:
Trong Neo4j hướng của mối quan hệ có thể được lờ đi nếu nó không hữu
ích trong ứng dụng.
Một nút có thể có mối quan hệ với chính bản thân nó
Nhận dạng Key Player trên Twitter
Để nâng cao việc duyệt đồ thị, các mối quan hệ đều có kiểu hay gọi cách
khác là được gán nhãn. Ví dụ dưới đây là một mạng xã hội đơn giản với hai
kiểu mối quan hệ.
Để tìm một người theo sau thì duyệt theo mối quan hệ có kiểu “follows”,
còn nếu tìm một người chặn một người khác thì duyệt theo mối quan hệ có
kiểu “blocks”
2.3. Thuộc tính
Cả nút và mối quan hệ đều có thể có thuộc tính.
Các thuộc tính là các cặp key-value với key là kiểu string. Các giá trị thuộc
tính có thể là kiểu cơ bản (integer, long, float, …) hay một mảng của một kiểu
cơ bản. Ví dụ String, int và int[] là các giá trị hợp lệ cho thuộc tính.
2.4. Đường đi
Một đường đi là một hay nhiều nút với các mối quan hệ kết nối, thường
được truy hồi như là một kết quả truy vấn hay duyệt đồ thị.
Nhận dạng Key Player trên Twitter
Đường đi ngắn nhất có chiều dài là 0 giống như sau:
Một đường đi có chiều dài là 1
2.5. Duyệt