Relationlog(ID:7143/rel008)Extension of Datalog to suit nested relations People: Related languages
References: We propose a novel logic-based language for nested relations called Relationlog. It is a typed extension to Datalog with powerful sets and tuples constructors. Typing is a good programming discipline, and is essential to guarantee program termination and the consistency of the database. [...] One of the main novelties of Relationlog is the powerful mechanisms for representing both partial and complete information on sets and tuples. With them, we can represent the extended relational algebra operations [...] directly and recursively as we do in Datalog for the relational algebra operators. Another novel feature of the Relationlog is the introduction of a new ordering, namely preferable sub-interpretation, on interpretations. This ordering captures the intended semantics for nested sets, tuples and relations. The Relationlog language is given a firm logical foundation in the form of Herbrand-like minimal model semantics based on the preferable sub-interpretation ordering. A stratification in the spirit of a number of other researchers is used [3, 4, 6]. We show that for a stratified program, a minimal and supported model when it exists can be computed bottom-up using a finite sequence of fixpoints and used as the intended semantics of the program. The RELATIONLOG Language Unlike Datalog which is an untyped deductive language for flat relations, Relationlog is a typed deductive language for nested and complex object relations. A Relationlog database consists of a collection of named relations, whose tuple components can be tuples, sets, lists, and bags besides atomic values. The relations are partitioned into two kinds: base relations (or extensional relations) which are stored persistently on disk and can be directly updated by the user, and views (or intensional relations) which are defined by rules and cannot be directly updated by the user. The Relationlog language consists of three sub-languages: data definition language, data manipulation language, and query language. Extract: Datalog languages Deductive database systems based on Datalog only support flat relations which are inappropriate for advanced data and knowledge-based applications. For this reason, Datalog has been extended into more powerful languages to support data with complex structures, such as LDL [32], LPS [33], COL [34], Hilog [35], and Relationlog [36]. See Reference [37] for an overview of some of these languages. Several deductive database systems that support data with complex structure have been developed, such as LDL [38], COL [34], and CORAL [39]. However, they are only implemented as memorybased systems and fail to address the issues of effective storage, efficient access and inference of large amounts of data with complex structures, although LDL and CORAL both have interfaces to persistent database systems so that persistent data can be loaded into the memory for processing. The objective of the Relationlog system is to develop techniques for new generation database systems that directly support the storage and inference of large amounts of data with complex structures based on the Relationlog query language [36]. The Relationlog query language is a typed extension of Datalog with tuples and sets. It stands in the same relationship to the nested relational and complexobject models as Datalog stands to the relational model. Furthermore, it has a well-defined declarative semantics. Extract: Implementing Relationlog The Relationlog project started at the beginning of 1996. There have been three different implementations of Relationlog. The first one was built on top of the commercial DBMS Oracle and Ingres by using C with embedded SQL statements. This implementation successfully turned Oracle and Ingres into a persistent deductive database system that supported large amounts of data with complex values and the Relationlog language. However, the performance was not satisfactory for the following reasons. First, nested and complex-object relations in Relationlog had to be stored as flat relations so that there was a significant overhead to convert between flat relations and complex object relations. Second, not much query optimization could be performed by the Relationlog program as it was a fat client with no access to the physical level of the DBMS server. Last, even though relational database operations were set-at-a-time, access to the relations in our C program with embedded SQL statements could only be cursor-based and was only tuple-at-a-time. The second implementation was built on top of the EXODUS persistent storage manager [9]. EXODUS was a very good choice for Relationlog. It was client/server based and supported the storage of data with complex structures. However, it was no longer supported and its host language, E, did not provide a reasonable debugging environment so that it turned out to be very difficult to develop a large system like Relationlog. After struggling with EXODUS for several months with a small portion of Relationlog working, we had to abandon this implementation. Finally, we have chosen PARODY (Persistent Almost-Relational Object Database Manager) [40] for the Relationlog system development. Unlike Oracle, Ingres and EXODUS, PARODY is only a singleuser database system that does not support concurrency control, transaction, and recovery management. However, PARODY supports persistent objects with B-tree and Hash indexes and has concise fullyimplemented C++ codes that are portable to multiple platforms. These features are essential for the objective of the Relationlog prototype, as we do not have to start from scratch. To make PARODY more suitable for Relationlog, the original code has been modified extensively to support Relationlog data and metadata storage and management. |