Netlog: a logic query language for network model databases

Data & Knowledge Engineering 6 (1991) 183-203 North-Holland

183

Netlog: a logic query language for network model databases* Sergio G R E C O , * Luigi P A L O P O L I * and Pasquale R U L L O * •Dipartimento di Sistemi, Universit,~ della Calabria, 87036 Rende (CS), Italy •CRAI, c/da S. Stefano, 87036 Rende (CS), Italy

Abstract. A logic-based language for network model databases is presented. The language, called Netlog, provides support for navigating through objects while preserving the declarativity of logic programming. A formal definition of the network data model is presented along with a syntax and a declarative sematics of Netlog. The suitability of Netlog as a query language for CODASYL databases is then shown and an operational semantics, in terms of ordinary logic programs, is provided. Keywor~. Logic programming, Navigational data models, Query languages, CODASYL databases.

1. Introduction

Nowadays, one of the main research directions in the database field is represented by the combination of the database technology with the logic programming paradigm. In particular, so far, most of the efforts have been devoted towards the integration of logic programming with relational databases [3, 24]. It is because there is a deep affinity between logic and the relational data model [8], as the structural simplicity of the latter allows the definition of declarative languages based on first order calculus [25]. Datalog [4, 24, 251 is an example of a logic language that extends the relational calculi (tuple- and domain-oriented) with recursion. Its bottom-up operational semantics provides support for a fully declarative style of programming. Little work has been done, so far, in combining logic programming with navigational databases, i.e. databases that can be described by data models that explicitly support the notion of relationship. These models are object-based (opposed to the relational model which is value oriented) in that objects have a permanent identity that allows to specify stable relationships among them independently on their values. A consequence of the existence of predefined paths among objects is that these databases are supportive of navigational query languages that provide suitable constructs for path traversals. Early examples of object-based models are the CODASYL [6, 7] and Entity-Relationship [5, 22] data models. More recently, GEM [27] and DAPLEX [21] have been proposed as extensions of the relational model to cope with explicit associations among relations. An interesting discussion on the use of Prolog as a query language for navigational DBMSs can be found in [281. In this paper we present Netlog, a logic language for querying navigational databases. It is based on a Prolog-like syntax and provides suitable constructs for navigating through * This work has been developed in the framework of the project 'LOGIDATA', partially supported by the Italian National Research Council within the program 'Progetto Finalizzato Sistemi Informatici e Caleolo Parallelo'. 0169-023X/91/$03.50 (~) 1991 - Elsevier Science Publishers B.V. (North-Holland)

184

S. Greco et al. / Netlog

objects. A peculiarity of Netlog is the way how it combines the declarativity of logic progamming with the navigational style of query languages for object-based data models. In the sequel of this paper, we shall confine ourselves to describe Netlog as a query language for CODASYL databases, as they represent a very large family of commercial database systems (e.g. IDMS, IDS/II). CODASYL databases support the network data model [25] which is based on two basic constructs: the record type, used to represent an entity, and the C O D A S Y L set (that we call Coset), representing a one-to-many relationship between two record types. The CODASYL Data Manipulation Language (DML) [10, 11] consists of a set of elementary commands defined on the underlying data model. These commands allow to efficiently access the database, but their expressive power is very limited as they support record-oriented operations (as opposed to the set-oriented primitives of relational languages). Thus, a general-purpose host language is needed to supply the control structures for navigating the database. The motivations for using Netlog as query language for CODASYL databases are two-fold: 1. It provides a single formalism to serve the role played by both DML and host languages. 2. It allows to express navigations at a very high level, as the only thing required is that of declaratively expressing conditions for relationship among objects. We point out that the elimination of (procedural) navigations provides a considerable advantage in terms of simplicity of programming and data independence. With respect to other proposals of declarative languages for CODASYL databases, such as those described in [13, 15, 20], we claim that Netlog is more natural and expressive as it provides support for navigation while keeping the elegance and the computational power of logic programming. This allows to write even complex enquiring transactions in a concise, readable and simple way. In the following sections of this paper we provide a formal description of the language and we show its capabilities by means of examples. In particular, in Section 2 we describe the CODASYL data model. In Section 3 we give the syntax of the language and a model theoretic semantics for negation-free programs. In Section 4 we illustrate, by a number of examples, the suitability of Netlog as a query language for CODASYL databases. In Section 5 we introduce negation in Netlog programs and modify the given semantics to cope with it. Finally, in Section 6 we provide an operational semantics in terms of ordinary logic programs.

2. The CODASYL data model

We summarize next some basic concepts about the CODASYL Data Model. We assume the existence of the following disjoint sets: 1. A countably, infinite set U of values. This set, called universe, contains (i) a special constant nil and (ii) a subset Z whose elements are called database keys. 2. A finite set R of symbols called record names. Each element of R is associated with a positive integer, its arity. 3. A finite set A = { A~ . . . . . A,, } of symbols, called attribute names. Each A~ is associated with a (countably infinite) subset of U, called the domain of A~ and denoted by d o m ( A i ) . We assume that, for each i, d o m ( A i ) is disjoint from {nil} U Z. 4. A finite set C of symbols, called Coset names. The basic data objects of the CODASYL data model are record types (or, simply, records) and C O D A S Y L set types (or Cosets). A record type is r(A 1. . . . . A , ) , where r E R is a record name, A~ E A (1