Representing and querying complex information in the Coral deductive database system. Divesh Srivastava. The inadequacy of relational databases for new classes of applications has led to considerable research directed at enhancing the modeling capability of the database and the expressive power of the query language. The development of deductive databases was aimed at providing a declarative, potentially complete query language based on Datalog. However, Datalog lacks features such as aggregation and negation, does not support the manipulation of numeric values, and inherits the relational data model with its limited modeling power. Our goal in this thesis is to resolve these limitations of Datalog and to demonstrate that powerful and practical database query languages based on Datalog can be designed and efficiently implemented. We present a Magic-sets based bottom-up evaluation technique, Ordered Search, that can be used to efficiently evaluate programs with left-to-right modularly stratified aggregation and negation; this class of programs includes useful applications such as bill-of-materials. We provide theoretical results to demonstrate that our technique is more efficient than previous bottom-up evaluation techniques. We also give performance results from the implementation of Ordered Search in the Coral deductive database system showing the practicality of this evaluation technique. We propose a program transformation technique, Constraint-rewrite, which propagates arithmetic constraints, such as Cost <= 100, specified in a program. By considering semantic manipulation of constraints, our techniques significantly extend earlier work. The Constraint-rewrite transformation can be combined with the Magic-sets transformation to efficiently propagate both constant binding and constraint binding information. We also develop a uniform framework that integrates our results and the earlier related work in the literature. We design a deductive, object-oriented language, Coral++, that combines the data modeling features of C++ and the querying capability of Coral---two existing languages---with minimal changes to either, and yields a powerful combination of the object-oriented and deductive paradigms. We describe our implementation strategy for Coral++, which effectively uses the existing Coral run-time system and the C++ compiler to support the object-oriented features of the Coral++ data model and query language.