So far it has been characteristic of Prolog-based representations of relational databases that only the instance level is represented explicitly whereas the schema (or meta) level is implicitly in the mind of the user. This approach has several serious disadvantages. In this paper we develop a Prolog-based experimental system for relational databases. In this system all manipulation is based on such a knowledge representation which binds the instance and schema levels together in a natural, precise and systematic way. We show that this kind of knowledge representation affords the possibility of defining the essential concepts associated with structures and operations of relational databases generally i.e. without binding the definition to any sample database which is the usual situation in the approaches based on representing only the instance level explicitly. Because of general definitions in our experimental system it can be connected flexibly to other rule-based systems. We show that our experimental system can also be used flexibly to define various constraints related to the structures and operations of relational databases. These constraints may concern both the schema and instance levels. Complex structural relationships among data have a central role in database applications. Therefore we need strong general means and principles for structuring knowledge in Prolog. In this paper we propose the use of the structural primitives : tuples, maps and sets with their primitive operations to manage complex structural modelling in a Prolog environment. Analogously to the abstract data type mechanism we can combine these structural primitives with each other. This approach affords also the possibility of defining a set of general primitive operations for each structural primitive. In general such primitive operations are called meta-rules and they play a central role in the definition of our experimental system. The framework of this paper is based only on the theoretical foundations of the relational model. This starting point affords the possibility of utilizing the framework both in the context of different approaches to integrate a relational database system with a deductive system and in the context of different relational database topics such as relational database design, relational database restructuring, relational query languages etc.

Keywords : Logic programming methodology, Prolog, logic grammars, metarules, knowledge representation, relational databases, query execution.

Abstract of Data conversion, aggregation and deduction for advanced Retrieval from heterogeneous fact databases

Modern distributed fact databases are heterogeneous and autonomous. Their heterogeneity is due to many reasons, including varying data models, data structures, attribute naming conventions, units of measurement or naming of data values, composition of data as attributes, technical representation of data, abstraction levels of data, etc. Database autonomity means that the database users have hardly any means for reducing such heterogeneity. Present information retrieval (IR) systems either provide no support for overcoming such heterogeneity or their support is insufficient and difficult to utilize. In this paper we offer integrated and powerful data conversion, aggregation and deductive techniques for advanced IR in such environments. These techniques allow the users to overcome data inconsistency due to units of measurement or naming of data values, composition of data as attributes, abstraction levels of data, and difficulties related to deductive use of hierarchically classified data. In complex situations, all these inconsistencies appears together. Therefore we also show how these techniques are integrated into a powerful query language which has been implemented in Prolog in a workstation environment.

Abstract of Advanced Query Formulation in Deductive Databases

A novel operation-oriented framework for deductive databases is introduced. Several types of end user queries to deductive databases are classified, and sample queries are used to demonstrate how they can be expressed in our framework. The sample queries and their sample evaluations show essentially reduced user effort and essentially increased user capability in the expression of advanced queries in deductive databases. These are also necessary features in modern information retrieval from fact databases. We establish also criteria for advanced query formulation in deductive databases from the end-user viewpoint and analyze failures of conventional and present deductive DBMSs in meeting them.

Keywords: Knowledge-based retrieval, deductive databases, relational databases, knowledge representation, integration of recursive and non-recursive processing, entity types and instances.

Abstract of Operation-Oriented Query Language Approach for Recursive Queries - Part1. Functional Definition, Information Systems, Vol. 17, no. 1, 49- 75, 1992.

So far the aspects related to efficient processing have dominated the research on recursive queries. In this paper we consider how the formulation of recursive queries can be made easier from the view point of the non-professional user - also in the context of complex recursive queries. It is obvious that the conventional rule-based way of defining is too hard and cumbersome for many non-professional users. We provide operations at a high abstraction level in terms of which the user can formulate his recursive queries in a compact and convenient way. In our approach recursive processing is needed for constructing transitive relationships among data. In practice, it is often very important to compute transitive relationships among several union- compatible binary relations instead of one binary relation as usual. We define the operations so that they are able to manipulate transitive relationships among several relations. For the changing needs of the user our approach contains three kinds of operations: relation-oriented, node-oriented and path-oriented operations. In this paper we specify a functional language consisting of operations of these types and give several examples on how the user can formulate his recursive queries in terms of this language. We also discuss its role in deductive databases, i.e. its integration with processing based on an extensional database.

