Re: What exactly are "Constraint programming" & "constraint databases" about ?

On Wednesday, January 6, 2016 at 7:52:39 AM UTC-8, Nicola wrote:
> On 2015-12-29 14:16:11 +0000, Erwin said:
>
> > I run into these terms rather frequently, without ever getting/finding
> > a good explanation as to what it's really about.
>
> The idea of constraint databases is simple: a tuple may be viewed as a
> very restrict form of constraint, and a relation instance as a set of
> (simple) constraints. For example:
>
> R
> x y
> ---
> 1 2
> 3 4
>
> may be viewed as a representation of the constraint (x=1 and y=2) or
> (x=3 and y=4). Think of that relation as a set of points in the plane:
> the relation then defines two points.
>
> Now, what if we allow more general constraints, say inequalities (x=1
> and y<2)? It turns out that it is possible to give reasonable
> definitions of generalized tuples and generalized relations
> corresponding to such constraints. The generalized relations are
> possibly infinite (x=1 and y<2 would represent an infinite set of
> points). So, constraint databases are a way to extend the relational
> model to deal with (finitely represented) infinite relations.
>
> The approach is particularly attractive for spatial databases. Consider
> again the Euclidean (2D) plane: an inequality of the form ax + by + c
> <= 0 defines a half-plane. Any convex polygon may be defined as an
> intersection of half-planes, and non-convex polygons as unions of
> convex polygons. Lines and points are degenerate forms of polygons, so
> they also may be represented in the same way. Therefore, points, lines
> and polygons may be all represented as sets of constraints of the form
> ax + by + c <= 0--that is, generalized relations.
>
> Constraint programming is another thing entirely: it deals with solving
> problems that may be modeled via constraints (e.g, find all the ways to
> put eight queens on a chessboard without them being able to capture
> each other). Of course, in constraint databases queries become
> constraint problems, so one may naturally apply constraint programming
> techniques to solve them.
>
> This is maybe not the good explanation you expected, but I hope it is a
> start. Let's try to provoke more posts:
>
> constraint programming : constraint database = relational algebra :
> relational database
>
> Nicola

So suppose you have the following system of constraints:

y^2 -3*y +2 = 0
x*y -x -3*y +3 = 0
x^2 -3*x -2*y +4 = 0

Can you exhibit an algorithm that:
1. Decides if it is a finite set of points 2. Lists the points
(If I remove inequality then the algorithm that does that is doubly exponential. Is there such an algorithm in semi-algebraic case and what its complexity?) Received on Wed Jan 06 2016 - 18:30:47 CET