Traditionally, database applications have relied on Data Definition Languages (DDLs) for the declaration of data types and structures and Data Manipulation Languages (DMLs) for the insertion, retrieval, manipulation and upate of data. Such languages are generally lacking in the computational power necessary for most applications, which is usually obtained by embedding the DML in a programming language, thus giving an uneasy amalgam of the data model and the computational model.
FDL is a new database language with a single integrated model for both data and computation. The language consists of two, purely functional, complementary levels, the object level and the meta level. Data representation, manipulation and querying are handled at the object level, and upates at the meta-level. This paper outlines the motivation for development of FDL and overviews its central features. The expressiveness and computational power furnished by its functional model are demonstrated, including its suitability for representing and manipulating complex objects. The method used in its implementation is also described.
Traditionally, database applications have relied on Data Definition Languages (DDLs) for the declaration of data types and Data Manipulation Languages (DMLs) for the insertion, retrieval, manipulation and upate of data. Such languages have generally been lacking in the computational power necessary for most applications, and this has been obtained either by embedding DMLs in programming languages or extending them with computational features, or by equipping programming languages with persistent data types. In both cases, an uneasy amalgam of the data model and the computational model usually arises.
FDL is a new database language with a single model for both data and computation. It consists of two, purely functional, complementary levels, the object level and the meta level. This paper outlines the motivation for the development of FDL and overviews its central features. The expressiveness and computational power furnished by its functional model are demonstrated, and an implementation is described.
We introduce the functional database language FDL which extends the functional data model to computational completeness while also supporting the persistence of any function, whether extensionally or intensionally defined. FDL improves on previous implementations of the functional data model by providing a uniform formalism both for modelling data and for computation, by supporting arbitrarily nested types which are all persistent, and by allowing for the representation of incomplete and default knowledge. All functions are updated incrementally by the insertion and deletion of individual equations and an integrity sub-system verifies updates against the declared semantic integrity constraints.
We present the concept of a default database which comprises a set of facts a set of deduction rules and a set of defaults. Defaults define assumptions to be made about information not derivable from the rules and facts. Defaults, by augmenting the information which is a consequence solely of the rules and facts, enable definite responses to queries on the basis of 'common sense' assumptions rather than responses of the form 'unknown'. The augmented information is termed an extension. Although such an extension is self-consistent, in general two or more mutually inconsistent extensions can arise. We characterise the rules and defaults of a database as safe if only one extension can arise for any given set of facts. We give conditions which are necessary and sufficient to ensure safety.
This paper argues that the treatment of incomplete information in conventional database systems is inadequate. It is not possible for users to formulate queries which clearly state what it is they want to know and the answers to queries are often misleading. These problems can be remedied by the use of modal logic which allows questions to be asked about what might be true and what must be true, rather than simply what is true.
This paper presents a functional database language which seamlessly integrates propositional modal logic with the computationally complete functional data model of FDL, thus allowing incomplete information to be handled more effectively than in SQL or in more recent developments.
Fudal is a functional database language incorporating Modal Logic. Its purpose is the management of incomplete information.
Fudal is a development of the language FDL, which integrates the functional programming paradigm and the functional data model, and contains two elements not found in FDL. Firstly, when the result of a function is unknown, one may specify a list of possible results. Secondly Fudal allows modal expressions : (Surely P) is true if it is certain that P is true, and (Maybe P) is true if it is possible that P is true.
The use of Modal expressions leads to a treatment of incomplete information that is more logical than that performed by languages such as SQL, and allows us to state more clearly the conditions to be satisfied in the course of evaluating a query by specifying whether those conditions should be certainly true, or possibly true.
We present in this paper Gql, a declarative graphical query language based on the functional data model. Gql queries are fully represented by a single diagram. Without containing any explicit boolean operators or logical quantifiers, Gql provides users of varying degrees of programming experience, with the same expressive power for retrieval as SQL. The design philosophy and characteristics of the language are discussed, and an informal presentation of Gql's constructs and semantics is given. Finally, gql_int, the implementation of an interface for the language is described.
The problem of formalization for visual query languages has been identified as an important one. We present in this paper a formal definition of both the syntax and semantics of Gql, a declarative graphical query language based on the functional data model. In Gql a query is fully and unambiguously represented by a single diagram and the user interaction is kept distinct from the language itself. In our approach for formalization we abstract from the world of graphics and concentrate on a world of sets and functions, called the base structure, which represent the various elements of the language. The syntactical definition of the language is completed by defining a set of rules that a base structure instance must satisfy, in order for it to correspond to a legal Gql query. The semantics of the language is given via a functionally defined, syntax-directed translation from Gql queries (represented as base structure instances) to list comprehensions. Finally, a form of Attribute Grammar is used in conjunction with the previous definitions for specifying in a single formalism both the syntax and semantics of Gql.
This paper describes the use of Hydra to program a facility to find database values which are directly or indirectly associated with each one of a list of parameter values.
In functional databases surrogates are used to represent entities, and functions to represent relationships. Typically surrogates are system-generated and not visible to the user. We believe this weakens the connection between a real-world entity and its database counterpart. It also prevents the use of existing unique identifiers as surrogates. In a functional database language a function name represents a Lambda expression and it is not possible to return a function as a result in a form which conveys semantics. This prevents answers being given to a query such as What links are there between the entities John and Mary?. This paper presents the approach of Hydra, a functional database language with several novel features including the facility to find how distinct entity instances are linked. Surrogates are visible and may be user-defined or system-generated; they may also be changed. Functions are distinguished and compared using their identity rather than the mapping they represent. Hence functions, representing links between entities, may be meaningfully returned and further used, so significantly increasing semantic power.
The integration of the Functional Data Model with functional programming represents an important advance. However this integration limits the retrieval power of the resulting database language for certain application areas. In particular they lack the ability to query schema information and to discover associations between particular entities. The language Hydra described in this paper enhances the query power of functional database languages with associational primitives which search the database for connections.
This paper presents the functional database language Hydra which extends previous such languages with associational facilities enabling a user to pose queries about the ways in which values and entities in the database are related to each other. These associational facilities work by treating the database as a graph and following all the arcs from a node or finding paths between nodes. The nodes of the database graph correspond to entities or values in the application domain and the arcs to associations between those entities and values. From the perspective of Hydra this database graph is viewed in terms of functions between sets of entities and values. Associational facilities are provided by built-in second-order primitives which use schema-level information to determine what arcs may be associated with a node or as the basis for searching for an instance-level path. Results from associational primitives are returned in the form of lists of functions which may be displayed to the user or directly applied to other parameters. The associational facilities provided are fully integrated into a computationally complete language in the style of Miranda. The integration allows complex queries to be answered, which are beyond the power of conventional database query languages.
The motivation and objectives of TriStarp are reviewed and the overall architecture of the project presented. This architecture comprises three levels, a binary relational storage structure (BRSS) at Level 0, a computationally complete database language at Level 1, and an end-user interface at Level 2. Requirements of the BRSS are identified and methods for its implementation are discussed. Two Level 1 languages have been developed which extend the BRSS with deductive and constraint enforcement capabilities, based upon the logic and functional paradigms. We identify a common architecture for these languages and show how they can be integrated to share data. We conclude with a discussion of further research directions for TriStarp.
Textual database programming languages are computationally complete, but have the disadvantage of giving the user a non-intuitive view of the database information that is being manipulated. The visual languages developed in recent years have allowed naive users access to a direct representation of data, often in a graph form, but have concentrated on user interface rather than complex programming tasks. There is a need for a system which combines the advantages of both these programming methods.
We describe the implementation of Spider, an experimental visual database programming language aimed at programmers. It uses a graph-rewriting paradigm as a basis for a fully visual, computationally complete language. The graphs it rewrites represent the schema and instances of a database.
The unique graph-rewriting method used by Spider has syntactic and semantic simplicity. Its form of algorithmic expression allows complex computation to be easily represented in short programs. Furthermore, Spider has greater power than normally provided in textual systems, and we show that queries on the schema and associative queries can be performed easily and without requiring any additions to the language.
We describe in brief a lazy functional database language Relief, which supports an entity-function model and provides for update and the input of data by means of functions with side-effects. An eager let construct is used within the lazy graph reduction mechanism to sequence the effects. To redress the loss of referential transparency we have implemented an effects checker which can identify referentially transparent regions or scopes within Relief.
Recent work in database systems has proposed the use of default rules to extend the apparent information content of a database using explicitly stated assumptions. This work, carried out in the context of the logic paradigm, is briefly reviewed. We then also review how such defaults can be coded in FDL, a recently introduced database language which follows the functional paradigm. The paper concludes with some comparative comments and suggests further work.
Current approaches to computation using visual data representations usually access a textual language for complex tasks, or concentrate on the simpler queries that can be easily expressed with the present visual techniques.
We describe an implementation of Spider, an experimental visual database programming language. It uses a graph rewriting paradigm as a basis for a fully visual, computationally complete language. The graphs it rewrites represent the schema and instances of a functional data model. Application nodes are added to this graph and initiate transformations which delete and create primitives, including the application nodes.
Separate visual tools are included for defining the database instance and schema data, and transformations. A window displays the graph rewriting process, including the final results.
This paper discusses a new approach to Temporal Database modelling using the notion of a real world event as primitive,the target implementation language being TFDL. We believe that our approach greatly improves the semantic content of the database.
This paper introduces a Temporal Functional Database Language (TFDL), which realizes an event oriented approach to historical database modeling. According to this approach, the events that occur in an evolving system is the fundamental information which should be recorded. The time series of the system states is secondary information in the sense that it can be derived from the occurred events.
This paper introduces a new approach to incorporating the temporal dimension n database systems. Instead of introducing time as an attribute in a conventional state database the paper proposes that state databases are derivatives from event databases which are regarded as fundamental. A data modelling approach is introduced together with a realization in terms of a Temporal Functional Database Language (TFDL).
This paper presents an approach to providing an interface to a functional database which allows novice users to query the database without the need to be familiar with a query language or the database schema. We use the set of types and functions in the database schema as the basis for generating a set of default queries. This set of default queries may then be modified by the database designer to select the most appropriate queries and to add further queries which were not automatically generated. The queries are organised in the form of a lattice such that similar queries are closely related. This lattice then forms the basis of a graphical interface to the database from which queries can be invoked and further refined.
The basic premise of this work is that an important feature of dynamic multi-dimensional file organisations should be a facility for tuning performance on the basis of information provided by database administration. In this paper we suppose that such information is given as probability distributions for both the form of, and specified values in, queries to be made to the system. For a class of grid file methods we show how the information supplied can be exploited. Of existing optimisation methods in the literature, none are totally assumption-free with respect to these probability distributions. The method we give, however, is totally assumption-free.
This dissertation investigates and discusses issues relating to the locking of triple stores in a multi-user environment.<.p>
This paper presents and discusses a radically different approach to multi-dimensional indexing based on the concept of the space-filling curve. It reports the novel algorithms which had to be developed to create the first actual implementation of a system based on this approach, on some comparative performance tests, and on its actual use within the TriStarp Group at Birkbeck to provide a Triple Store repository. An important result that goes beyond this requirement, however, is that the performance improvement over the Grid File is greater the higher the dimension.