Keywords: Deductive databases, recursive queries, transitive relationships, knowledge representation, functional specification.

Abstract of Operation-Oriented Query Language Approach for Recursive Queries - Part2. Prototype Implementation and Its Integration with Relational Databases,Information Systems, Vol. 17, no. 1, 77-106, 1992.

In terms of our operation-oriented language introduced in [1] the non-professional user can formulate queries which find transitive relationships among objects. In our approach the user can make these kinds of queries without mastering recursive definition techniques. In this paper we consider how our operation-oriented language can be implemented on the basis of the rule-oriented approach. The rule-oriented implementation contains several recursive definitions but this definition level is invisible to the user. The rule-based prototype implementation is defined in Prolog. For the prototype implementation we propose the use of structural objects such as objects of type tuple, map and set. In terms of these objects the prototype can be defined in a compact and systematic way. Likewise, a Prolog-based way of parsing and evaluating functional expressions is developed. The integration of our operation- oriented language with the extensional database (EDB) based on the relational model is also considered. Any node-oriented expression generated by our language is integrated with relational processing using a restriction operation tailored for this purpose. We discuss how the interface of our prototype can be utilized in deductive databases based on both the heterogeneous and homogeneous approach. We also give a prototype implementation for the generalized aggregation operation introduced in Part I which involves transitive computation. Now relational processing can be utilized in the implementation of its EDB-dependent aspects.

Keywords: Deductive databases, recursive queries, knowledge representation, Prolog programming, logic grammars, prototyping, integration of recursive and non-recursive processing.

Abstract of Deductive Information Retrieval based on Classifications

Modern fact databases contain abundant data classified through several classifications. Typically users must consult these classifications in separate manuals or files thus making their effective use difficult. Contemporary database systems do little to support deductive use of classifications. In this paper we show how deductive data management techniques can be applied to the utilization of data value classifications. Computation of transitive class relationships is here of primary importance. We de- fine a representation of classifications which supports transitive computation and present an operation-oriented deductive query language tailored for classification- based deductive information retrieval. The operations of this language are on the same abstraction level as relational algebra operations and can be integrated with these to form a powerful and flexible query language for deductive information retrieval. We define the integration of the operations and demonstrate the usefulness of the language in terms of several sample queries.

Keywords: fact databases, information retrieval, classifications, deduction.

Abstract of General value Conversion and Aggregation Operations: Definition and Integration with Relational, Entity-Based and Deductive Data Retrieval Techniques

Modern distributed database environments are characterized by heterogeneity and autonomity. Their heterogeneity is due to many reasons, including varying data models, data structures, attribute naming conventions, units of measurement or naming of data values, composition of data as attributes, technical representation of data, abstraction levels of data, etc. Often many data item values are based on clas- sifications which the users must consult in manuals or separate files. Database autonomity means that the database users have hardly any means for reducing such heterogeneity in the databases. Present systems either provide no support for overcoming such heterogeneity or their support is insufficient and difficult to utilize. In this paper we define general value conversion and aggregation operations precisely and offer an integrated general query language which is based on powerful value conversion and aggregation, relational and entity-based data retrieval operations, and deductive techniques for advanced information retrieval in such environments. These techniques allow the users to overcome data inconsistency due to units of measurement or naming of data values, composition of data as attributes, abstraction levels of data, and difficulties related to deductive use of the classifications applied on the data. In complex situations, all these inconsistencies appear together. Therefore we give several examples on integrating the techniques together. The value conversion and aggregation operations are defined generally as relational operations, i.e. they can be applied on relations and they yield relations as their results. The value conversion operation provides unit of measurement -related transparency. It supports very versatile conversion (including conversion of compound attributes) and checks automatically the derivability of conversion requests. The conversion expressions require minimal information from the user. The data aggregation operation provides abstraction level transparency. It supports, among others, multiple consequtive aggregation levels and hierarchical reclassification of the classification attributes determining the aggregation levels. The integration of the value conversion and aggregation, relational and entity-based data retrieval operations, and deductive operations allows free mixing and unlimited levels of nesting of the operations. Interfaces between different types of operations are handled by simple type conversion functions. These operations and their integration, based on logic grammars, have been implemented in Prolog in a workstation environment.

