Хранение графа в SQLite - реляционный или плоский?
Эта проблема
Мне нужно хранить ориентированный граф в базе данных sqlite, и мне интересно, как это решить.
Моим первым решением было создать две таблицы, одну для узлов и одну для ребер, однако я не удовлетворен производительностью вставки по сравнению с нереляционной моделью проблемы.
Для типичного графа из 100 тыс. Узлов, каждый из которых имеет 50 исходящих ребер, для вставки в реляционную модель требуется ~20 с против 7 с использованием плоского подхода.
Актуальный вопрос
- Могу ли я что-нибудь сделать, чтобы ускорить процесс вставки графа в базу данных с помощью реляционной модели?
- Я использую API SQLite неоптимальным способом?
- Стоит ли даже рассматривать реляционный подход, учитывая, что он не обязателен, только "хорош"?
Дополнительная информация
Я написал два примера, чтобы продемонстрировать мою проблему:
Реляционный подход
public sealed class RelationalGraphDatabase
: IDatabase
{
private readonly SQLiteConnection _connection;
public RelationalGraphDatabase()
{
const string fname = @"E:\relational_graph.db";
if (File.Exists(fname))
File.Delete(fname);
var conn = new SQLiteConnectionStringBuilder
{
DataSource = fname
};
_connection = new SQLiteConnection(conn.ToString());
_connection.Open();
using (
var command = new SQLiteCommand("CREATE TABLE Node (Id INTEGER PRIMARY KEY, Name TEXT)", _connection))
{
command.ExecuteNonQuery();
}
using (
var command =
new SQLiteCommand(
"CREATE TABLE Edges (Node_From INTEGER NOT NULL, Node_To INTEGER, P1 INTEGER NOT NULL, P2 INTEGER NOT NULL, P3 INTEGER NOT NULL, P4 INTEGER NOT NULL)",
_connection))
{
command.ExecuteNonQuery();
}
}
public void Commit(IEnumerable<Node> values)
{
using (SQLiteTransaction transaction = _connection.BeginTransaction())
{
using (var command = new SQLiteCommand("INSERT INTO Node (Id, Name) VALUES (@Id, @Name)", _connection))
{
command.Parameters.Add("@Id", DbType.Int64);
command.Parameters.Add("@Name", DbType.String);
foreach (Node bts in values)
{
command.Parameters[0].Value = bts.Id;
command.Parameters[1].Value = bts.Name;
command.ExecuteNonQuery();
}
}
using (
var command =
new SQLiteCommand("INSERT INTO Edges (Node_From, Node_To, P1, P2, P3, P4) VALUES (@From, @To, @P1, @P2, @P3, @P4)",
_connection))
{
command.Parameters.Add("@From", DbType.Int64);
command.Parameters.Add("@To", DbType.Int64);
command.Parameters.Add("@P1", DbType.UInt16);
command.Parameters.Add("@P2", DbType.UInt16);
command.Parameters.Add("@P3", DbType.UInt16);
command.Parameters.Add("@P4", DbType.UInt16);
foreach (Node bts in values)
{
foreach (NodeId neighbour in bts.Edges)
{
command.Parameters[0].Value = (long) bts.Id;
command.Parameters[1].Value = null;
command.Parameters[2].Value = neighbour.P1;
command.Parameters[3].Value = neighbour.P2;
command.Parameters[4].Value = neighbour.P3;
command.Parameters[5].Value = neighbour.P4;
command.ExecuteNonQuery();
}
}
}
transaction.Commit();
}
}
public IEnumerable<Node> Select()
{
var ret = new Dictionary<uint, Node>();
using (var command = new SQLiteCommand("SELECT * FROM Node", _connection))
{
using (SQLiteDataReader reader = command.ExecuteReader())
{
while (reader.Read())
{
var bts = new Node
{
Id = (uint) reader.GetInt64(0),
Name = reader.GetString(1),
Edges = new List<NodeId>()
};
ret.Add(bts.Id, bts);
}
}
}
string sql = string.Format("SELECT * FROM Edges WHERE Node_From IN ({0})", string.Join(", ", ret.Keys));
using (var command = new SQLiteCommand(sql, _connection))
{
using (SQLiteDataReader reader = command.ExecuteReader())
{
while (reader.Read())
{
var id = (uint) reader.GetInt64(0);
int mcc = reader.GetInt32(2);
int mnc = reader.GetInt32(3);
int lac = reader.GetInt32(4);
int ci = reader.GetInt32(5);
ret[id].Edges.Add(new NodeId
{
P1 = (ushort) mcc,
P2 = (ushort) mnc,
P3 = (ushort) lac,
P4 = (ushort) ci
});
}
}
}
return ret.Values.ToList();
}
public void Dispose()
{
_connection.Dispose();
}
}
Плоский подход
public sealed class FlatGraphDatabase
: IDatabase
{
private readonly SQLiteConnection _connection;
public FlatGraphDatabase()
{
const string fname = @"E:\flat_graph.db";
if (File.Exists(fname))
File.Delete(fname);
var conn = new SQLiteConnectionStringBuilder
{
DataSource = fname
};
_connection = new SQLiteConnection(conn.ToString());
_connection.Open();
using (
var command = new SQLiteCommand("CREATE TABLE Node (Id INTEGER PRIMARY KEY, Name TEXT, Edges TEXT)", _connection))
{
command.ExecuteNonQuery();
}
}
public void Commit(IEnumerable<Node> values)
{
using (var transaction = _connection.BeginTransaction())
using (var command = new SQLiteCommand("INSERT INTO Node (Id, Name, Edges) VALUES (@Id, @Name, @Edges)", _connection))
{
command.Parameters.Add("@Id", DbType.Int64);
command.Parameters.Add("@Name", DbType.String);
command.Parameters.Add("@Edges", DbType.String);
foreach (var bts in values)
{
command.Parameters[0].Value = bts.Id;
command.Parameters[1].Value = bts.Name;
command.Parameters[2].Value = string.Join(",", bts.Edges);
command.ExecuteNonQuery();
}
transaction.Commit();
}
}
public IEnumerable<Node> Select()
{
var ret = new List<Node>();
using (var command = new SQLiteCommand("SELECT * FROM Node", _connection))
{
using (var reader = command.ExecuteReader())
{
while (reader.Read())
{
var bts = new Node
{
Id = (uint) reader.GetInt64(0),
Name = reader.GetString(1),
Edges = reader.GetString(2).Split(',').Select(NodeId.Parse).ToList()
};
ret.Add(bts);
}
}
}
return ret;
}
public void Dispose()
{
_connection.Dispose();
}
}
Спасибо за ваше время заранее:)