CAREER: Visual Query Languages for Database Systems

M. Isabel F. Cruz

Computer Science Department
Worcester Polytechnic Institute

Contact Information

100 Institute Rd
Worcester, MA 01609-2280
Phone: (508) 831-5621
Fax : (508) 831-5776
Email: ifc@cs.wpi.edu

WWW PAGE

http://www.cs.wpi.edu/~ifc/grants/career.htm

Keywords

Query languages, Visual languages, Digital libraries, Multimedia, Information visualization, Web retrieval, Constraint languages, Human-Computer Interaction

Project Award Information

Project number: 9896052
Duration: Four years (currently 2^nd year)
Title: CAREER: Visual Query Languages for Database Systems

Project Summary

New technologies such as multimedia, digital libraries, and electronic publishing require large databases and powerful query languages. This project investigates a database management system that supports a meta-query language with which users can design their own visual query languages to specify both the data to retrieve and the display format. Theoretical aspects of the research address the characterization of classes of visual queries that can be evaluated with guaranteed time-complexity by providing a careful design of the query evaluation engine. Practical goals include the implementation of a database management system supporting visual queries, the dissemination of results using the WWW, and the transfer of technology. The project has a strong educational component, seeking the involvement of graduate and undergraduate students and the inclusion of prototypes in the classroom so as to reflect the more interactive and visual aspects of today's computer science. Visual query languages will be key components of the next generation of declarative database interfaces because they take advantage of the user's visual perception to convey information efficiently. Their successful implementation will provide database systems with fundamental capabilities not currently available.

Goals, Objectives, and Targeted Activities

We are currently involved in several projects. We describe their current status and plans for 1998-1999.

Delaunay^MM: We have been designing and implementing this visualization framework for querying and presenting multimedia information in distributed resources, including the Web. Currently we are using Delaunay^MMto query the Perseus digital library (www.perseus.tufts.edu) and are conducting usability studies. In 1998-1999 we will continue this work in several directions, including its extension to electronic commerce applications and further investigation on heterogeneous database querying and data migration.
CASA (Classification using a Structural Approach): We have been investigating automatic classification of Web documents Recent results include the study of recall based on the structural analysis of over 600,000 Web documents. In 1998-1999 we will look at more sophisticated algorithms for classification that may improve recall.
Mocha: This is a distributed model with a client-server architecture that optimally partitions the software components of a typical algorithm animation system and leverages the power of the Java language. This system is currently used for geometric algorithms.
Other Projects: Multimedia authoring (visual languages for the specification of animation using different multimedia streams), and incremental graph drawing using a constrained approach.

Indication of Success

Less than half-way through the tenure of the grant we have exceed the proposed goals for the first two years. In particular, we have implemented three systems (Delaunay, Delaunay^MM, Mocha) that we demonstrated in major conferences. Our research has already had a practical impact: Delaunay^MM is being integrated with the Web interface to Perseus, an award-winning digital library of ancient history. Several projects have attracted the interest of industry and we are maintaining close collaboration with two companies. We collaborate with other universities (Brown University, SUNY Buffalo, University of Rome, University of Bari) and our work has been published in conferences in the areas of Databases, Visualization, Multimedia, and Computational Geometry. Our work on algorithm animation was recently selected to appear on a special issue of Computational Geometry Theory and Applications, featuring the best papers in the ACM Symposium on Computational Geometry.

Project Impact

Human Resources: In the last two years, fifteen students have been involved in the different projects (and five have been directly sponsored by the grant). Wendy Lucas's PhD is expected for the spring of 1998; she has accepted a tenure-track position in the MIS Department at Bentley College. Seven of the students have published in major international conferences (including five undergraduate students). Four women students and two minority students have been part of the team. Of the undergraduate students, Kirby Zhang was accepted with full support for graduate studies at Berkeley and the others have joined industry. Slava Borisov (MS, 1997) has his own software company in New York City. Two of the undergraduate students, Melissa Radzyminski and Michael Averbuch have received the CS best student award for their graduation year. We collaborate with researchers from several universities and have sponsored several researchers to visit our group.
Education and curriculum development at all levels: We are redesigning two courses on Human-Computer Interaction (at the graduate and undergraduate levels). In 1998-1999, we will continue the development of a senior course on Webware, which will be taught for the second time at WPI. The curriculum will include the study of client-server architectures, access to databases on the Web, information retrieval on the Web, and Web-based user interfaces.
Department/institution infrastructure: The Computer Science Department has twelve faculty members in the areas of Databases, Knowledge Representation and AI, Visualization, Distributed Systems, Web-based education, and Software Engineering. Recently with Matthew Ward and Elke Rundensteiner we were awarded a NSF CISE Research Instrumentation Grant to support research on Large-Scale Data Visualization and Management.
Industry: Transfer of technology and collaboration has started with GTE in Waltham, MA (query and languages for electronic publishing and electronic commerce) and with Dataviews Corporation in Northampton, MA (data visualization and data migration).

Selected Project References