Keywords: relational databases, entity types, heterogeneous databases, data inconsistency, value conversion, data aggregation, deduction.

Abstract of an Entity-based Approach to Query Processing in Relational databases PART I : Entity type representation

An entity-based query interface to relational databases is developed. The interface combines some object-oriented features with the strengths of universal relation DBMSs (UR-DBMSs) by a value-oriented entity representation and provides enhanced logical data independence. It provides a high-level representation of complex entity types and hides their implementation in a relational database. It also supports a declarative entity- based query language of the level of QUEL (described in Part II). The key features of the interface are : 1) an entity type representation and associated operations which allow the derivation of the entity types of the results of entity-based queries, and 2) an unambiguous and optimizing solution to the query interpretation problem of UR-DBMSs by an entity-based window generator. The window generator constructs RA expressions which can be evaluated by relational DBMSs (RDBMSs). The interface is specified in a formal and general way. It has many essential benefits, which support further processing of query results , improve query efficiency, clarify query semantics, enhance logical data independence, and allows use of existing RDBMS software by interfacing them to the entity level processing in a systematic way. It separates the entity type and relational levels into different domains and integrates them together through a well-defined interface. The entity types as such provide a good platform for type hierarchies and property inheritance in them. The interface exploits fully and easily the optimization capabilities of universal relation-based systems. The entity types provide the users with a high-level and natural view of the database. The users express their queries in terms of the entity types. This simplifies the ex- pression of complex queries considerably w.r.t. conventional query systems. The interface exploits this knowledge in an effective way.

Abstract of An Entity-based Approach to Query Processing in Relational Databases Part I I : Entity Query Construction and Updating

A declarative entity-based query language called the E-TRC for relational databases is presented and the construction and evaluation process of RA queries for its expressions is developed. This extends the value-oriented entity representation and the entity- based window generator for entity type projections of Part I. It is also shown how entity-level update transactions can be interpreted in a logical and consistent way and targeted to suitable relations while maintaining database integrity. The query construction and evaluation process derives the entity type and instance for query results automatically. The construction process solves query interpretation problems and improves query efficiency e.g. by rejecting semantically incorrect interpretations. The semantics of query results are thus also clear and accurate. This facilitates the formulation of a complex queries which become simpler and more comprehensible than corresponding RA expressions. The declarativeness of the E-TRC increases its user-friendliness. The expressive power of E-TRC is of the level of Quel. Disjunctions are allowed in the predicates of E-TRC. This increases its expressive power and extends optimization beyond conjunctive queries. Because the query construction process constructs RA expressions, they can be optimized and evaluated by existing well-tested RDBMSs. The query construction process defines the semantics of the E-TRC language formally in terms of equivalent RA expressions. The entity types provide the users with a high-level and natural view of the database. The users express all query and update transactions in terms of the entity types. This simplifies the expression of complex transactions considerably w.r.t. conventional systems. The interface exploits this knowledge in an effective way.

Abstract of A Form-based User Interface for NF2 Relations and Its Implementation Strategy

It has been widely recognized that query formulation in a SQL-like query language extended to the NF2 relational model requires large nested expressions in the context of complex queries. This means that query formulation, from the view point of the user, resembles rather the design of an algorithm than a nonprocedural specification. In this paper we propose a truly declarative user interface which minimizes the user effort in query formulation. In our approach the user describes the structure of the result of the query in a straightforward way without specifying, as usually, those restructuring operations on the basis of which the result is derived from the source NF2 relation. We show that query formulation based on our interface is simple and compact - also in the context of complex queries. In this paper we define a query processing strategy based on this interface. Because our interface has been intended to simplify formulation of complex queries the starting point of our query processing strategy is that existing relationships among data have to be restructred considerably when producing the query result. Our query processing strategy is based on such a calculus which is able to construct an NF2 relation from the representations of atomic-valued attributes or the smallest data units in the NF2 relational model. The data structures allowed by the calculus, called nf2-structures, describe both the schema and instance levels explicitly and bind them together by an indexing mechanism. Therefore our calculus has the pleasant feature that it performs all processing on the schema and instance levels at the same time. We can characterize our approach as an object-based processing strategy because all data processed by the calculus are modelled structurally as objects of type tuple, set, map or tree. We pay also attention to a variety of features in our query processing strategy which support its main memory implementation.

