How to prevent the insertion of cycles into a hierarchical table?

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

How to prevent the insertion of cycles into a hierarchical table?

Shane Dev
Related to my previous question
https://www.mail-archive.com/sqlite-users@.../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?
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: How to prevent the insertion of cycles into a hierarchical table?

Lifepillar
On 24/12/2017 11:56, Shane Dev wrote:

> Related to my previous question
> https://www.mail-archive.com/sqlite-users@.../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
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: How to prevent the insertion of cycles into a hierarchical table?

J Decker
make child a unique key.  so each node can only have 1 parent.



On Sun, Dec 24, 2017 at 6:44 AM, Lifepillar <[hidden email]>
wrote:

> On 24/12/2017 11:56, Shane Dev wrote:
>
>> Related to my previous question
>> https://www.mail-archive.com/sqlite-users@...
>> 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
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: How to prevent the insertion of cycles into a hierarchical table?

E.Pasma
On 24/12/2017 11:56, Shane Dev wrote:

> Related to my previous question
> https://www.mail-archive.com/sqlite-users@...
> 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?
>


Sorry for ignoring the two earlier repiies, but it looks that WITH can  
be used inside triggers. Like

create trigger ins_edges before insert on edges
begin
     with recursive r as (
         select  new.child
         union all
         select  edges.child
         from    r
         join    edges on edges.parent=r.child
             )
     select raise (FAIL, 'example error')
     from    r where child=new.parent;
end
;



_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: How to prevent the insertion of cycles into a hierarchical table?

Shane Dev
Thanks for the wonderfully simple and concise solution. I see now triggers
do support CTEs if they SELECT a RAISE() function. I never thought of using
a BEFORE trigger.

Fijne kerstdagen

On 24 December 2017 at 17:17, E.Pasma <[hidden email]> wrote:

> On 24/12/2017 11:56, Shane Dev wrote:
>
> Related to my previous question
>> https://www.mail-archive.com/sqlite-users@...
>> 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?
>>
>>
>
> Sorry for ignoring the two earlier repiies, but it looks that WITH can be
> used inside triggers. Like
>
> create trigger ins_edges before insert on edges
> begin
>     with recursive r as (
>         select  new.child
>         union all
>         select  edges.child
>         from    r
>         join    edges on edges.parent=r.child
>             )
>     select raise (FAIL, 'example error')
>     from    r where child=new.parent;
> end
> ;
>
>
>
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users