make child a unique key. so each node can only have 1 parent.
On Sun, Dec 24, 2017 at 6:44 AM, Lifepillar <lifepil...@lifepillar.me> wrote: > On 24/12/2017 11:56, Shane Dev wrote: > >> Related to my previous question >> https://www.mail-archive.com/sqlite-users@mailinglists.sqlit >> e.org/msg107527.html, >> I want to prevent the client from inserting a cycle. >> >> For example - >> >> sqlite> .sch edges >> CREATE TABLE edges(parent integer not null, child integer not null, >> constraint self_reference check (parent<>child)); >> >> sqlite> select * from edges; >> parent child >> 1 2 >> 1 3 >> 2 4 >> >> insert into edges select 2, 5; -- ok >> insert into edges select 2, 1; -- should not be allowed. >> insert into edges select 4, 1; -- should not be allowed. >> >> Many kinds of insertions can be prevented using triggers. Existing cycles >> can be detected using a recurisve common table expression. However, since >> CTEs are not supported inside triggers, I assume they can't be used for >> this purpose. Is there another way? >> > > You may define a custom function that, given an edge (u,v) to be added > to the Edges table, checks whether there is a path from v to u in Edges: > > static void > cyclesFunc(sqlite3_context* context, int argc, sqlite3_value** argv) { > char query[] = "with recursive Nodes(n) as (" > " select ?2" > " union" > " select child" > " from Nodes" > " join Edges" > " on parent = n" > ")" > "select count(*) from Nodes where n = ?1"; > sqlite3* db = sqlite3_context_db_handle(context); > sqlite3_stmt* stmt; > sqlite3_prepare_v2(db, query, (int)strlen(query), &stmt, 0); > int v1 = sqlite3_value_int(argv[0]); > int v2 = sqlite3_value_int(argv[1]); > sqlite3_bind_int(stmt, 1, v1); > sqlite3_bind_int(stmt, 2, v2); > int retVal = sqlite3_step(stmt); > if (retVal != SQLITE_ROW) > fprintf(stderr, "Error %d\n", retVal); > int count = sqlite3_column_int(stmt, 0); > retVal = sqlite3_step(stmt); > if (retVal != SQLITE_DONE) > fprintf(stderr, "Commit failed: error %d\n", retVal); > sqlite3_finalize(stmt); > sqlite3_result_int(context, count > 0); > } > // ... > rc = sqlite3_create_function(db, "cycles", 2, > SQLITE_UTF8 SQLITE_DETERMINISTIC, 0, cyclesFunc, 0, 0); > > The function returns 1 if adding the edge introduces a cycle, and 0 > otherwise. For example: > > .load ./cycles > create table Edges(parent int, child int, primary key (parent,child)); > select cycles(1,1); -- 1 > select cycles(1,2); -- 0 > insert into Edges(parent,child) values (1,2), (2,3); > select cycles(3,1); -- 1 > select cycles(1,3); -- 0 > > I think you can use this function in a before/instead of trigger, but > I haven't tried. > > Life. > > > _______________________________________________ > sqlite-users mailing list > sqlite-users@mailinglists.sqlite.org > http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users > _______________________________________________ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users