CORAL(ID:1925/cor004)Language for deductive databasefor COntrol Relations And Logic U Wisconsin Madison. 1993. Language for deductive database. Prolog-like syntax with SQL-like extensions. Many evaluation techniques are supported. Implemented in C++. from CMU AI gloss: "CORAL is a deductive database/logic programming system developed at the University of Wisconsin-Madison. It is a declarative language based on Horn-clause rules with extensions like SQL's group-by and aggregation operators, and uses a Prolog-like syntax. CORAL supports many evaluation techniques, including bottom-up fixpoint evaluation and top-down backtracking, a module mechanism, support for disk-resident data, a C++ interface, and an on-line help facility." People: Structures: Related languages
References: in Chomicki, Jan (ed) Proceedings of the NA CLP’90 Workshop on Deductive Databases view details of CORAL is that it provides a wide range of evaluation strategies and allows users to --- optionally --- tailor execution of a program through high-level annotations. A CORAL program is organized as a collection of modules, and this structure is used as the basis for expressing control choices. CORAL has an interface to C++, and uses the class structure of C++ to provide extensibility. Finally, CORAL supports a command sublanguage, in which statements are evaluated in a user'specified order. The statements can be queries, updates, production-system style rules, or any command that can be typed in at the CORAL system prompt. External link: Citeseer in Proceedings of the International Conference on Very Large Databases, 1992 view details in [ACM SIGMOD] Proceedings of the 1993 ACM SIGMOD Conference on Management of Data view details in [ACM SIGMOD] Proceedings of the 1993 ACM SIGMOD Conference on Management of Data view details in [ACM SIGMOD] Proceedings of the 1993 ACM SIGMOD Conference on Management of Data view details 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. in [ACM SIGMOD] Proceedings of the 1993 ACM SIGMOD Conference on Management of Data view details the data model is feasible, and is orthogonal to the techniques used for object storage and retrieval. Extract: Related research 1.2 Related Proposals The Coral++ data model and query language have been influenced by other proposals for integrating object-oriented data models and declarative query languages. Some of the important aspects of our design are: Overview of the Coral++ Design The central observation is as follows: Object-oriented features such as abstract data types, encapsulation, inheritance and object-identity are essentially extensions of the data model. We can achieve a clean integration of these features into a deductive query language by allowing the deductive language to draw values from a richer set of domains, and by allowing the use of the facilities of the deductive language to maintain, manipulate and query collections of objects of a given type. In relational query languages such as SQL, values in fields of tables have been restricted to be atomic constants (e.g. integers or strings). In logic programs, values can be Herbrand terms, which are essentially structured values. In Coral++, values can additionally be of any class definable in C++ [29]. (We chose C++ since it provides a well-understood and widely used object-oriented type system.) Coral++ provides support for maintaining extents or collections of objects of a given type, either in a simple manner that reflects the inclusions associated with traditional IS-A hierarchies, or in a more sophisticated way through the use of declarative rules. The idea is to automatically invoke code that handles extent maintenance whenever objects are created or destroyed, and provide constructs to use these extents in Coral++. We also provide support for creating and manipulating various types of collections: sets, multisets, lists and arrays, whereas traditionally only sets and multisets are provided. Coral++ separates the querying of objects from the creation, updating and deletion of objects, and provides separate sub-languages for these two purposes. This methodology stems from the view that querying is possible in a declarative language, whereas creation, updates and deletion should be performed only using an imperative language. In summary, the proposal is simple, combines features of C++ and Coral---two existing languages--- with minimal changes to either, and yields a powerful combination of the object-oriented and deductive paradigms. The essential aspects of the integration are not specific to our choice of C++ and Coral, and the ideas can readily be used to combine other object-oriented and deductive systems in a similar manner. Extract: Introduction Introduction In recent years considerable research has been done in extending relational database languages, such as SQL, which have proven inadequate for a variety of emerging applications. Two main directions of research in database programming languages have been object-oriented database languages and deductive database languages, and the issue of combining the two paradigms has received attention recently. Object-oriented database languages, such as O++ [1] and O 2 [7], among others, enhance the relational data model by providing support for abstract data types, encapsulation, object identifiers, methods, inheritance and polymorphism. Such sophisticated features are very useful for data modeling in many scientific, engineering, and multimedia applications. Deductive database languages, such as LDL [19], Coral [23] and Glue-Nail! [21], among others, enhance the declarative query language by providing a facility for generalized recursive view definition, which is of considerable practical importance. However, data models for deductive databases are typically structural, and do not have the richness of object-oriented data models. One of the contributions of this paper is to demonstrate that the advantages of object-oriented database languages and deductive database languages can indeed be combined in a clean and practical manner. Our proposal, Coral++, has the following objectives: Related Work There are many proposals in the literature ([28, 4, 6, 8, 13, 9, 20, 10, 17, 3, 2, 11, 30], among others) for integrating object-oriented data models and declarative query languages. Typically, these proposals support features such as complex objects, data abstraction, inheritance and polymorphism in their data model, and the ability to pose queries on collections of objects using a suitable query language. We presented a summary of the differences between our proposal and these other proposals in Section 1.2. We now examine some of the closely related proposals in more detail. Proposals Based on C++ ZQL[C++] [3] and CQL++ [6] are the proposals most closely related to Coral++ since they are also based on the C++ object model. The Coral++ query language is more expressive than CQL++ or ZQL[C++], which are based on SQL. However, each of these proposals is integrated with a computationally complete imperative language: CQL++ with O++ [1], and Coral++ and ZQL[C++] with C++. CQL++ has a syntax similar to SQL syntax for class definition. These classes do not have any facility for data abstraction (i.e., all class members are public). Further, accessing an attribute or invoking a method in a CQL++ query uses the `dot notation' of SQL, i.e., the user does not have to deal with explicit pointer dereferencing. In Coral++ and ZQL[C++], class definitions can use all the features of C++ including data abstraction, and C++ expressions can be used for accessing attributes and invoking methods in a query. In Coral++ and CQL++, path expressions are treated as values that can be arguments to booleanvalued predicates. ZQL[C++], on the other hand, allows C++ expressions to serve directly as predicates. Since ZQL[C++] also allows SQL subqueries to appear as predicates, it does not distinguish between the predicate truth semantics and the C++ expression truth semantics, unlike Coral++ and CQL++. Proposals Based on Deductive Languages The COMPLEX data model [9] is a structural, typed data model that adds features such as object identity, object sharing and inheritance to the relational model. It does not support abstract data types, encapsulation, or methods; consequently, the data model is not as rich as the Coral++ data model. The query language of COMPLEX is C-Datalog which can be automatically translated to Datalog, and evaluated using an engine for evaluating Datalog programs. This translation is possible because of the lack of behavioral features and polymorphism in the data model. It is not clear how the translation approach generalizes once we introduce behavioral features in the model. LDL++ [2] is a deductive database system whose type system extends that of LDL [19] with an abstract data type facility that supports inheritance and predicate-valued methods. However, it does not support object sharing or ADT extents, and its support of encapsulation and object identity is limited. consequently, the data model is not as rich as the Coral++ data model. Further, LDL++ methods can be defined only using LDL++ rules; however, this can be done more naturally than in Coral++. Proposals Based on Non-Horn Logics XSQL [13] extends SQL by adding path expressions that may have variables that range over classes, attributes and methods. This facilitates querying schema information as well as instance-level information in object-oriented databases, using a single declarative query language. Noodle [17, 18] is a declarative query language for the Sword declarative objectoriented database. Unlike Coral++ and XSQL, Noodle does not use path expressions to access attributes and invoke methods on objects. Instead, Noodle uses a syntax reminiscent of HiLog [5] for this purpose. Noodle also has a number of built-in classes to facilitate schema querying. Orlog [10] combines the modeling capabilities of object-oriented and semantic data models, and is similar to Noodle in that its logic-based language for querying and implementing methods uses a higher-order syntax with first order semantics. In Coral++, methods and other aspects of data abstraction borrowed from C++ are viewed as being outside the scope of the deductive machinery, notably the unification mechanism. A more comprehensive treatment of features like path expressions (e.g., as in XSQL [13]) may well enable more efficient (i.e., setoriented) processing of certain queries. We make no attempt to give these features a logical semantics; we simply borrow the C++ semantics, in order to enable ease of implementation. The semantic foundations of XSQL, i.e., F-logic [14], Noodle, i.e., HiLog, and Orlog have features that are difficult to support efficiently, at least in a bottomup implementation. In particular, variables can get bound to predicate names only at run-time, and this causes problems with analysis of strongly connected components (SCCs) and can make semi-naive evaluation inefficient. In contrast, one of the design motivations of Coral++ was to have a language that is rich in expressive power and can be efficiently evaluated within the framework of existing evaluation techniques. There are several other interesting proposals for combining semantically rich data models with deductive databases that are less closely related to Coral++. ConceptBase [11] and Quixote [30] are two such systems. ConceptBase is based on the Telos knowledge representation language, and allows the specification of methods using deductive rules and integrity constraints. Quixote is a knowledge representation language that allows subsumption constraints, knowledge classification and inheritance and query processing for partial information databases. in [VLDB] Proceedings of the International Conference on Very Large Databases, 1993. view details in The VLDB Journal, Special Issue on Prototypes of Deductive Database Systems, 3(2) April 1994 view details in Concurrency: Practice and Experience 2000 v12 view details Resources
|