Dina Q Goldin, Principal Investigator

Mathematics & Computer Science Department
University of Massachusetts / Boston
100 Morrissey Blvd., Boston, MA 02125
Tel : 617-287-6483
Fax : 617-287-6499
email: dqg@cs.umb.edu

http://www.cs.umb.edu/~dqg/cdb/

•      Award Number: IIS-9733678
•      Duration: 05/01/1998 - 04/30/2002
•      Title: Towards Practical Constraint Query Algebras

constraint database, spatiotemporal data, query algebra,  GIS

Constraint Databases (CDBs) are an extension of relational databases that enrich both the relational data model and the relational query primitives with constraints.  For data-intensive applications over non-traditional data, CDBs hold the promise to combine the versatility of constraints with the commercial success of the relational approach.

This project focuses on the internal query representation of CDBs queries, i.e. Constraint Query Algebra (CQA). CQA forms the ``middle layer'' of CDBs, underneath the user interface layer and above the disk access layer, providing a homogenous set of operators for expressing queries over any data. The following challenges related to are addressed, both from a theoretical and a practical perspective, leading to a system we call UMB-CDB:

(1) efficient data representation and algebraic operator implementation,
(2) safe use of additional operators,
(3) query optimization techniques for CQA expressions,
(4) integration with user-friendly metaphores for CDB front end,
(5) flexible interactive data visualization mechanisms

Journal Publications:
 

Dina Goldin, Srinath Srinivasa, Bernhard Thalheim, "Information Systems = Databases + Interaction: Towards Principles of Information System Design", 19th International Conference on Conceptual Modeling, published as Lecture Notes in Computer Science, Vol. 1920, Springer 2000, ISBN 3-540-41072-4, vol. 1920, (2000), p. 140. Published Jan Chomicki, Dina Goldin, Gabriel Kuper, and David Toman, "Variable Independence in Constraint Databases", IEEE Transactions on Knowledge and Data Engineering), Submitted

Book(s) or other one-time publications(s):

Dina Goldin, "Algebraic Constraint Query Languages" , bibl. Springer Verlag, (2000). chapter in a book Published of Collection: L. Libkin, J. Paredaens, G. Kuper, "Constraint Databases"

Dina Goldin, David Keil, "An Interactive Viewpoint on the Role of UML" , bibl. Idea Group Publishing, (2001). Chapter in a book Published of Collection: Keng Siau, Terry Halpin, "Unified Modeling Language: Systems Analysis, Design, and Development Issues"

UMB-CDB is a modular Java-based Constraint Database implementation using Constraint Query Algebras for its query representation, optimization, and evaluation. The homepage for UMB-CDB is http://www.cs.umb.edu/~dqg/cdb/

The description of the system, and the figure showing its architecture, is available in our demo proposal,  at http://www.cs.umb.edu/~dqg/cdb/demo01.ps

The UMB-CDB system is built from the ground up in Java for a PC NT, using the latest JAVA-based system development tools:

SWING - for the CDB-UMB graphical user interface;

JavaCC - for parsing constraints in the interactive data editor;

JNI - Java Native Interface, for binary compatibility across VM implementations;

JTree - for handling the CQA expression trees;

J3D - for the graphical data visualizer;

JNL - linear algebra package, for the query evaluator.

The result is a platform-independent system with a state-of-the-art interactive user-friendly interface. UMB-CDB is meant for the naive user, providing the common metaphors of spreadsheets (and potentially SQL) for the front end data input and for querying.  CQA serves as the middle layer, like an intermediate language in a compiler.

It has been a good learning experience for the graduate students involved.  Students working on UMB-CDB have had to learn to understand research articles on the theory of constraint databases.  They also had to become acquainted with geographic information systems (GIS).  They also had to evaluate existing formats for storing GIS data, and present their findings to the group so as to decide on an import format for UMB-CDB. They also participated in putting together our demo proposal to VLDB'01, writing the first draft of the proposal.   And of course, nothing compares to the experience gained from hands-on development of a large system such as UMB-CDB.

We are completing the implementation of the 'plain vanilla' version of UMB-CDB, and are in the process of getting it ready to demo.   The purpose of this version is to demonstrate the advantages of our seamless integration of traditional and spatiotemporal data in one system, and of our homogenous query operators over both types of data, in terms of added expressiveness and ease-of-use.  It is our plan to demo this system at VLDB'01.

Once complete, this system will serve as a platform for implementing extensions for, and conducting research in:

(a) query languages for contraint systems
(b) visualization of contraint data
(c) optimization of constraint queries
(d) indexing structures for constraint databases

The homepage for UMB-CDB is http://www.cs.umb.edu/~dqg/cdb/

The description of the system, and the figure showing its architecture, is available in our demo proposal, at http://www.cs.umb.edu/~dqg/cdb/demo01.ps

Constraint Databases (CDBs) are an extension of relational databases that enrich both the relational data model and the relational query primitives with constraints.  For data-intensive applications over non-traditional data, CDBs hold the promise to combine the versatility of constraints with the commercial success of the relational approach.

Systems such as ours are meant to be used by researchers in other disciplines, such as Geography and Environmental Sciences, where the research involves large quantities of spatiotemporal data. It is hoped that our research will lead to revolutionizing the systems that researchers in those areas use to store and query their data.

There are several research projects taking place concurrently with ours, to provide proof-of-concept for relational databases.  However, ours is the only one where the system is built from the ground up (rather than on top of another database), and provides a flexible interactive interface designed for the naive user.