Cơ sở dữ liệu nâng cao
MỤC LỤC
GVHD : PGS.TS Đỗ Phúc Trang 1
HVTH : Mã Tuấn Huy
Cơ sở dữ liệu nâng cao
LỜI MỞ ĐẦU

Ngày nay các hệ thống lưu trữ ảnh vân tay thô xuống database trong các công ty
ngày càng phát triển, mỗi khi khách hàng hoặc nhân viên đăng nhập (không cần gõ
username + pass world mà chỉ cần sử dụng vân tay) hệ thống sẽ tải từng file ảnh
lên rồi dùng thuật toán so khớp. Tuy nhiên khi dữ liệu quá lớn thì việc này là bất
khả thi về thời gian chờ cũng như dung lượng đường truyền. Việc xử lý đòi hỏi phải
linh hoạt và không làm gián đoạn ứng dụng.Với hệ thống lưu trữ hiện tại không thể
linh động với đòi hỏi này.
Người sử dụng muốn có một cầu nối, một biện pháp để giải quyết những vấn đề
trên do đó dữ liệu đồ thị ra đời. Cơ sở dữ liệu đồ thị là cách thức lưu trữ thông tin
ở dạng đồ thị những đỉnh (Node) và cạnh (Edge).Với cách thức lưu trữ này, việc
quản lý dữ liệu trở nên mềm dẽo và dễ dàng hơn ngay cả trong việc ứng dụng tri
thức vào khối dữ liệu lưu trữ.
Tiểu luận này là sự khởi đầu cho việc thực hiện bài luận tốt nghiệp cuối khóa, do
thời gian có hạn nên em chỉ trình bày khái quát về cơ sở dữ liệu đồ thị, đồng thời
ứng dụng trong việc lưu trữ dữ liệu đồ thị (được biểu diễn bằng ma trận) xuống
“Cơ sở dữ liệu”.
Em xin chân thành cảm ơn PGS.TS. Đỗ Phúc – Giảng viên phụ trách giảng dạy
chuyên đề “cơ sở dữ liệu nâng cao” đã truyền đạt những kiến thức cùng kinh
nghiệm vô cùng quý báu đồng thời gợi ý về việc thực hiện đề tài này, xin chân
thành cám ơn ban cố vấn học tập và ban quản trị chương trình đào tạo”Thạc sĩ
Khoa học máy tính” của Đại Học Quốc Gia TPHCM đã tạo điều kiện về tài liệu
tham khảo để em có thể hoàn thành môn học này.
GVHD : PGS.TS Đỗ Phúc Trang 2
HVTH : Mã Tuấn Huy

đầu/gốc và y được gọi là điểm cuối/ngọn của cạnh.
• Cấu trúc đồ thị có thể mở rộng bằng cách gán trọng số cho các cạnh của đồ thị. Có
thể sử dụng đồ thị có trọng số để ứng dụng trong thực tế như chiều dài con đường
(tìm đường đi ngắn nhất giữa 2 điểm), thời gian đi giữa hai nút, độ mạnh liên kết
giữa các nút, số giao tác kết nối giữa 2 nút cùng thời điểm.
Tham khảo và trích dẫn từ />%C4%90%E1%BB%93_th%E1%BB%8B_%28l%C3%BD_thuy
%E1%BA%BFt_%C4%91%E1%BB%93_th%E1%BB%8B
%29#.C4.90.E1.BB.93_th.E1.BB.8B_v.C3.B4_h.C6.B0.E1.BB.9Bn
g
GVHD : PGS.TS Đỗ Phúc Trang 4
HVTH : Mã Tuấn Huy
Cơ sở dữ liệu nâng cao
2. Cơ sở dữ liệu đồ thị
a. Giới thiệu :
Cơ sở dữ liệu đồ thị là tập các đồ thị.Một cơ sở dữ liệu đồ thị có thể có nhiều
đồ thị nhưng cũng có thể chỉ có một đồ thị, đó là một đồ thị rất lớn chứa nhiều
nút và đỉnh ví dụ như mạng xã hội
b. Cách lưu trữ dữ liệu đồ thị :
 Lưu trữ bằng RDBMS
Dữ liệu được lưu trữ thành những dòng và cột trong những table khác
nhau. Dữ liệu được truy xuất bằng câu lệnh SQL.SQL cho phép người sử
dụng truy xuất khá mạnh mẽ dữ liệu đồ thị bao gồm cả việc trích xuất dữ liệu
mới từ dữ liệu đã lưu trữ .
Mặc dù có nhiều điểm mạnh nhưng SQL không thể hổ trợ những thao tác
tính toán, những biểu thức phức tạp một cách linh hoạt và tùy lúc.Ví dụ như
tính chi phí một con đường đi từ đỉnh này để đỉnh khác, tìm chi phí thấp nhất
để đi giữa hai nút cho trước…
 Lưu trữ bằng SBGE
Để giải quyết vấn đề trên DB2 và RDBMS đã mở rộng SQL bằng cách
xây dựng nhưng hàm cụ thể được gọi là user-defined functions (UDFs).

