Can I create a column constraint that prevents 2 values where one is a prefix of another? So 'abc' and 'abd' can both be in the table, but not 'abc' and 'ab'.

A similar question for PostgreSQL was asked here: https://stackoverflow.com/questions/44685013/postgresql-constraint-using-prefixes but the answers all use PostgreSQL functions.

SQLite CHECK constraints can't refer to other rows (since they don't permit subqueries). You might be able to simulate things with AFTER triggers?

A before trigger is the correct way of doing it, once you figure out how to actually identify that a candidate record SHOULD NOT be inserted.

In the example you gave, the 'abc' and 'ab' is not adequately described.

Lets say 'abc' is added first and has been added to the table.

Now you want to add 'ab'.

What is the test you execute in order to determine that the addition of 'ab' should be rejected? (test 1)

On the other hand, lets say 'ab' is added first to the table.

Now you want to add 'abc'.

What test do you execute in order to determine that the addition of 'abc' should be rejected? (test 2)

Obviously both test 1 and test 2 must indicate that the new record must not be added (otherwise your "but not 'abc' and 'ab'" is violated).

When you get down to it, order of insertion will be important and deterministic of what is allowed to be successfully inserted.

So, of the two datums 'abc' and 'ab', you want to only be able to successfully insert the whichever, by happenstance, is first and reject the other -- making the database content dependent on insertion order (non-deterministic).

Once you have devised the test you want to use then it is simply a matter of:

create trigger ProhibitInsert before insert on t
begin
  select raise(ABORT, 'Cannot Insert Ill-formed Record')
   where ... record should not be inserted test ...;
end;

Something like the following:

sqlite> create table x
   ...> (
   ...>     item    text not null collate nocase
   ...> );
sqlite> create index x_item on x(item);
sqlite>
sqlite> create trigger x_bi_prohibit before insert on x
   ...> begin
   ...>      select raise(ABORT, 'Cannot insert substring of existing item')
   ...>       where (
   ...>              select 1
   ...>                from x
   ...>               where item like (new.item || '%')
                      limit 1
   ...>             );
   ...>      with lens(i) as
   ...>           (
   ...>               select 1
   ...>            union all
   ...>               select i + 1
   ...>                 from lens
   ...>                where i < length(new.item)
   ...>           ),
   ...>           hits(x) as
   ...>           (
   ...>            select 1
   ...>              from lens, x
   ...>             where item like (substr(new.item, 1, i) || '%')
                     limit 1
   ...>           )
   ...>      select raise(ABORT, 'Cannot insert superstring of existing item')
   ...>       where (select count() from hits);
   ...> end;
sqlite>
sqlite> insert into x values ('abc');
sqlite> insert into x values ('ab');
Runtime error: Cannot insert substring of existing item (19)
sqlite> delete from x;
sqlite> insert into x values ('ab');
sqlite> insert into x values ('abc');
Runtime error: Cannot insert superstring of existing item (19)

This is a case-insensitive version. LIKE must be case insensitive. The column definition includes COLLATE NOCASE. If you want it to be case sensitive then you must switch LIKE to case-sensitive mode and get rid of the COLLATE NOCASE.

In any event, you MUST NOT "diddle about" with any inconsistent setting (LIKE case-sensitivity and collation sensitivity -- if you do not keep them identical at all times then madness is likely to ensue).

NOTE Added the "limit 1" and changed max(x) to count() -- all because there is no point to finding more than 1 failure -- 1 is sufficient. Also changed the substring limits to 1 (2 is incorrect).

Note that for the case sensitive implementation (where you change the case sensitivity of LIKE) you have to have trusted_schema=1 otherwise the parser whines ...

sqlite> pragma trusted_schema=1;
sqlite> pragma case_sensitive_like=1;
sqlite> create table x
   ...> (
   ...>     item    text not null
   ...> );
sqlite> create index x_item on x(item);
sqlite>
sqlite> create trigger x_bi_prohibit before insert on x
   ...> begin
   ...>      select raise(ABORT, 'Cannot insert substring of existing item')
   ...>       where (
   ...>              select 1
   ...>                from x
   ...>               where item like (new.item || '%')
                       limit 1
   ...>             );
   ...>      with lens(i) as
   ...>           (
   ...>               select 1
   ...>            union all
   ...>               select i + 1
   ...>                 from lens
   ...>                where i < length(new.item)
   ...>           ),
   ...>           hits(x) as
   ...>           (
   ...>            select 1
   ...>              from lens, x
   ...>             where item like (substr(new.item, 1, i) || '%')
                    limit 1
   ...>           )
   ...>      select raise(ABORT, 'Cannot insert superstring of existing item')
   ...>       where (select count(*) from hits);
   ...> end;
