Báo cáo chuyên đề cơ sở dữ liệu nâng cao Network Data Model
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (946.18 KB, 35 trang )
Báo cáo chuyên đề cơ sở dữ liệu nâng cao
LỜI MỞ ĐẦU
Ngày nay, hầu hết các ứng dụng đều có một lượng dữ liệu khổng lồ.Vấn đề lưu trữ và xử
lý dữ liệu trở nên khó khăn và cần được quan tâm hơn, dữ liệu linh hoạt và được thay đổi
gần như theo thời gian thậm chí thay đổi cấu trúc cơ bản của dữ liệu. 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 Dữ liệu đồ thị là cách thức lưu trữ thông tin ở dạng đồ thị những
đỉnh và cạnh.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ự trình bày khái quát về cơ sở dữ liệu đồ thị, đồng thời trình bày trình
bày một cách chi tiết việc ứng dụng network data model của oracle để lưu trữ dữ liệu đồ
thị và sử dụng Java API để phân tích dữ liệu đã lưu trữ.
Em xin chân thành cảm ơn PGS.TS. Đỗ Phúc – Giảng viên môn học cơ sở dữ liệu nâng
cao đã truyền đạt những kiến thức vô cùng quý báu, 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ĩ Công nghệ thông tin qua mạng 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.
Chân thành cám ơn!
Nguyễn Ngọc Diễm
HVTH: Nguyễn Ngọc Diễm Trang: 1
Báo cáo chuyên đề cơ sở dữ liệu nâng cao
PHẦN I. TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU ĐỒ THỊ
I. Khái quát đồ thị
Đồ thị là một tập các đối tượng được gọi là các đỉnh được nối với nhau bởi các
cạnh.Có 2 loại đồ thị : đồ thị vô hướng và đồ thị có hướng.
Đồ thị vô hướng
Đồ thị có hướng
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ị trọng số để biểu diễn những khái niệm khác nhau như chiều dài con
đường,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 ở một thời điểm nào đó…
Nhiều bài toán thực tế có thể được biểu diễn bằng đồ thị. Ví dụ, cấu trúc liên kết của
một website có thể được biểu diễn bằng một đồ thị có hướng, XML, cấu trúc phân tử hóa
học, cấu trúc protein, đối tượng 3D…
II. 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…
HVTH: Nguyễn Ngọc Diễm Trang: 2
Báo cáo chuyên đề cơ sở dữ liệu nâng cao
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).UDFs được sử dụng mọi
nơi mà người sử dụng muốn.
SBGE sử dụng những hàm mở rộng của DB2 để thao tác trên dữ liệu đồ thị.Với
SBGE có thể dễ dàng quản lý dữ liệu đồ thị thông qua các nút, cạnh.
Với RDBMSs cho phép người sử dụng định nghĩa cũng như tìm kiếm những đồ
thị con.RDBMSs có thể linh hoạt trên một đồ thị dữ liệu lớn bởi vì SQL có thể tìm kiếm
mà không đòi hỏi việc load cả dữ liệu đồ thị lên bộ nhớ tạm. Do đó, SBGE chính là sự
kết hợp giữa SQL để quản lý dữ liệu của đồ thị và những hàm mở rộng để quản lý những
hàm truy xuất của đồ thị.
Lưu trữ bằng network data model trong oracle
Oracle hỗ trợ những procedure để tạo dữ liệu đồ thị.Tiểu luận này sẽ trình bày chi
tiết cách sử dụng data network model để lưu trữ cũng như phân tích dữ liệu đồ thị.
III. Ứng dụng của cơ sở dữ liệu đồ thị
Dữ liệu đồ thị có nhiều ứng dụng trong thực tế như : trong sinh học (dùng cơ sở dữ
liệu đồ thị để lưu trữ cấu trúc genes, protein hoặc mô hình của một tế bào…), trong hóa
học ( Cấu trúc phân tử của một chất), lưu trữ ảnh, mạng xã hội, cấu trúc liên kết
website…
PHẦN II. NETWORK DATA MODEL
I. Giới thiệu
Data network model được tích hợp vào oracle để lưu trữ dữ liệu đồ thị.Có 2 bước
chính để thao tác trên dữ liệu đồ thị sử dụng data network model : Lưu trữ dữ liệu và
phân tích dữ liệu.Với data network model, đồ thị được lưu trữ thông qua các table node,
link, path. Và sử dụng PL/SQL hoặc Java API để phân tích dữ liệu đã lưu trữ.
Data network model thao tác trên hai loại dữ liệu đồ thị: Logical và Spatial. Với
đồ thị dang Spatial, người sử dụng có thể lưu trữ được thông tin không gian của các đỉnh
như vị trí địa lý, kinh độ, vĩ độ để từ đó có thể có những thao tác thích hợp. Đồ thị
Spatial thường được sử dụng để lưu trữ các dữ liệu GIS (hệ thống thông tin địa lý). Còn
đồ thị logical thì ngược lại, chỉ lưu trữ được những thông tin cơ bản của một node như
tên, trạng thái, nhãn Ví dụ như lưu trữ : XML, cấu trúc protein, và mạng xã hội…
Mạng Spatial :
Mạng logical
HVTH: Nguyễn Ngọc Diễm Trang: 3
Báo cáo chuyên đề cơ sở dữ liệu nâng cao
Đây là mô hình tương tác của client với database thông quan network data model
II. Các thành phần chính của network data model
Việc sử dụng data network model để quản lý dữ liệu đồ thị bao gồm các thành
phần chính sau :
Mô hình dữ liệu đồ thị được lưu trữ trong database dưới dạng các table.
Những hàm SQL để định nghĩa và quản lý dữ liệu (nằm trong gói SDO_NET).
Những hàm phân tích đồ thị sử dụng Java API.Java API phân tích dữ liệu đồ
thị bằng cách copy dữ liệu từ database và lưu trữ vào bộ nhớ tạm trong quá
trình thao tác.
Phân tích dữ liệu đồ thì bằng PL/SQL.
Đây là mô hình mô tả việc sử dụng Java API để thao tác trên dữ liệu đồ thị được
lưu trữ sẳn
HVTH: Nguyễn Ngọc Diễm Trang: 4
Báo cáo chuyên đề cơ sở dữ liệu nâng cao
III. Cấu trúc dữ liệu lưu trữ đồ thị
Một dữ liệu đồ thị được lưu trữ trong database thông qua 2 table chính : Node và
Link.Tuy nhiên bên cạnh đó còn có 2 table khác đó là Path và Path Link, dữ liệu trong
2 table này chính là kết quả của những hàm phân tích đồ thị ví dụ như tìm đường đi
ngắn nhất giữa 2 node, tìm danh sách node liền kề…
Hình sau miêu tả mối quan hệ giữa các table trong database.
NODES : đỉnh của đồ thị
LINKS : cạnh của đồ thị
PATHS : đường dẫn của 2 đỉnh trong đồ thị.
PATH_LINKS : Lưu trữ những cạnh mà đường dẫn PATHS đi qua. Khóa chính
của table PATHS chính là khóa ngoại của table PATH_LINKS
IV. Lưu trữ đồ thị bằng table có sẵn
1. Tạo NODE
Sử dụng procedure SDO_NET.CREATE_NODE_TABLE để tạo ra table node.
Đây là procedure đã được oracle định nghĩa sẳn, tham số của procedure trên là
Table_node_name : Tên của table sẽ lưu trữ các nút của đồ thị
Geom_type : chỉ định loại đồ thị mà node này sẽ thuộc.SDO_GEOMETRY
với đồ thị Spatial và null với đồ thị logical.
Geom_column : chỉ định cột sẽ lưu trữ dữ liệu không gian nếu là đồ thị
Spatial.
Cost_column : Tên của cột chứa các chi phí giá trị được liên kết với các nút.
No_of_hierarchy_levels: Số level phân cấp của đồ thị.
HVTH: Nguyễn Ngọc Diễm Trang: 5
SDO_NET.CREATE_NODE_TABLE(
Table_node_name varchar2,
Geom_type varchar2,
Geom_column varchar2,
Cost_column varchar2,
No_of_hierarchy_levels number)
Báo cáo chuyên đề cơ sở dữ liệu nâng cao
Hình sau có no_of _hierachy_levels là 2.
Ví dụ :
EXECUTE SDO_NET.CREATE_NODE_TABLE('NODES_DATA', NULL,NULL, NULL, 1);
Câu lệnh trên sẽ tạo ra một table có tên là NODES_DATA, table này sẽ lưu trữ toàn bộ
các nút của đồ thị logical không phân cấp.
Table NODES_DATA sau khi tạo sẽ có các thuộc tính sau:
Tên thuộc tính Kiểu Mô tả
NODE_ID Number ID của node, là duy nhất không được trùng với các id
khác
NODE_NAME Varchar2 Tên của node
NODE_TYPE Varchar2 Loại node, do người sử dụng tự định nghĩa
ACTIVE Varchar2 Y nếu nút là active có nghĩa là có thể hiển thị trong
mạng, N nếu node được ẩn.
PARTITION_ID Number Đây là khóa ngoại của table PARTITION
Ví dụ : Ta có mạng sau
Ta sẽ tiến hành insert 3 dòng vào table NODES_DATA, mỗi dòng sẽ lưu thông tin một
đỉnh của đồ thị
HVTH: Nguyễn Ngọc Diễm Trang: 6
Báo cáo chuyên đề cơ sở dữ liệu nâng cao
2. Tạo LINK
Sử dụng procedure SDO_NET.CREATE_LINK_TABLE để tạo table link lưu trữ
sự kết nối giữa 2 node trong một mạng.Hay nói cách khác, một link chính là một cạnh
trong đồ thị.
Các tham số của procedure SDO_NET.CREATE_LINK_TABLE là :
Tương tự như procedure tạo table Node.
Ví dụ :
EXECUTE SDO_NET.CREATE_LINK_TABLE('LINKS_DATA', NULL,NULL, NULL, 1);
Câu lệnh trên sẽ tạo ra table LINKS_DATA với các thuộc tính như sau
Tên thuộc tính Kiểu Mô tả
LINK_ID Number ID link, là duy nhất
LINK_NAME Varchar2 Tên của link liên kết
START_NODE_ID Number ID của node bắt đầu. Nếu đồ thị có hướng thì đây
là ID của đỉnh gốc.
END_NODE_ID Number ID của node kết thúc.Nếu đồ thị có hướng thì đây
là ID của định ngọn.
LINK_TYPE Varchar2 Loại link, do người sử dụng tự định nghĩa.
ACTIVE Varchar2 Y : nếu link này được hiển thị trong đồ thị, N :
nếu link bị ẩn đi.
LINK_LEVEL Number Cấp độ của link, được sử dụng trong đồ thị phân
cấp.Cấp độ của link cũng chính là độ ưu tiên khi
duyệt độ thị tìm đường đi.
Ví dụ :
HVTH: Nguyễn Ngọc Diễm Trang: 7
INSERT INTO NODES_DATA (NODE_ID, NODE_NAME, ACTIVE) VALUES (1, 'N1', 'Y');
INSERT INTO NODES_DATA (NODE_ID, NODE_NAME, ACTIVE) VALUES (2, 'N2', 'Y');
INSERT INTO NODES_DATA (NODE_ID, NODE_NAME, ACTIVE) VALUES (3, 'N3', 'Y');
SDO_NET.CREATE_LINK_TABLE(
Table_link_name varchar2,
Geom_type varchar2,
Geom_column varchar2,
Cost_column varchar2,
No_of_hierarchy_levels number)
Báo cáo chuyên đề cơ sở dữ liệu nâng cao
Đồ thị có 3 cạnh cũng chính là 3 link liên kết giữa các node.Khi lưu trữ đồ thị trên vào
database, mỗi cạnh được ánh xạ thành một dòng trong table LINKS_DATA được tạo
bằng procedure trên.
Cụ thể như sau
3. Tạo PATH
Sử dụng procedure SDO_NET.CREATE_PATH_TABLE để tạo table Paths trong
database, table này sẽ chứa đường đi giữa 2 node bất kỳ trong đồ thị.
Dữ liệu table này lúc đầu mặc định là rỗng, sẽ được thêm vào nếu người sử dụng
muốn lưu lại thông tin khi phân tích đồ thị.
Các tham số cần truyền vào khi gọi procedure trên :
Table_ Path _name : Tên của table sẽ lưu trữ danh sách đường đi giữa hai node
bất kỳ của đồ thị.
Geom_type : chỉ định loại đồ thị mà đường dẫn này sẽ thuộc.SDO_GEOMETRY
với đồ thị Spatial và NULL với đồ thị logical.
Ví dụ : Nếu gọi procedure EXECUTE SDO_NET.CREATE_PATH_TABLE('PATHS', NULL);
Thì sẽ tạo một table PATHS trong database với các thuộc tính sau:
Tên thuộc tính Kiểu Mô tả
PATH_ID NUMBER ID , là duy nhất
PATH_NAME Varchar2 Tên đường đi
START_NODE_ID Number ID của node bắt đầu của link đầu tiên trong
danh sách link mà con đường này đi qua.
END_NODE_ID Number ID của node cuối cùng của link cuối cùng
trong danh sách link mà con đường này đi
qua.
PATH_TYPE Varchar2 Loại Path do người sử dụng tự định nghĩa
COST Number Chi phí khi thực hiện đi theo con đường trên
ví dụ như thời gian lái xe khi khảo sát trong
đồ thị giao thông, khoảng cách đi giữa hai
node giao thông…
HVTH: Nguyễn Ngọc Diễm Trang: 8
INSERT INTO LINKS_DATA (LINK_ID, LINK_NAME, START_NODE_ID, END_NODE_ID,
ACTIVE) VALUES (1, 'L1', 1, 2, 'Y');
INSERT INTO LINKS_DATA (LINK_ID, LINK_NAME, START_NODE_ID, END_NODE_ID,
ACTIVE) VALUES (2, 'L2', 2, 3, 'Y');
INSERT INTO LINKS_DATA (LINK_ID, LINK_NAME, START_NODE_ID, END_NODE_ID,
ACTIVE) VALUES (3, 'L3', 1, 3, 'Y');
SDO_NET.CREATE_NODE_TABLE(
Table_Path_name varchar2,
Geom_type varchar2)
Báo cáo chuyên đề cơ sở dữ liệu nâng cao
SIMPLE Varchar2 Y: nếu là đường đi đơn, N: trường hợp
ngược lại.Đường đi đơn là con đường mà từ
node đầu tiên đến node cuối cũng mỗi link
được duyệt qua duy nhất chỉ một lần.
BIDIRECTED CHAR(1) Chỉ đồ thị có hướng hay vô hướng
Ví dụ với đồ thị dữ liệu sau :
Ta lưu trữ đường đi từ A đến F như sau :
A B C F
Thì lúc này dữ liệu trong table PATHS sẽ được insert như sau
Vì đây là đồ thị không trọng số nên mỗi link đi qua có chi phí như nhau và được tính là
1.Vậy với đường đi trên sẽ tốn chi phí là 3.
4. Tạo PATH_LINK
Sử dụng procedure SDO_NET.CREATE_PATH_LINK_TABLE để tạo table PATHS_LINK
trong database, table này sẽ lưu trữ cụ thể những link mà một đường đi sẽ đi qua.
Các tham số của procedure trên là
Table_Path_Link_name : Tên table sẽ lưu trữ thông tin trên.
Khi procedure trên thực thi xong thì một table có tên là PATH_LINKS sẽ được tạo
trong database, thuộc tính của table trên bao gồm :
Tên thuộc tính Kiểu Mô tả
PATH_ID Number ID của đường đi,đây là khóa ngoại của table PATHS được
tạo bên trên
LINK_ID Number ID link, đây là khóa ngoại của table LINKS.PATH_ID và
LINK_ID khóa chính trong table này.
HVTH: Nguyễn Ngọc Diễm Trang: 9
INSERT INTO PATHS (PATH_ID, PATH_NAME, START_NODE_ID, END_NODE_ID,
COST, SIMPLE) VALUES (1, 'P1', A, F,3 ,'Y');
SDO_NET.CREATE_PATH_LINK_TABLE(
Table_Path_Link_name varchar2)
Báo cáo chuyên đề cơ sở dữ liệu nâng cao
SEQ_NO Number Số lượng link_Id trong đường đi này, SEQ_NO mặc định
là 1 ( đường đi chỉ chứa 1 link có mã số là LINK_ID),
thuộc tính này cho phép đường đi có thể lặp lại cạnh đã đi
rồi.
Với đường đi A B C F trong ví dụ trên thì dữ liệu được lưu trữ vào table
PATH_LINKS như sau:
V. Lưu trữ đồ thị bằng table tự tạo
Bên cạnh sử dụng những table có sẳn, người sử dụng vẫn có thể tự tạo ra những table
lưu trữ thông tin đồ thị .
Tạo table NODES
Tạo table LINKS
Tạo table PATHS
Tạo table PATH_LINKS
HVTH: Nguyễn Ngọc Diễm Trang: 10
CREATE TABLE NODES
( USER_NAME varchar(255), Node Id
PASS varchar(255), Node name
NODE_TYPE varchar(255),
ACTIVE varchar(255),
PARTITION_ID number
);
CREATE TABLE LINKS
(
LINK_ID number,
LINK_NAME varchar(255),
START_NODE_ID varchar(255),
END_NODE_ID varchar(255),
ACTIVE varchar(255),
LINK_LEVEL number
);
CREATE TABLE PATHS
(
PATH_ID number,
PATH_NAME varchar(255),
PATH_TYPE varchar(255),
START_NODE_ID varchar(255),
END_NODE_ID varchar(255),
COST number,
SIMPLE varchar(1));
);
INSERT INTO PATH_LINKS (PATH_ID, LINK_ID,SEQ_NO) VALUES (1, 1,1);
INSERT INTO PATH_LINKS (PATH_ID, LINK_ID,SEQ_NO) VALUES (1, 2,1);
INSERT INTO PATH_LINKS (PATH_ID, LINK_ID,SEQ_NO) VALUES (1, 3,1);
Báo cáo chuyên đề cơ sở dữ liệu nâng cao
Số lượng thuộc tính trong các table trên vẫn có thể thay đổi tùy thuộc vào yêu cầu của
từng đồ thị.
VI. Tạo mạng dữ liệu
Mỗi mạng dữ liệu khi được tạo ra sẽ lưu trữ vào table
user_sdo_network_metadata thuộc tính của table đó như sau
Tên thuộc tính Kiểu Mô tả
NETWORK VARCHAR2(24) Tên của mạng lưu trữ, là duy nhất.
NETWORK_ID NUMBER ID của mạng đang lưu trữ.
NETWORK_CATEGORY VARCHAR2(12) Có 2 option.SPATIAL nếu mạng lưu
trữ dữ liệu không gian, ngược lại là
LOGICAL.
GEOMETRY_TYPE VARCHAR2(24) Loại của dữ liệu không gian nếu
NETWORK_CATEGORY là
SPATIAL, có 3 lựa chọn
SDO_GEOMETRY,LRS_GEOMETR
Y,TOPO_GEOMETRY
NETWORK_TYPE VARCHAR2(24) Người sử dụng tự định nghĩa để miêu
tả loại mạng lưu trữ.
NO_OF_HIERARCHY_LE
VELS
NUMBER Chiều cao phân cấp của mạng, là 1
nếu mạng không có sự phân cấp.
NO_OF_PARTITIONS NUMBER Số partition của mạng lưu trữ
LINK_DIRECTION VARCHAR2(12)
UNDIRECTED : Đồ thị vô hướng
DIRECTED : Đồ thị có hướng
NODE_TABLE_NAME VARCHAR2(32) Tên table lưu trữ danh sách
node(đỉnh) của đồ thị
NODE_GEOM_COLUMN VARCHAR2(32) Tên của cột chứa dữ liệu không gian
trong table lưu trữ danh sách
node.Thuộc tính này chỉ chứa dữ liệu
khi đồ thị đang xét là SPATIAL.
NODE_COST_COLUMN VARCHAR2(10
24)
Tên của cột lưu trữ thông tin về chi
phí của node. Mặc định là 0
LINK_TABLE_NAME VARCHAR2(32) Tên table lưu trữ danh sách link liên
HVTH: Nguyễn Ngọc Diễm Trang: 11
CREATE TABLE PATH_LINKS
(
PATH_ID number,
LINK_ID number,
SEQ_NO number
);
Báo cáo chuyên đề cơ sở dữ liệu nâng cao
kết giữa 2 node trong đồ thị
LINK_GEOM_COLUMN VARCHAR2(32) Tên của cột chứa dữ liệu không gian
trong table lưu trữ danh sách
link.Thuộc tính này chỉ chứa dữ liệu
khi đồ thị đang xét là SPATIAL.
LINK_COST_COLUMN VARCHAR2(10
24)
Tên của cột lưu trữ thông tin về chi
phí của node. Mặc định là 1
PATH_TABLE_NAME VARCHAR2(32) Tên của table PATHS.Không chỉ định
thì mặc định sẽ không sử dụng table
PATHS trong đồ thị này.
PATH_LINK_TABLE_NA
ME
VARCHAR2(32) Tên của table Path_Links.Được chỉ
định khi và chỉ khi thuộc tính
PATH_TABLE_NAME được chỉ
định.
PATH_GEOM_COLUMN VARCHAR2(32) Tên của cột lưu trữ thông tin không
gian trong table PATHS
LRS_TABLE_NAME VARCHAR2(32) Nếu GEOMETRY_TYPE là
SDO_GEOMETRY, thì thuộc tính
này sẽ chứa tên của table mà lưu trữ
thông tin không gian.
LRS_GEOM_COLUMN VARCHAR2(32) Nếu LRS_TABLE_NAME chứa tên
table, thì thuộc tính này sẽ chứa tên
cột dữ liệu không gian của table đó
PARTITION_TABLE_NA
ME
VARCHAR2(32) Tên table lưu partition của mạng dữ
liệu.
Có 2 cách để tạo một cấu trúc mạng lưu trữ dữ liệu đồ thị :
Cách 1 : Dùng procedure mà oracle đã hỗ trợ :
Có 2 hàm procedure tương ứng với 2 loại mạng Spatial và
Logical.SDO_NET.CREATE_SDO_NETWORK tạo ra mạng Spatial,
SDO_NET.CREATE_LOGICAL_NETWORK tạo ra mạng Logical.
Procedure trên chứa 4 tham số : Tên mạng, số phân cấp mạng. loại đồ thị được lưu trữ có
hướng hay vô hướng, trạng thái node có chi phí hay không.
Khi procedure trên được thực thi thì sẽ tạo ra một cấu trúc mạng như sau :
Tạo một mạng SPATIAL có tên là US_ROAD, tạo ra một table
US_ROAD_NODE$ để lưu trữ các node của mạng, table US_ROAD_LINK$ lưu trữ các
link của mạng,table US_ROAD_PATH$ để lưu trữ các đường đi của 2 node trong mạng,
US_ROAD_PLINK$ để lưu trữ danh sách link mà đường đi giữa 2 node đi qua.
HVTH: Nguyễn Ngọc Diễm Trang: 12
EXEC SDO_NET.CREATE_SDO_NETWORK ('US_ROADS',1,TRUE,FALSE)
Báo cáo chuyên đề cơ sở dữ liệu nâng cao
Chú ý : Procedure trên không tự động rollback nếu bị lỗi. Do đó nếu đang tạo cấu trúc
mạng mà bị lỗi, phải tiến hành drop mạng bằng procedure DROP_NETWORK trước khi
tạo lại mạng mới có tên như cũ.
Với cách này, sẽ không linh hoạt trong việc sử dụng, nếu nhưng người sử dụng muốn có
một sự thay đổi nào đó trong cấu trúc của các table thì không thể dùng cách này được.
HVTH: Nguyễn Ngọc Diễm Trang: 13
!
"#$%&'%(
)*"#$%&%+(
#""#$%&,(
* !
- ) ).- )
/
/ !
/ "#$%&'%#$(
!
!
/)*"#$%&%+#$(
#""#$%&,#$(
/" !
- ) ).- )
# !
!#"#$%&,(
*$
*$ !
*$ "#$%&'%#$(
*$)*"#$%&%+#$(
!
!
# !
*"#$%&,#$(
- ) ).- )
*/
*$ !
/ !
!
Báo cáo chuyên đề cơ sở dữ liệu nâng cao
Cách 2: Đây là cách linh hoạt hơn, dùng để giải quyết khuyết điểm ở cách
thứ nhất
Insert trực tiếp vào table user_sdo_network_metadata
HVTH: Nguyễn Ngọc Diễm Trang: 14
#001230
#!20432&
23 !5
3432- )5
#204326* )/)&23(
(7
#001260
#!00&
26 !5
0023 !5
223 !5
48#$&,(5
0093- )5
002901 !5
084 !5
0#$&,(5
#006* )/)&26(
(7
#0010
#!01&
01 !5
0023 !5
223 !5
30 !5
"#$%&,(5
0193- )5
#016* )/)&01(
(7
#001260
#!0126&
0125
2625
:2325
#01266* )/)&01526(
(7
Báo cáo chuyên đề cơ sở dữ liệu nâng cao
Table us_ streets chứa 2 cột biểu diển chi phí : chiều dài con đường(002901(
và thời gian đi hết con đường đó(084(
Mạng US_ROAD được đã định nghĩa sử dụng Street_length cho cột lưu trữ chi
phí của mạng.Điều này đồng nghĩa với việc có thể tính được đoạn đường đi ngắn nhất
giữa hai node bất kỳ.
HVTH: Nguyễn Ngọc Diễm Trang: 15
;/ &
;/5
;/#-)5
- ))*5
<$#$)"
<*5
/#5
! 5
- # 5
## 5
/! 5
/- # 5
/## 5
*$! 5
*$- # 5
*$/!
(
"&
==520>36&6(
=*=520>36093
=- )=59300
,5233?118
,5233?4432
=#=526432
=#=52302
=#=5239332
5233032&2330023
==52602
=- =5269332
=-$=5263032
=*$=50102
=*$- =5019332
=*$/=012602
(7
# 7
Báo cáo chuyên đề cơ sở dữ liệu nâng cao
Bên cạnh đó, việc tính toán thời gian đi nhanh nhất giữa 2 node bất kỳ vẫn có thể
được yêu cầu. Để giải quyết được bài toán đó thì phải tạo thêm một mạng thứ 2, mạng
này sẽ có cấu trúc tương tự mạng US_ROAD nhưng cột chi phí giữa hai node là
travel_time.
HVTH: Nguyễn Ngọc Diễm Trang: 16
;/ &
;/5
;/#-)5
- ))*5
<$#$)"5
<*5
/#5
! 5
- # 5
## 5
/! 5
/- # 5
/## 5
*$! 5
*$- # 5
*$/!
(
"&
= =520>36&6(
=*=520>36093
=- )=59300
,5233?118
,5233?4432
=#=526432
=#=52302
=#=5239332
5233032&23300238(
==52602
=- =5269332
=" =5263032
=*$=50102
=*$- =5019332
=*$/=012602
(7
Báo cáo chuyên đề cơ sở dữ liệu nâng cao
VII. Kiểm tra mạng dữ liệu được tạo
Sau khi tạo xong cấu trúc mạng, để chắc chắn mạng tạo không bị lỗi cần phải kiểm
tra lại bằng lệnh sau
SELECT SDO_NET.VALIDATE_NETWORK('US_ROADS') FROM DUAL;
Kết quả :
NULL : nếu như mạng không tồn tại
TRUE : nếu mạng tạo thành công và không bị lỗi
Một chuổi string miêu tả lỗi nếu mạng được định nghĩa không chính xác.
VIII. Tạo cây chỉ mục tìm kiếm
Việc tạo chỉ mục để tìm kiếm trong oracle được kế thừa từ cấu trúc của R-Tree
index. R-Tree là một cây cân bằng tương tự như B-Tree. Với ý tưởng như sau : các
index sẽ nằm tại các node lá chứa các điểm dữ liệu, khi đó việc tìm kiếm sẽ thực hiện
trên một số lượng nhỏ các nút.Thuật toán tìm kiếm duyệt cây từ gốc đi xuống theo
cách tương tự như B-Tree. Tuy nhiên khi thăm một nút sẽ có nhiều hơn một cây con
dưới node đó đang cần được tìm kiếm, vì lý do đó thuật toán không đảm bảo thực
hiện tốt trong trường hợp xấu nhất. Tuy nhiên với nhiều kiểu của dữ liệu, thuật toán
cập nhật sẽ duy trì hình dạng của cây để cho phép thuật toán tìm kiếm loại đi những
vùng không liên quan của không gian index và kiểm tra duy nhất dữ liệu gần vùng tìm
kiếm.
Ví dụ: Mỗi vùng sẽ được ánh xạ thành một nhánh trong cây chỉ mục.
Cây chỉ mục được lưu trữ trong database oracle như sau
Ví dụ như table Customers có cột location lưu trữ vị trí địa lý của từng khách hàng
như số nhà tên đường tên thành phố…
HVTH: Nguyễn Ngọc Diễm Trang: 17
Báo cáo chuyên đề cơ sở dữ liệu nâng cao
Hình trên mô tả cách mà database lưu trữ và quản lý cây chỉ mục tìm kiếm.Table
USER_SDO_INDEX_METADATA lưu trữ cây chỉ mục được tạo.Mỗi một nút là của cây chỉ
mục sẽ được ánh xạ thành một row trong table MDRT_<>$.
Hai loại đồ thị Logical và Spatial tương ứng với hai cách tạo cây chỉ mục khác
nhau. Đối với đồ thị logical ta chỉ cần tạo indexes đơn giản bằng lệnh sau :
Còn với loại spatial, để tạo indexes cần thực hiện 2 bước sau :
Bước 1: Insert dữ liệu các lớp dữ liệu không gian trước khi tạo chỉ mục.
HVTH: Nguyễn Ngọc Diễm Trang: 18
CREATE INDEX sdo_nodes_idx ON nodes_data(NODE_NAME);
INSERT INTO user_sdo_geom_metadata
(TABLE_NAME,
COLUMN_NAME,
DIMINFO,
SRID)
VALUES (
'US_INTERSECTIONS',
'LOCATION',
SDO_DIM_ARRAY(
SDO_DIM_ELEMENT('X', 0, 300, 0.005),
SDO_DIM_ELEMENT('Y', 0, 200, 0.005)
),
NULL
);
Báo cáo chuyên đề cơ sở dữ liệu nâng cao
Với câu lệnh trên sẽ định nghĩa tọa độ x,y của cột Location trong table
US_INTERSECTION có giá trị nhỏ nhất là 0 lớn nhất là 300 đối với x, 200 đối với y.
Với độ sai số là 0.005.Độ sai số miêu tả nếu 2 vị trí ở gần nhau và khoảng cách nhỏ hơn
0.005 thì xem như là một vị trí.
Bước 2: Tạo chỉ mục để tìm kiếm theo cột Location
Khi câu lệnh trên thực thi xong thì sẽ tạo 1 cây chỉ mục index R – tree trong table
USER_SDO_INDEX_METADATA đồng thời tạo một indexes trong table USER_INDEXES.
Các tham số khi tạo chỉ mục
Tham số TABLESPACE
Chỉ định một tablespace khác để lưu trữ chỉ mục.Mỗi database trong oracle có một
tablespace riêng .Trong ví dụ trên ta sẽ lưu trữ cây chỉ mục trong tablespace TBS_3.
Để xem danh sách tablespace ta xem trong table user_tablespaces
Lưu ý: chỉ sử dụng những tablespace có sẳn trong USER_TABLESPACES mà thôi.
Tham số WORK_TABLESPACE
Việc tương tác lên cây chỉ mục là thường xuyên như xóa hoặc thêm chỉ mục, chính vì
vậy để tránh tình trạng phân mảnh bộ nhớ khi ta tạo hoặc xóa chỉ mục, ta sẽ chỉ định
tablespaces mà chỉ mục này làm việc bằng tham số WORK_TABLESPACE.
Tham sốLAYER_GTYPE:
HVTH: Nguyễn Ngọc Diễm Trang: 19
#@20432AUS_INTERSECTION &3432(
@)* ).*@
#@B2A2B02&B322(
@)* ).*@
* &=0029=(7
#@20432AUS_INTERSECTION &3432(
@)* ).*@
* &=!*#C!'=(7
#@20432AUS_INTERSECTION &3432(
@)* ).*@
* &= WORK!*#C!'=(7
Báo cáo chuyên đề cơ sở dữ liệu nâng cao
Tham số này được sử dụng để chỉ định loại dữ liệu không gian mà người sử dụng lưu
trữ : điểm, đường, vùng.Nếu không sử dụng tham số này thì mặc định là tấc cả các loại
dữ liệu trên.
Ngoài ra còn các tham số khác như SDO_DML_BATCH_SIZE, SDO_LEVEL,
SDO_INDX_DIMS.
IX. Phân tích dữ liệu đồ thị bằng Java API
1. Giới thiệu
Java API hỗ trợ những hàm phân tích mạng như tìm đường đi ngắn nhất giữa 2
node, tìm danh sách những node liền kề node cho trước…Để sử dụng được java API, ứng
dụng phải add thư viện hỗ trợ java API.Danh sách các thư viện cần add
Package JAR File Vị trí Chức năng
oracle.spatial.network sdonm.jar $ORACLE_HOME/md/jlib Phân tích mạng
oracle.spatial.geometry sdoapi.jar $ORACLE_HOME/md/jlib Đối tượng
Geometry
oracle.spatial.util sdoutl.jar $ORACLE_HOME/md/jlib Các tiện ích
ojdbc14.jar $ORACLE_HOME/jdbc/lib Driver JDBC
Java API cung cấp các lớp chính sau:
Network,Node,Link,Path : dùng để lưu trữ và quản lý các đối tượng mạng.
NetworkManager : Class này dùng để phân tích mạng, đọc mạng dữ liệu từ database cũng
như ghi thông tin xuống database.Đây là class quan trọng nhất.
NetworkFactory : Class này dùng để tạo mạng và các đối tượng mạng.
2. Phân tích mạng:
Tấc cả những hàm phân tích mạng đều được cung cấp bởi các phương thức trong
class NetworkManager.Những phương thức này thực thi trên dữ liệu mạng được copy từ
database.Do đó việc đầu tiên của việc phân tích mạng là load mạng dữ liệu từ database.
Có 2 cách load :
Network UNet =NetworkManager.readNetwork(dbConnection, "UNET");
Tham số truyền vào là connection xuống database và tên của mạng dữ liệu.Với
cách load này thì người sử dụng chỉ có thể thao tác đọc dữ liệu từ mạng vừa load mà
thôi.Không thể update được dữ liệu mới.
Network UNet =NetworkManager.readNetwork(dbConnection, "UNET",
true);
Với cách load thứ 2 truyền thêm tham số true vào cho phép update dữ liệu
mới.Tuy nhiên ở mỗi thời điểm chỉ duy nhất một user được quyền update mạng mà thôi
để tránh tình trạng đụng độ xảy ra.
HVTH: Nguyễn Ngọc Diễm Trang: 20
#@20432AUS_INTERSECTION &3432(
@)* ).*@
* &= LAYER_GTYPE=POINT'(7
Báo cáo chuyên đề cơ sở dữ liệu nâng cao
Sử dụng đồ thị sau để làm minh họa cho các hàm phân tích mạng.Đây là đồ thị vô hướng.
Tìm đường dẫn ngắn nhất giữa 2 nút:
Sử dụng hàm shortestPath() của class NetworkManager.Kết quả trả về là kết quả
tối ưu nhất.Đường dẫn ngắn nhất giữa hai nút là đường có chi phí ít nhất.Chi phí của nút
và link được định nghĩa lúc tạo cấu trúc của mạng.Chi phí này có thể là khoảng cách
ngắn nhất, thời gian ít nhất hoặc bất cứ thuộc tính nào mà người sử dụng muốn.Chỉ xét
những node Active = Y trong danh sách node của mạng.
HVTH: Nguyễn Ngọc Diễm Trang: 21
DD-0130001?323+03'
0>36000C07
003C+7
23C'7
*0101C0>36 29.1300*01&0005003523(7
DD13>0130223?26
0.30.202&E*0130FEG01.90#30&((7
0.30.202&E3?26FEG01.903?26&((7
0.30.202&E01EG01.&((7
DD13>012608
0.30.202&E2608FE(7
26HI26C01.9026&(7
?3&20CJ7B26.29017GG(
0.30.202&E26EG26HI.90&(GEK0E
G26HI.90&(GEK0EG26HI.90#30&((7
DD13>012308
0.30.202&E308FE(7
3HI23C01.903&(7
?3&20CJ7B23.29017GG(
0.30.202&E3EG23HI.90&(GEK0E
G23HI.90&(GEK0EG23HI.90#30&((7
Báo cáo chuyên đề cơ sở dữ liệu nâng cao
Kết quả trả về :
Save danh sách link trên vào table Path.
Danh sách bạn của node cho trước.
Sử dụng hàm nearestNeighbors của NetworkManager để liệt kê danh sách những nút gần
nút cho trước nhất.
HVTH: Nguyễn Ngọc Diễm Trang: 22
*0130F'.J
3?26F'
010
2608F
26LL,.J
26,J,J,.J
26'',.J
308F
3++J.J
3MMJ.J
3NNJ.J
3''J.J
DD-8203010132000290101.
01.0&E*EG01.90&(GE<A32E(7
DD#30019303?0101
01.30-30&J.JM(7
DD0101030120>36
20>36.*01&01(7
Báo cáo chuyên đề cơ sở dữ liệu nâng cao
Kết quả
Tìm tấc cả nút có khoảng cách nhất định đối với nút cho trước
Sử dụng phương thước withinCost() của 0>36 29
HVTH: Nguyễn Ngọc Diễm Trang: 23
DD<2010>32029133?23+
0>36000C07
003C+7
2913C%7
*01HI01C
0>36 29.20913&000500352913(7
DD0142901
0.30.202&EEG01.2901GE2029133?23O
G003GE220>36EG000.90&((7
?3&20CJ7B01.29017GG(
P
*0101C01HI7
0.30.202&E23EG01.9023&(.90&(GE50130EG
01.90#30&((7
Q
%2029133?23+220>36
23M50130,.J
23R50130,.M
DD<2230100123:03'=3020=?323%
0>36000C07
003C%7
A#30C'7
*01HI01C
0>36 29.>012#30&00050035A#30(7
DD0142901
0.30.202&EEG01.2901GE23?323E
G003GE220>36EG000.90&(G
E>012303?EGA#30GEFE(7
?3&20CJ7B01.29017GG(
P
*0101C01HI7
0.30.202&E23EG01.9023&(.90&(G
E50130EG01.90#30&((7
Q
Báo cáo chuyên đề cơ sở dữ liệu nâng cao
Kết quả trả về :
Tìm cây bao trùm có chi phí cực tiểu.
Kết quả là :
Cây bao trùm tìm được là :
HVTH: Nguyễn Ngọc Diễm Trang: 24
+23?323%220>36>012303?'.JF
23,50130,.J
23'50130%.J
23N50130'.J
23R50130'.J
DD#3001 22229#30
0>3600C0>36 29.0&0(7
DD200142920>36
0.30.202&E3FEG00.903?3&((7
0.30.202&E26FEG00.903?26&((7
DD #20>3626
26HI26C00.9026&(7
30#30CJ7
?3&20CJ7B26.29017GG(P
0.30.202&E26EG26HI.90&(GEK0E
G26HI.90&(GEK0E
G26HI.90#30&((7
0#30C0#30G26HI.90#30&(7
Q
0.30.202&E3030FK0K0EG0#30(7
3FL
26FS
26%%%.J
26++,.J
26SS,.M
26LL,.J
26,,,.J
26'',.J
26,J,J,.J
26MM,.J
3030FL.M
Báo cáo chuyên đề cơ sở dữ liệu nâng cao
Tìm tấc cả những đường dẫn giữa hai nút cho trước.
Ta sử dụng phương thức allPaths() của class NetworkManager để trả về danh sách các
đường dẫn. Tuy nhiên, kết quả này có thể rất lớn đối với những đồ thị dữ liệu lớn.Do đó,
để hạn chế lại điều này, việc tìm kiếm danh sách đường dẫn sẽ phụ thuộc vào các yếu tố
sau:
- Số link liên kết : chỉ trả về kết quả có số link trong đường dẫn nhỏ hơn hoặc bằng
số link liên kết cho trước.
- Chi phí : chỉ trả về kết quả có tổng chi phí nhỏ hơn hoặc bằng chi phí cho trước.
- Số giải pháp : chỉ trả về số lượng kết quả tối ưu nhất nhỏ hơn hoặc bằng số giải
pháp cho trước
HVTH: Nguyễn Ngọc Diễm Trang: 25
DD-0010>223'2+
A01C,JJJ7
A#30C,JJJ7
A3432C,JJJ7
*01HI01C
0>36 29.*01&05'5+5A015A#305A3432(77
DD013432?32
?3&20CJ7B01.29017GG(
P
*01C01HI7
20226C.903?26&(7
330C.90#30&(7
0.30.202&E01HEGGEI26FEG226GE50130EG30(7
Q