khổng lồ.
Hình 2.1.1.1: Hình ảnh về các dấu vân tay (Finger print)
Trong bài tiểu luận này, em sẽ trình bày quá trình lưu 1 đồ thị (đã mã hóa
thành ma trận) vào cơ sở dữ liệu. Vấn đề về mã hóa hình ảnh vân tay thành đồ
thị và tìm kiếm dấu vân tay trong cơ sở dữ liệu đồ thị em sẽ cố gắng nghiên cứu
và hoàn chỉnh đề tài này để trình bày trong bài luận cuối khóa.
GVHD : PGS.TS Đỗ Phúc Trang 7
HVTH : Mã Tuấn Huy
Cơ sở dữ liệu nâng cao
2. Giải quyết bài toán
Trong báo cáo này, em sử dụng C# (Visual 2005) giao diện Form để người dùng
nhập đồ thị được biểu diễn dạng ma trận vào cơ sở dữ liệu. Cơ sỡ dữ liệu sử dụng là
SQL Server 2005.
Hình 2.2.1: Mô hình dữ liệu đồ thị
Table “Graph”
Tên thuộc tính Kiểu Mô tả
graphID Int ID của Graph, là duy nhất không được trùng với
các id khác.
graphNAME Varchar Tên của Graph
graphDescription Text Mô tả
Table “Node”
GVHD : PGS.TS Đỗ Phúc Trang 8
HVTH : Mã Tuấn Huy
Cơ sở dữ liệu nâng cao
Tên thuộc tính Kiểu Mô tả
nodeID Int ID của Node (đỉnh), là duy nhất không được
trùng với các id khác.
nodeNAME Varchar Tên của Node
graphID Int Khóa ngoại, Link tới table “Graph”
nodeLevel Int Bậc của Node (chỉ xét đồ thị vô hướng).

SQL_Latin1_General_CP1_CI_AS NULL,
CONSTRAINT [PK_graph] PRIMARY KEY CLUSTERED
(
[graphID] ASC
)WITH (PAD_INDEX = OFF, IGNORE_DUP_KEY = OFF) ON
[PRIMARY]
) ON [PRIMARY]
Cơ sở dữ liệu nâng cao
• Create Table “Node” trong SQL Server
• Create Table “Edge” trong SQL Server
Giao diện Form sử dụng
GVHD : PGS.TS Đỗ Phúc Trang 11
HVTH : Mã Tuấn Huy
CREATE TABLE [dbo].[node](
[nodeID] [int] NOT NULL,
[nodeName] [nvarchar](50) COLLATE
SQL_Latin1_General_CP1_CI_AS NOT NULL,
[graphID] [int] NOT NULL,
[nodeLevel] [int] NOT NULL,
CONSTRAINT [PK_node] PRIMARY KEY CLUSTERED
(
[nodeID] ASC
)WITH (PAD_INDEX = OFF, IGNORE_DUP_KEY = OFF) ON
[PRIMARY]
) ON [PRIMARY]
CREATE TABLE [dbo].[edge](
[edgeID] [int] NOT NULL,
[graphID] [int] NOT NULL,
[nodeID1] [int] NOT NULL,
[nodeID2] [int] NOT NULL,

• Tiếp tục tìm hiểu và nghiên cứu “Cơ sở dữ liệu đồ thị” và áp dụng hệ cơ sở dữ
liệu khác trong việc lưu trữ dữ liệu đồ thị để tối ưu hóa thời gian tìm kiếm.
• Phát triển hoàn chỉnh thành bài luận cuối khóa với những mục tiêu đã đề ra lúc
đầu.
• Kết hợp với bài tiểu luận trong các chuyên đề trước đã thực hiện: “Tìm hiểu về
Logic Mờ” để áp dụng cho việc tìm gần đúng đối với trường hợp sử dụng ảnh
gương mặt để lưu trữ hoặc tìm theo ảnh dấu vân tay.
GVHD : PGS.TS Đỗ Phúc Trang 14
HVTH : Mã Tuấn Huy
Cơ sở dữ liệu nâng cao
CHƯƠNG IV. TÀI LIỆU THAM KHẢO
1. Tài liệu giấy:
• A/ Prof. Do Phuc - Mining, Indexing and Searching Graph Databases
• HOÀNG KIẾM – THANH THỦY – CHI MAI – “Đôi cánh I – CA – RƠ nhà
xuất bản thống kê HÀ NỘI – 1990”
• PGS.TS. Đỗ Văn Nhơn – TS. Đỗ Phúc – “Giáo trình Các Hệ Cơ Sở Tri Thức, Đại
học Quốc gia Tp.HCM, 2002”.
• Bài thu hoạch các khóa trước (khóa 2008 – 2009 - 2010).
2. Tài liệu Web:
• />%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%93_th%E1%BB%8B
%29#.C4.90.E1.BB.93_th.E1.BB.8B_v.C3.B4_h.C6.B0.E1.BB.9Bng
• />• />GVHD : PGS.TS Đỗ Phúc Trang 15
HVTH : Mã Tuấn Huy