sqlite>
sqlite> insert into x values ('abc');
sqlite> insert into x values ('ab');
Runtime error: Cannot insert substring of existing item (19)
sqlite> delete from x;
sqlite> insert into x values ('ab');
sqlite> insert into x values ('abc');
Runtime error: Cannot insert superstring of existing item (19)
sqlite> insert into x values ('AbC');

NOTE Added the "limit 1" and changed max(x) to count() -- all because there is no point to finding more than 1 failure -- 1 is sufficient. Also changed the substring limits to 1 (2 is incorrect).

This version works with a case sensitive comparison by forcing the creation and use of a case insensitive index so that "like" may choose case insensitive candidates which are then culled (by doing a case sensitive compare). It will work without changing the case_sensitive_like pragma (if you use pragma case_sensitive_like=... on a connection then that connection will no longer be able to insert into x).

sqlite> create table x
   ...> (
   ...>     item    text not null
   ...> );
sqlite> create index x_item_nocase on x(item collate nocase);
sqlite>
sqlite> create trigger x_bi_prohibit before insert on x
   ...> begin
   ...>      select raise(ABORT, 'Cannot insert substring of existing item')
   ...>       where (
   ...>              select 1
   ...>                from (
   ...>                      select rowid as candidate
   ...>                        from x indexed by x_item_nocase
   ...>                       where item like (new.item || '%')
   ...>                     ) as candidates
   ...>                join x
   ...>                  on x.rowid == candidates.candidate
   ...>               where substring(item, 1, length(new.item)) == new.item
   ...>             );
   ...>      with lens(i) as
   ...>           (
   ...>               select 1
   ...>            union all
   ...>               select i + 1
   ...>                 from lens
   ...>                where i < length(new.item)
   ...>           ),
   ...>           hits as
   ...>           (
   ...>            select item, new.item
   ...>              from (
   ...>                    select rowid as candidate,
   ...>                           i
   ...>                      from lens,
   ...>                           x indexed by x_item_nocase
   ...>                     where item like (substr(new.item, 1, i) || '%')
   ...>                   ) as candidates
   ...>              join x
   ...>                on x.rowid == candidates.candidate
   ...>             where item == substring(new.item, 1, i)
   ...>           )
   ...>      select raise(ABORT, 'Cannot insert superstring of existing item')
   ...>       where (
   ...>              select count()
   ...>                from hits
   ...>             );
   ...> end;
sqlite>
sqlite> insert into x values ('abc');
sqlite> insert into x values ('ab');
Runtime error: Cannot insert substring of existing item (19)
sqlite> delete from x;
sqlite> insert into x values ('ab');
sqlite> insert into x values ('abc');
Runtime error: Cannot insert superstring of existing item (19)
sqlite> insert into x values ('AbC');
sqlite> insert into x values ('Ab');
Runtime error: Cannot insert substring of existing item (19)
sqlite> insert into x values ('ABc');
sqlite>
sqlite>

Note that you must ensure pragma case_sensitive_like=0 and pragma trusted_schema=1 if you "fiddle" the case_sensitive_like setting before insert into x will work again on a connection.

The docs say:

• Common table expression are not supported for statements inside of triggers.

If your sample code runs as indicated, there's an implementation/documentation mismatch.

The following eliminates CTE's but requires the generate_series extension. I believe that the problem with CTE's affects recursion, however, this bypasses that by not using CTE's (whether recursive or not).

create table x
(
    item    text not null
);
create index x_item_nocase on x(item collate nocase);

create trigger x_bi_prohibit before insert on x
begin
     select raise(ABORT, 'Cannot insert substring of existing item')
      where exists (
                    select *
                      from (
                            select rowid as candidate
                              from x indexed by x_item_nocase
                             where item like (new.item || '%')
                           ) as candidates
                      join x
                        on x.rowid == candidates.candidate
                     where substring(item, 1, length(new.item)) == new.item
                   );
     select raise(ABORT, 'Cannot insert superstring of existing item')
      where exists (
                    select *
                      from (
                            select x.rowid as candidate,
                                   value
                              from generate_series,
                                   x indexed by x_item_nocase
                             where item like (substr(new.item, 1, value) || '%')
                               and start = 1
                               and stop = length(new.item)
                           ) as candidates
                      join x
                        on x.rowid == candidates.candidate
                     where item == substring(new.item, 1, value)
                   );
end;

insert into x values ('abc');
insert into x values ('ab');
delete from x;
insert into x values ('ab');
insert into x values ('abc');
insert into x values ('AbC');
insert into x values ('Ab');
insert into x values ('ABc');

Note that "not supported" IS DISTINCT FROM "does not work".

You are, however, correct. recursive CTE's "does not work" inside a trigger, whereas non-recursive CTE's work just dandy. The recursive CTE will fail for prefixes greater than 2. You will see that if you add a more full set of test data.

