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

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


--- news://freenews.netfront.net/ - complaints: news_at_netfront.net ---