I.F. Cruz, M. Averbuch, W. T. Lucas, M. Radzyminski, and K. Zhang. Delaunay: a Database Visualization System. In Proc.of ACM SIGMOD 97, pp. 510-513, 1997
I.F. Cruz and W. T. Lucas. Delaunay^MM: a Visual Framework for Multimedia Presentation. In Proc. of IEEE Visual Languages, pp. 216-223, 1997.
I.F. Cruz and W. T. Lucas. A Visual Approach to Multimedia Querying and Presentation. In Proc. of ACM Multimedia, pp. 109-120, 1997
I.F. Cruz, S. Borisov, M. A. Marks, T. R. Webb, Measuring Structural Similarity among Web Documents: Preliminary Results. In Proc. of the 7^th Int. Conf. on Electronic Publishing, LNCS, Springer Verlag, 1998 (to appear).
J. E. Baker, I. F. Cruz, G. Liotta, and R. Tamassia. Algorithm Animation over the World Wide Web. In Proc. Int. Workshop on Advanced Visual Interfaces (AVI '96), ACM Press, pp. 203-212, 1996.
I.F. Cruz. Tailorable Information Visualization. ACM Computing Surveys 28A(4), 1996.

Area Background

Declarative query languages allow for the user to specify what information to retrieve from the database without having to specify how the information is to be retrieved. Visual query languages appeal to the strengths of human perception and are based on visual representations (e.g., entity-relationship diagrams, class and object hierarchies). We investigate declarative and visual query languages with which users can define the presentation of quantitative information (e.g., as bar charts), of relationships (e.g., as networks), and of multimedia data (e.g., as pages in a virtual book). Data can be in a local database or in distributed repositories, such as those available on the Web. Our research also addresses the retrieval of Web documents and their automatic classification, e.g., based on their layout characteristics.

Information visualization systems typically map data into visual objects. Traditionally, the layout specification has been expressed textually. In our research, we use visual (query) languages to express this mapping. A natural strength of this approach is the capability to filter out unwanted data and in general to express powerful queries involving recursion while specifying the visualization. Constraints allow for the specification of the spatial and temporal layout of the information (the latter being used for the layout of multimedia streams). Algorithm animation addresses the visualization of information to display the sequence of data transformations as performed by an algorithm.

Area References

T. Catarci, M. F. Costabile, S. Levialdi, and Carlo Batini. Visual Query systems for Databases: A Survey. Journal of Visual Languages and Computing, March 1997.
T. Catarci, I. F. Cruz. Special Issue on Information Visualization. ACM SIGMOD Record 25(4), 1996.
W. F. Cody et al. Querying Multimedia Data from Multiple Repositories by Content: the Garlic Project. In Proc. of the 3rd IFIP Working Conference on Visual Database Systems, 1995.
I.F. Cruz. DOODLE: A Visual Language for Object-Oriented Databases. In Proc.of ACM SIGMOD, pp. 71-80, 1992.
I.F. Cruz. Expressing Constraints for Data Display Specification: A Visual Approach , Principles and Practice of Constraint Programming, Vijay Saraswat and Pascal Van Hentenryck, eds., The MIT Press, pp 443-468, 1995.
I.F. Cruz. User-defined Visual Query Languages. IEEE Symposium on Visual Languages (VL '94), pp. 224-231, 1994.
I. F. Cruz and A. Garg. Drawing Graphs by Example Efficiently: Trees and Planar Acyclic Digraphs. In Proc. of Graph Drawing '94, LNCS, Springer Verlag, pp. 404-415, 1995.
G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis. Algorithms for Drawing Graphs: an Annotated Bibliography. Computational Geometry: Theory and Applications, 4(5), pp. 235-282, 1994.
K.J. Goldman, S.A.Goldman, P.C. Kanellakis, and S.B. Zdonik. ISIS: Interface for a Semantic Information System. In Proc.of ACM SIGMOD, pp. 328-342, 1985.
E. M. Haber, Y. E. Ioannidis and M. Livny. OPOSSUM: Desk-Top Schema Management through Customizable Visualization. In Proc.of VLDB, pp. 527-538, 1995.
D. Harel, On Visual Formalisms. CACM, 31(5), pp. 514-530, 1988.
M. Kifer, G. Lausen, and J. Wu. Logic Foundations of Object-Oriented and Frame-Based Languages. JACM, 42(4), pp. 741-843, 1995.
Miron Livny, Raghu Ramakrishnan, Kevin Beyer, Guangshun Chen, Donko Donjerkovic, Shilpa Lawande, Jussi Myllymaki, and Kent Wenger.``DEVise: Integrated Querying and Visual Exploration of Large Datasets. In Proc of ACM SIGMOD, May, 1997.
A. O. Mendelzon and G. A. Mihaila and T. Milo. Querying the World Wide Web. Int. J. of Digital Libraries, 1(1), pp 54-67, 1997.
L. Weitzman and K. Wittenburg. Grammar-based Articulation for Multimedia Document Design, Multimedia Systems 4:99-111, 1996.

Potential Related Projects

PIs: Alex Brodsky, Shi-Kuo Chang, Max J. Egenhofer, Michael Kifer, Miron Livny, Renée J. Miller, Raghu Ramakrishan, Louiqa Raschid, Peter Revesz, Ken Ross, Elke Rundensteiner, Dennis Shasha, Jason T. L. Wang.