What is unsupported is that there is no support (ie, guarantee) that a CTE, if used in a trigger, will function as expected, and if it does or does not, that is the users problem (the author has already stated a caveat that CTE's (with statements) may not function inside a trigger the same way that it does outside of a trigger and that if you discover this fact, that is jolly good on you, but will generate no more than a "see, told ya so" from the author).

NOT SUPPORTED does not imply DOES NOT WORK
DOES NOT WORK does not imply SUPPORTED nor NOT SUPPORTED

The expression "undefined" usually does not mean undefined. It usually means that the definition is beyond the scope of the recipients understanding.

I don't think this can be optimized any more ...

-- case sensitive
create table x
(
    item    text not null
);
create index x_item_nocase on x(item collate nocase);
create index x_item_case on x(item);

create trigger x_bi_prohibit before insert on x
begin
     select raise(ABORT, 'Cannot insert substring of existing item')
      where exists (
                    select *
                      from (
                            select rowid as candidate
                              from x indexed by x_item_nocase
                             where item like (new.item || '%')
                           ) as candidates
                      join x
                        on x.rowid == candidates.candidate
                     where substring(item, 1, length(new.item)) == new.item
                   );
     select raise(ABORT, 'Cannot insert superstring of existing item')
      where exists (
                    select *
                      from generate_series,
                           x indexed by x_item_case
                     where item == substr(new.item, 1, value)
                       and start = 1
                       and stop = length(new.item)
                   );
end;

-- case insensitive
create table x
(
    item    text not null collate nocase
);
create index x_item_nocase on x(item collate nocase);

create trigger x_bi_prohibit before insert on x
begin
     select raise(ABORT, 'Cannot insert substring of existing item')
      where exists (
                    select *
                      from x indexed by x_item_nocase
                     where item like (new.item || '%')
                   );
     select raise(ABORT, 'Cannot insert superstring of existing item')
      where exists (
                    select *
                      from generate_series,
                           x indexed by x_item_nocase
                     where item == substr(new.item, 1, value) collate nocase
                       and start = 1
                       and stop = length(new.item)
                   );
end;

If at least one of the existing items has the candidate as a prefix, the smallest item greater than the candidate must be one of them. So you don't need LIKE at all, which means you don't have to worry about what collation LIKE uses.

create table x(
    item text
        collate nocase  -- the code below works with any collation or none at all
        unique          -- might as well create the index right here
);

create trigger x_noprefix_insert
    before insert on x
begin
    select raise(ABORT, 'Prefix constraint failed: x.item')
        where new.item=
            (select substr(item, 1, length(new.item)) from x
                where item>new.item
                order by item);
    select raise(ABORT, 'Prefix constraint failed: x.item')
        from generate_series(1, length(new.item)),
            x on item=substr(new.item, 1, value);
end;

create trigger x_noprefix_update
    before update of item on x
begin
    select raise(ABORT, 'Prefix constraint failed: x.item')
        where new.item=
            (select substr(item, 1, length(new.item)) from x
                where item>new.item
                    and item!=old.item
                order by item);
    select raise(ABORT, 'Prefix constraint failed: x.item')
        from generate_series(1, length(new.item)),
            x on item=substr(new.item, 1, value)
        where item!=old.item;
end;

Brilliant!

Also, I see no way you can get the LIKE optimization to kick in for this problem, so using LIKE gives you a full scan instead of a search. Ouch.

Parse error near line 3: near "case": syntax error
   on table1 for each row begin select raise(abort, case when length(new.field1)
                                      error here ---^

You may have missed that the code in post 12 does no scans (as long as there's an appropriate index).

It does one greater-than search and length(new.item) equal-to searches for each insert.

I did miss that. My apologies.

So you're saying "If this is a prefix, then the next thing in order will be something it is a prefix of." ...which uses that weird SQLite quirk that you don't have to put "limit 1" on the sub-query and it'll still just produce 1 item. Which always confuses me as I'm used to Postgres requiring the subquery to not produce multiple items. So when reading it quick I think my mind processed it as "that's gonna run through half the table"

So my bad. Can confirm that's a brilliant solution of yours there.

Since we can't get the LIKE optimization

Why can't you get the like optimization? My code does so.

Is it a wattage problem?

THe like optimization works just fine and my sample codee with LIKE uses the index. Otherwise, why would I have bothered to create it? Also note that the code REQUIRES the use of the appropriate index during the LIKE processing, otherwise the planner will throw an error. You can also simply turn on eqp if you want to look at the generated code -- which may be perspicacious rather than making assumptions.

I did in fact use the shell's most excellent .eqp trigger command to examine what the optimizer made of the various triggers suggested in this thread, and post 14 is informed by my findings.

Can you say the same for post 20?

You are either (a) mistaken or (b) are using some prior version of SQLite3 (prior to the current release) in which a bug exists in the implementation of the LIKE optimization that has been subsequently fixed. That is because if I do the same thing (which I had done all along) your "findings" are incorrect.

sqlite> create table x
   ...> (
   ...>     item    text not null
   ...> );
sqlite> create index x_item_nocase on x(item collate nocase);
sqlite> create index x_item_case on x(item);
sqlite>
sqlite> create trigger x_bi_prohibit before insert on x
   ...> begin
   ...>      select raise(ABORT, 'Cannot insert substring of existing item')
   ...>       where exists (
   ...>                     select *
   ...>                       from (
   ...>                             select rowid as candidate
   ...>                               from x indexed by x_item_nocase
   ...>                              where item like (new.item || '%')
   ...>                            ) as candidates
   ...>                       join x
   ...>                         on x.rowid == candidates.candidate
   ...>                      where substring(item, 1, length(new.item)) == new.item
   ...>                    );
   ...>      select raise(ABORT, 'Cannot insert superstring of existing item')
   ...>       where exists (
   ...>                     select *
   ...>                       from generate_series,
   ...>                            x indexed by x_item_case
   ...>                      where item == substr(new.item, 1, value)
   ...>                        and start = 1
   ...>                        and stop = length(new.item)
   ...>                    );
   ...> end;
sqlite> .eqp trigger
sqlite> insert into x values ('a');
TRIGGER x_bi_prohibit
|--SCAN x USING COVERING INDEX x_item_nocase (~983040 rows)
|--SEARCH x USING INTEGER PRIMARY KEY (rowid=?) (~1 row)
|--SCAN generate_series VIRTUAL TABLE INDEX 3: (~960 rows)
`--SEARCH x USING COVERING INDEX x_item_case (item=?) (~10 rows)
sqlite>

You will see that ALL operations, without exception, are using either a covering index or the rowid index (except for generate_series which does not have an index).

You should note that the LIKE optimization takes place after prepare on the re-examination after the bindings are set, so even if the usage of the index were not explicitly forced, it would still be used anyway (although you would not know this unless you asked for ".eqp full" since the initial plan would not use an index because that optimization cannot be determined until after the bindings are known (ie, at execution time, not prepare time).

    SQLite version 3.39.0 2022-06-25 14:57:57
    Enter ".help" for usage hints.
    sqlite>

Using the table and trigger definitions from the parent post.

Firstly, let's see what a successful LIKE optimization looks like.

    sqlite> select * from x where item like 'abc%';
    QUERY PLAN
    `--SEARCH x USING COVERING INDEX x_item_nocase (item>? AND item<?)

We get a search with lower and upper bounds.

Secondly, what about GLOB?

    sqlite> select * from x where item glob 'abc*';
    QUERY PLAN
    `--SEARCH x USING COVERING INDEX x_item_case (item>? AND item<?)

GLOB is a case sensitive operation, so it uses the case sensitive index. Otherwise, it's identical to LIKE.

Thirdly, let's force GLOB to use the wrong index.

    sqlite> select * from x indexed by x_item_nocase where item glob 'abc*';
    QUERY PLAN
    `--SCAN x USING COVERING INDEX x_item_nocase

It says SCAN x instead of SEARCH x, so we didn't get any optimization. It does use the specified index, but as a data source rather than for searching.

Fourthly, there are other ways to prevent optimization.

    sqlite> select * from x indexed by x_item_nocase where item like ('abc' || '%');
    QUERY PLAN
    `--SCAN x USING COVERING INDEX x_item_nocase

The right operand of the LIKE should remind you of something.

Finally, let's exercise the trigger.

    sqlite> insert into x values('abc');
    TRIGGER x_bi_prohibit
    |--SCAN x USING COVERING INDEX x_item_nocase
    |--SEARCH x USING INTEGER PRIMARY KEY (rowid=?)
    |--SCAN generate_series VIRTUAL TABLE INDEX 3:
    `--SEARCH x USING COVERING INDEX x_item_case (item=?)

Note that the first step looks like the unoptimized examples (SCAN x) rather than the optimized examples (SEARCH x).

Summary: no optimization here. Full table scan on each insert. Slow.

You are correct, of course. There is no way to know that NONE of the item start with a wildcard, so the planner cannot apply the optimization.

Also, the generate_series(1, length(new.item)) should change to generate_series(1, length(new.item) - 1) so that UNIQUE violations throw a UNIQUE constraint error (otherwise you get a Prefix Constraint error because the new.item matches an existing item, rather than a UNIQUE violation -- if that makes any difference).

Notwithstanding, however, getting rid of LIKE altogether provides the (slight) advantage that you can twiddle the case_sensitive_like setting without affecting the trigger operation. It should also save a millisend or half due to not having to process the comparison, but merely the seek. It will also save the storage space associated with the extra index.