Categories and Subject Descriptors: H.2.3 [Database Management]: Languages-query languages; H.2.4 [Database Management]: Systems-query processing General Terms: Algorithms, Design, Human Factors, Languages, Performance Additional Key Words and Phrases: Formal specification, NF2 relations, query formulation, query processing strategy, structural objects

Abstract of Prolog-based Implementation of a Straightforward NF2 Relational Query Interface

It has been widely recognized that the proposed user-oriented NF2 (Non-First- Normal-Form) relational query languages such as different SQL extensions are cumbersome to use from view point of an ordinary end-user. This is because the user usually has to formulate large nested expressions in order to specify how the result NF2 relation is derived from the source NF2 relation(s). The NF2 relational query interface in this paper is based on a different approach. In it the user describes only the structure of the result NF2 relation in a straightforward and intuitive way. This starting point of our interface affords the possibility of formulating queries in a compact and truly declarative manner - also in those cases which require considerable restructuring among data. In this paper we consider the Prolog-based implementation of the query processing strategy of our interface. Special attention is paid to those principles and techniques in terms of which the representation and manipulation of complex structural relationships of NF2 relations can be managed in Prolog. The representation of NF2 relations and the query processing strategy have been designed to support main memory oriented implementation.

Key Words: NF2 relational model, User interface, Query processing, Logic programming, Prolog-based knowledge representation

Abstract of An NF2 Relational Interface with Aggregation Capability for Document Retrieval, Restructuring and Analysis

Complex documents are used in many environments, including information retrieval (IR). Complex documents contain subdocuments, which may contain further subdocuments, etc. Therefore powerful tools are needed to facilitate their retrieval, restructuring, and analysis. Existing IR systems are poor in complex document restructuring and data aggregation. However, in practice, IR system users would often want to obtain aggregation information on subdocuments of complex documents. In this paper we address this problem and provide a truly declarative and powerful interface for the users. Our interface is based on the non- first-normal-form (NF2) relational model. It allows intuitive and systematic modeling of complex documents.

Abstract of A Straightforward NF2 Relational Interface with Applications in Information Retrieval

In information retrieval (IR) there is a need for greater structural expressiveness than that provided by ordinary retrieval systems or the ordinary relational model. Especially hierarchical structures are usual in IR applications. Therefore the non- first-normal-form (NF2) relational model often is a more natural and intuitive way to model data of IR applications than the pure relational model. Because many-to-many relationships often exist among real world entities of IR applications it is impossible to find a stable hierarchical structure which would be suitable to all needs of users. This means that a tool is needed which has a powerful restructuring capability. In other words it has to be able to produce for the user result NF2 relations in which hierarchical relationships among data have been organized in a way which is drastically different from that in the source NF2 relations. In this paper we classify typical data restructuring tasks in an IR environment and give several examples on their specifications. It has been widely recognized that NF2 relational query formulation with conventional query languages is too cumbersome for ordinary end users. In order to simplify NF2 relational query formulation we have developed and implemented a novel user interface. We show that query specification in this interface remains compact and truly declarative - also in the context of complex NF2 relational queries.

Abstract of CQL : A QBE-like Visual Query Language with Recursion for Data Classification

