| Constraint databases (CDBs) represent a new database paradigm for application domains that require to support large heterogeneous data that can be uniformly captured by constraints, including geographic information systems, mechanical engineering systems, manufacturing and warehouse control. This dissertation addresses two research issues in the context of constraint databases: (1) constraint algebras, and (2) constraint optimization languages supporting combinatorial optimization and search in the presence of large amounts of data. The main contributions of this dissertation are twofold.; The first contribution is the development of a multi-typed linear constraint algebra in the CCUBE Constraint Object-Oriented Database System. The designed multi-typed linear constraint algebra achieves a careful balance among expressiveness, computational complexity and representation usefulness, a major problem on previous researches. The data model for this multi-typed linear constraint algebra is based on constraint spatio-temporal (CST) objects that may hold spatial, temporal or constraint data, conceptually represented by constraints. To represent CST objects in the CCUBE constraint data model, first-order CST formulae are introduced as a convenient variant of first-order formulae. The multi-typed linear constraint algebra consists of eight interrelated linear constraint families, each representing a sub-family of first-order CST formulae, and guarantees polynomial time data complexity. Canonical forms for the CST families and the types of simplifications performed in the canonical forms are also defined. The multi-typed linear constraint algebra is implemented as a C++ library in CCUBE.; The second contribution is the development of the LAJIO constraint optimization language designed for combinatorial optimization and search in the presence of large amounts of data. To bridge the research gap between current constraint programming technology and database technology, the language is aimed at integrating object-oriented database query languages and constraint programming optimization languages into a cohesive framework. To this end, it is not only a database query language, but also has the ability to specify search procedures and combine different search strategies to guide searches in solving combinatorial optimization and search problems. This combined language uses constraint programming optimization constructs to support both systematic and stochastic searches. Constraint manipulation techniques are used to extract explicit constraints, and most importantly, database indexing techniques are utilized to efficiently filter and prune large search spaces. |
