DATALOG(ID:3793/dat012)Logic programming language designed to be used as a database language Structures: Related languages
References: in Proceedings of the Third International Conference on Database Theory, Lecture Notes in Computer Science Nr. 470, Springer-Verlag, 1990 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 Proceedings of the Third International Conference on Database Theory, Lecture Notes in Computer Science Nr. 470, Springer-Verlag, 1990 view details The integration of logic programming and relational database techniques has led to the active research area of deductive databases. It combines the benefits of the two approaches, such as representational and operational uniformity, reasoning capabilities, re- cursion, declarative querying, efficient secondary storage access, etc. The function symbols of Prolog, which are typically used for building recursive functions and complex data structures, have not been found useful for operating over relational databases made up of flat relations. As a result, a restricted form of Prolog without function symbols called Datalog (with nega- tion), with a well-defined declarative semantics based on the work in logic programming, has been widely accepted as the standard deductive database language. Extract: Problems with Datalog and derivatives In the past few years, various set-oriented evaluation strategies specific for deductive databases have been the main focus of extensive research and a number of deductive database systems or prototypes based on Datalog have been developed and reported. These include Nail, LOLA, Glue-Nail, XSB, CORAL, Aditi, LogicBase, Declare/SDS etc. [...] However, deductive databases based on Datalog only provide inexpressive flat structures and cannot directly support complex values such as nested tuples and sets common in novel database applications. In fact, its predecessor Prolog can indirectly support nested tuples by using functors. in Proceedings of the Third International Conference on Database Theory, Lecture Notes in Computer Science Nr. 470, Springer-Verlag, 1990 view details in Proceedings of the 1999 ACM International Conference on Management of Data and Symposium on Principles of Database Systems Philadelphia, Pennsylvania, United States (PODS'99), 1999 view details deductive rules Deductive rules, conceived in the context of logic programming, provide the ability of deriving (deducing) new information from existing information, or to specify and test declarative properties. In databases, they are used to derive complex information from stored data and to specify integrity constraints on objects. Deductive rules cannot modify the database and therefore are sometimes called passive rules. logic programming Logic programming (LP) is a programming paradigm, emerged in the late seventies, characterized by the declarative specification in a logical style of queries and constraints over an application domain; it is contrasted to imperative programming, which is based on a procerdural specification style. With logic programming, queries and constraints are expressed with an homogeneous formalism and are evaluated by the same inferencing mechanism. lp & databases Logic programming alone is not a technology for managing large, shared, persistent, and reliable data collections. The natural extension of logic programming is the integration with database management, based on the use of logic programming as a query language. The resulting systems combine a declarative style for formulating queries and constraints with efficient and reliable database technology for mass-memory data storage. Several names are used to describe these systems: The term deductive database highlights the ability to use a logic programming style for expressing deductions concerning the contents of a database. The term knowledge base management system (KBMS) highlights the ability to manage (complex) knowledge instead of (simple) data. The term expert database system highlights the ability to use expertise in a particular application domain to solve classes of problems featuring large data sets. prolog & datalog Prolog is the most popular logic programming language. Prolog was at first expected to be used as a database language, but some of its features were not suited to dababase applications and this motivated the definition of an alternative database and logic programming language, known as Datalog. Datalog is a logic programming language specifically designed to be used as a database language. Syntactically, Datalog is very similar to Prolog. The evolution from Prolog to Datalog consists in going from a procedural, record-oriented language to a nonprocedural, set-oriented language; this transformation was parallel to the evolution of database systems from the hierarchical and network data models to the relational data model. in Proceedings of the 1999 ACM International Conference on Management of Data and Symposium on Principles of Database Systems Philadelphia, Pennsylvania, United States (PODS'99), 1999 view details |