Làm thế nào để duy trì cấu trúc dữ liệu biểu đồ trong cơ sở dữ liệu quan hệ?

Question

Tôi đã xem xét việc tạo bảng Vertices và bảng Edges nhưng sẽ xây dựng biểu đồ trong bộ nhớ và duyệt qua biểu đồ phụ yêu cầu số lượng lớn tra cứu? Tôi muốn tránh đọc cơ sở dữ liệu quá mức. Có cách nào khác để duy trì một biểu đồ?

Lưu ý phụ: Tôi đã nghe nói về Neo4j nhưng câu hỏi của tôi thực sự là cách biểu diễn khái niệm biểu đồ trong cơ sở dữ liệu chuẩn. Tôi đang mở cho một số giải pháp NoSQL như mongodb mặc dù.

Answer 1

Câu trả lời là không may: Việc xem xét của bạn hoàn toàn đúng ở mọi thời điểm. Bạn phải lưu trữ các nút (đỉnh) trong một bảng và các cạnh tham chiếu một mã từ và một nút để chuyển đổi cấu trúc dữ liệu biểu đồ thành cấu trúc dữ liệu quan hệ. Và bạn cũng đúng, điều này kết thúc trong một số lượng lớn tra cứu, bởi vì bạn không thể phân vùng nó thành đồ thị con, có thể được truy vấn cùng một lúc. Bạn phải chuyển từ Node sang Edge sang Node sang Edge sang Node ... và cứ tiếp tục (Recursively, trong khi SQL đang làm việc với Sets).

Vấn đề là ...

Relational, Graph định hướng, định hướng đối tượng, tài liệu dựa trên các loại khác nhau của các cấu trúc dữ liệu mà đáp ứng các yêu cầu khác nhau. Đó là tất cả những gì về nó và tại sao có rất nhiều cơ sở dữ liệu NoSQL khác nhau (hầu hết trong số đó là các kho tài liệu đơn giản) xuất hiện, bởi vì nó đơn giản là không tổ chức dữ liệu lớn một cách quan hệ.

Alternative 1 - Graph cơ sở dữ liệu theo định hướng

Nhưng cũng có cơ sở dữ liệu NoSQL hướng đồ thị, mà làm cho các mô hình dữ liệu đồ thị là một công dân hạng nhất như OrientDB mà tôi đang chơi xung quanh với một chút vào lúc này. Điều tốt đẹp về nó là, mặc dù nó vẫn tồn tại dữ liệu dưới dạng đồ thị, nó vẫn có thể được sử dụng trong một cách định hướng quan hệ hoặc hướng đối tượng hoặc tài liệu cũng (tức là bằng cách truy vấn với SQL cũ đơn giản). Tuy nhiên, Traversing the graph là cách tối ưu để lấy dữ liệu của nó.

Phương án 2 - làm việc với đồ thị trong bộ nhớ

Khi nói đến việc định tuyến nhanh, khuôn khổ định tuyến như Graphhopper xây dựng hoàn chỉnh các đồ thị (tỷ Nodes) bên trong bộ nhớ. Bởi vì Graphhopper sử dụng một MemoryMapped thực hiện của GraphStore của nó, mà thậm chí làm việc trên các thiết bị Android chỉ với một số MB bộ nhớ cần. Biểu đồ hoàn chỉnh được đọc từ cơ sở dữ liệu vào bộ nhớ khi khởi động, và định tuyến được thực hiện ở đó, vì vậy bạn không cần tra cứu cơ sở dữ liệu.

Answer 2

tôi phải đối mặt với vấn đề này cùng và quyết định cuối cùng đi với cấu trúc sau đây, đòi hỏi 2 câu truy vấn cơ sở dữ liệu, sau đó phần còn lại của công việc là trong bộ nhớ:

cửa hàng nút trong một bảng và tham khảo các đồ thị với nhau kỷ lục nút:

Table Nodes 

id | title | graph_id 
--------------------- 
105 | node1 | 2 
106 | node2 | 2 

Cũng lưu trữ cạnh trong bảng khác và một lần nữa tham khảo đồ thị các cạnh thuộc với mỗi cạnh:

Table Edges 

id | from_node_id | to_node_id | graph_id 
----------------------------------------- 
1 | 105   | 106  | 2 
2 | 106   | 105  | 2 

. Nhận tất cả các nút với một truy vấn, sau đó nhận được tất cả các cạnh với nhau.

Bây giờ, hãy tạo cách ưa thích của bạn để lưu trữ biểu đồ (ví dụ: danh sách kề) và tiếp tục với luồng ứng dụng của bạn.