Algorithms and implementation of object-oriented constraint databases

Constraints provide a flexible and uniform way to represent diverse data capturing spatio-temporal behavior, complex modeling requirements, partial and incomplete information etc. Constraint databases integrate data captured by constraints in databases. This dissertation presents a threefold contribution to the area of constraint databases.; The first part is the development of an object-oriented constraint database system, CCUBE. CCUBE is designed for directly building constraint database applications, as well as for the implementation and optimization of high-level constraint object-oriented query languages. The CCUBE data manipulation language is an integration of constraint objects within monoid comprehensions, which serve as an optimization-level language for object queries. The focal point is achieving the right balance between the expressiveness, complexity and representation usefulness, without which the practical use of the system would not be possible. To that end, CCUBE constraint calculus guarantees polynomial time data complexity, and is tightly integrated with the monoid comprehensions to allow interleaved global optimization. This dissertation describes system design and its implementation on top of C++.; The second part is the study of how the CCUBE constraint database technology can be used for the Earth Observing System Data Information System. A number of typical content-browsing queries are expressed using the CCUBE query language, and run on real data sets. It is demonstrated that CCUBE provides savings in development time by allowing complex queries to be answered without a considerable programming effort.; The third part is devoted to the problem of evaluation of a conjunction of N disjunctions of linear constraints in R d (constraint join), which is a common constraint database operation. Existing methods are exponential in N. Combinatorial geometry methods are applied to establish conditions for a polynomial size of the join output. A polynomial method to compute a join for an arbitrary input is then given. As part of the solution, a new algorithm for convex decomposition of an arbitrary non-convex polyhedron is developed. The H-tree is proposed—a new data structure combining constraint storage and indexing. H-tree and R-tree implementations of the algorithm are given, and analytical considerations regarding the performance are provided.