Hi, are you sure you want to go that deep? :-) https://en.wikipedia.org/wiki/Constraint_satisfaction_problem https://en.wikipedia.org/wiki/2-satisfiability (an example what quite a small change in constraints can change the picture dramatically: once we moved from 3SAT to 2SAT - it is polynomial). https://www.cs.ox.ac.uk/activities/constraints/publications/ComplexityLanguages.pdf
Regards, Dmitry On Tue, 18 Feb 2025 at 19:56, Štefan Miklošovič <smikloso...@apache.org> wrote: > Sorry, CEP-42 > > On Tue, Feb 18, 2025 at 8:54 PM Štefan Miklošovič <smikloso...@apache.org> > wrote: > >> Hi list, >> >> We are doing good progress together with Bernardo when it comes to >> constraints which were merged recently (CEP-24). >> >> What I do now is that I try to "harden" it a little bit. If you think >> about that, a user could do something like this (currently) >> >> ALTER TABLE ks.tb ALTER column1 CHECK column1 > 10 AND column1 < 5 >> >> If you take a look at this, this constraint is not satisfiable. There is >> no such value for "column1" which would pass both checks. That means that >> whatever a user would try to put there, such an insertion would fail. >> >> I have a POC which covers the most obvious cases so it fails when a >> constraint is obviously not satisfiable, so we are not storing a check >> which is impossible to pass. >> >> However, we are not completely sure how far we should go with this. >> >> The problem here is that, in theory, we could also support OR, for example >> >> ALTER TABLE ks.tb ALTER column1 CHECK (column1 > 5 AND column < 10) OR >> (column1 > 1000) >> >> You got it. >> >> The problem with this is that, when it is generalized, I can not check if >> this is satisfiable, because this is basically a variation of SAT problem, >> which is ... NP-complete. Right? In its most general form, is not this a >> NP-complete problem? Or am I wrong? >> >> I do not think that we are going to solve NP-completeness of SAT here :D >> so I just want to make sure that we are on the same page when it comes to >> this and all we will ever support is just a simple AND (that is complicated >> enough to verify if it is satisfiable already). >> >> What do you think about this? Is this all OK for you? >> >> Regards >> >> (1) https://en.wikipedia.org/wiki/Boolean_satisfiability_problem >> > -- Dmitry Konstantinov