Data classification is an essential part in many database applications. In data classification, transitive relationships among classified data have an important role. The computation of transitive relationships is beyond the traditional data models because it presupposes the possibility of recursive definition. In this paper we develop a high- level visual QBE-like query language, called CQL (Classification Query Language), which is able to manipulate transitive relationships with minimal user effort. The language incorporates ordinary relations as well as hierarchical classifications which can be used transitively / recursively. Relations and classifications are represented in the visual interface through relation and classification skeletons. All query formulation in the visual language is QBE-like, i.e. based on the intuitive way of inserting constant values and sample values into the skeletons. The use of relations and classifications is integrated seamlessly with unlimited nesting depth. The abstraction level of the visual constructs of the language, relations and hierar- chical classifications, is high and their interpretation is obvious in many application domains. The visual language embeds recursion into concepts of classifications which can be interpreted as such in the application domain. Recursive definition is totally hidden from the users. Therefore users' query formulation in the visual language is both easy and safe. At the same time the language provides new expressive power that cannot be provided by relational query languages. The interpretation of CQL expressions into the internal intermediate representation is described and the translation of the intermediate expressions into the expressions of a textual, operation-oriented query language is defined. The proposed visual query language has been implemented in the homogeneous approach in our experimental Prolog-based deductive database system. The implementation of the visual language in the heterogeneous approach in relational database environments is also considered.

Abstract of The Implementation of the Visual Query Language CQL for Transitive Computation

CQL (Classification Query Language) is a high-level visual QBE-like query language with a great expressive power. The implementation of the language described in this paper is intented for data classification. In data classification, transitive relationships among classified data have an important role. The computation of transitive relationships is beyond the traditional data models. Recursion is a natural way of defining transitive relationships. The CQL language incorporates ordinary relations as well as hierarchical classifications. Relations and classifications are represented in the visual interface through relation and classification skeletons. All query formulation in the visual language is QBE-like, i.e. based on the intuitive way of filling constants and sample values into the skeletons. The use of relations and classifications is integrated seamlessly so that relational and classification expressions can be nested freely with each other without limiting nesting levels. The visual language embeds recursion into concepts of classifications which can be interpreted as such in the application domain. Recursive definition is totally hidden from the users. Therefore users' query formulation in CQL is both easy and safe. The implementation of CQL is based on relational algebra and a set of direction-oriented operations on transitive relationships (e.g., multiple hierarchical classifications). Each direction-oriented operation can be performed among a collection of binary relations representing transitive rela- tionships. The benefit of these operations is that the computation of the transitive closure of one large binary relation can be avoided. Both the direction of computation and subsets of the collection of binary relations have obvious semantic interpretations in many application domains. The translation process of visual CQL expressions into expressions of the operation-oriented query language is presented. CQL has been implemented on the basis of our experimental deductive database system which has been implemented in a homogeneous way. Also the implementation of CQL in the heterogeneous way is outlined.

Abstract of An NF2 Relational Interface for Document Retrieval, Restructuring and Aggregation

Complex documents are used in many environments, e.g., information retrieval (IR). Such documents contain subdocuments, which may contain further subdocuments, etc. Powerful tools are needed to facilitate their retrieval, re- structuring, and analysis. Existing IR systems are poor in complex document restructuring and data aggregation. However, in practice, IR system users would often want to obtain aggregation information on subdocuments of complex documents. In this paper we address this problem and provide a truly declarative and powerful interface for the users. Our interface is based on the non-first-normal-form (NF2) relational model. It allows intuitive and systematic modeling of complex documents.

Abstract of The Processing Strategy for the Frc-interface

The idea of the frc (form-relations-conditions) - interface is to reduce the user effort in the NF2 (Non-First-Normal-Form) relational query formulation considerably. In the frc-interface the user only describes the structure of the result NF2 relation in a straightforward and intuitive way without specifying in any way how the result NF2 relation is derived from the source NF2 relations. The lack of explicit restructuring expressions from the frc-interface means that query processing must be based on the different approach used in such query languages (e.g. different SQL extensions made for the NF2 relational model) in which the user specifies the needed restructuring among data explicitly. In this paper we introduce our query processing strategy of the frc-interface which has been implemented in Prolog. Its kernel is a calculus consisting of two constructors. By applying these constructors recursively to atomic-valued attribute representations any NF2 relation can be constructed. Our calculus-based approach affords the possibility of performing several operations at the same time which gives a good starting point for efficient implementation. In the paper the optimization process used to manipulate several NF2 relations are described.

Keywords: NF2 relational model, User interface, Query processing, Logic programming, Prolog-based knowledge representation