Safety, domain independence and translation of complex value database queries

This paper considers the theory of database queries on the complex value data model with external functions. Motivated by concerns regarding query evaluation, we first identify recursive sets of formulas, called embedded allowed, which is a class with desirable properties of “reasonable” queries.We then show that all embedded allowed calculus (or fix-point) queries are domain independent and continuous. An algorithm for translating embedded allowed queries into equivalent algebraic expressions as a basis for evaluating safe queries in all calculus-based query classes has been developed.Finally we discuss the topic of “domain independent query programs”, compare the expressive power of the various complex value query languages and their embedded allowed versions, and discuss the relationship between safety, embedded allowed, and domain independence in the various calculus-based queries.     

Fuzzy database query languages and their relational completenesstheorem

Two fuzzy database query languages are proposed. They are used to query fuzzy databases that are enhanced from relational databases in such a way that fuzzy sets are allowed in both attribute values and truth values. A fuzzy calculus query language is constructed based on the relational calculus, and a fuzzy algebra query language is also constructed based on the relational algebra. In addition, a fuzzy relational completeness theorem such that the languages have equivalent expressive power is proved     

Relational theory of queries

In this paper a new presentation of the relational theory of queries will be given. Both the relational algebra and the (domain) relational calculus will be systematically derived from first-order logic. The connections between logic, algebra and calculus will become extremely simple: e.g. the relational algebra will be isomorphic with a subset of relational calculus. Also some theoretical results about the completeness of the relational query languages will be presented. Both the relational calculus and the relational algebra will be extended to contain aggregate functions.     

Query languages for relational multidatabases

With the existence of many autonomous databases widely accessible through computer networks, users will require the capability to jointly manipulate data in different databases. A multidatabase system provides such a capability through a multidatabase manipulation language, such as MSQL. We propose a theoretical foundation for such languages by presenting a multirelational algebra and calculus based on the relational algebra and calculus. The proposal is illustrated by various queries on an example multidatabase. It is shown that properties of the multirelational algebra may be used for optimization and that every multirelational algebra query can be expressed as a multirelational calculus query. The connection between the multirelational languages and MSQL, the multidatabase version of SQL, is also investigated.     

A relational calculus with set operators, its safety, andequivalent graphical languages

The authors propose a relational calculus (RC/S) which uses set comparison and set manipulation operators to replace universal quantifiers and negations. It is argued that compared to the Codd relational calculus (RC), RC/S queries are easier to construct and comprehend. It is proved that the expressive power of RC is equivalent to the expressive power of RC/S, and algorithms for translating an RC query into an RC/S query and vice versa are given. A safe RC/S query is defined as one that has finite output and can be evaluated in finite time. Then a subset of RC/S queries, called RC/S* is defined, and it is proved that RC/S* is safe. RC/S* is compared to the existing largest safe subsets of RC, i.e. the evaluable formulas and the allowed formulas. Algorithms are given to transform any evaluable formula into an RC/S* query, and some RC/S* formulas that are not evaluable are given. RC/S* queries can be directly implemented using a graphical language similar to Query-by-Example (QBE). Two different graphical languages are described that are equivalent to the RC/S* in expressive power, and these languages are compared to QBE     

Foundations for object-oriented query processing

A minimal framework for an object-oriented query language standard should (1) include a formal definition of a high-level data model and the syntax and semantics of associated query languages, (2) provide the functionality of relational query languages, and (3) support proofs of correctness of transformations for logical query optimization. In this paper, a high-level conceptual model for object-oriented query processing is discussed; the model includes widely-used structural abstractions such as the isa relationship, associations (properties) between complex objects and complex objects/values, and inheritance of properties. A formal, algebraic query language for the model, inspired by relational algebra, is presented. Operators of the algebra allow queries based on values, queries that manipulate entire objects, and queries that construct new objects from existing objects/values. All queries retain connections to existing database objects, providing logical access paths to data. Each query result is a class, so the algebra has the closure property. The intensional and extensional results of query operators are summarized. Two forms of logical query optimization supported by the query algebra are outlined: algebraic transformations and classifier-based optimizations (optimizations which employ inclusion and exclusion dependencies between classes).     

A Safe Relational Calculus for Functional Logic Deductive Databases

In this paper, we present an extended relational calculus for expressing queries in functional-logic deductive databases. This calculus is based on first-order logic and handles relation predicates, equalities and inequalities over partially defined terms, and approximation equations. For the calculus formulas, we have studied syntactic conditions in order to ensure the domain independence property. Finally, we have studied its equivalence w.r.t. the original query language, which is based on equality and inequality constraints.     

An object-oriented deductive language

We propose a logic for objects that captures the knowledge represented with the LAURE object-oriented language. The work is oriented toward efficient implementation and compilation of queries. A data model for object-oriented databases is presented, with a declarative logic language used to perform queries and positive updates on the database. The expressiveness of this language is reduced, compared to other propositions in the same field, by the use of purely Horn clauses. An equivalent relational algebra is given, from which a formal technique for performing positive updates, called differentiation, is obtained. Two algorithms are proposed that achieve a sound and complete resolution, either for a bottom-up evaluation or a top-down resolution. An efficient implementation of constraint resolution is presented in this framework.     

Equivalence and Normal Forms for the Restricted and Bounded Fixpoint in the Nested Algebra

The nested model is an extension of the traditional, “flat” relational model in which relations can also have relation-valued entries. Its “default” query language, the nested algebra, is rather weak, unfortunately, since it is only a conservative extension of the traditional, flat relational algebra, and thus can express only a small fraction of the polynomial-time queries. Therefore, it was proposed to extend the nested algebra with a fixpoint construct, but the resulting language turned out to be too powerful: many inherently exponential queries could also be expressed. Two polynomial-time restrictions of the fixpoint closure of the nested algebra were proposed: the restricted fixpoint closure (by Gyssens and Van Gucht) and the bounded fixpoint closure (by Suciu). Here, we prove two results. First we show that both restrictions are equivalent in expressive power. The proof technique relies on known encodings of nested relations into flat ones, and on a novel technique, called type substitution, by which we reduce the equivalence of the two restrictions to its obvious counterpart in the flat relational model. Second we prove that both the bounded fixpoint queries and the restricted fixpoint queries admit normal forms, in which the fixpoint occurs exactly once. The proof technique relies on a novel encoding method of nested relations into flat ones.     

Taxonomy-based relaxation of query answering in relational databases

Traditional information search in which queries are posed against a known and rigid schema over a structured database is shifting toward a Web scenario in which exposed schemas are vague or absent and data come from heterogeneous sources. In this framework, query answering cannot be precise and needs to be relaxed, with the goal of matching user requests with accessible data. In this paper, we propose a logical model and a class of abstract query languages as a foundation for querying relational data sets with vague schemas. Our approach relies on the availability of taxonomies, that is, simple classifications of terms arranged in a hierarchical structure. The model is a natural extension of the relational model in which data domains are organized in hierarchies, according to different levels of generalization between terms. We first propose a conservative extension of the relational algebra for this model in which special operators allow the specification of relaxed queries over vaguely structured information. We also study equivalence and rewriting properties of the algebra that can be used for query optimization. We then illustrate a logic-based query language that can provide a basis for expressing relaxed queries in a declarative way. We finally investigate the expressive power of the proposed query languages and the independence of the taxonomy in this context.     

Querying fuzzy relational databases through fuzzy domain calculus

In this paper we present a definition of a domain relational calculus for fuzzy relational databases using the GEFRED model as a starting point. It is possible to define an equivalent fuzzy tuple relational calculus and consequently we achieve the two query language levels that Codd designed for relational databases but these are extended to fuzzy relational databases: Fuzzy relational algebra (defined in the GEFRED model) and the fuzzy relational calculus which is put forward in this paper. The expressive power of this fuzzy relational calculus is demonstrated through the use of a method to translate any algebraic expression into an equivalent expression in fuzzy domain relational calculus. Furthermore, we include a useful system so that the degree to which each value has satisfied the query condition can be measured. Some examples are also included in order to clarify the definition. ©1999 John Wiley & Sons, Inc.     

Using FP as a query language for relational data-bases

FP is the programming language defined by J. Backus to demonstrate the virtues of functional programming as opposed to conventional programming in Von Neumann-like languages.In this paper we investigate the use of FP in the framework of relational data bases. In particular, we show how the language can be used to define base relations, to derive views from a collection of relations, and to express complex database queries.The language provides all capabilities of pure algebraic relational languages, but is considerably more powerful. As such, it can be used as a formal specification language to describe the semantics of queries expressed in relational languages, such as Query-By-Example. In addition the algebra of FP programs allows one to formally prove properties of such queries.     

一个并发对象演算

由于缺乏一个为人们接受的描述并发对象系统语义的形式化模型,开发面向对象程序设计语言的开发受到了很大的制约,为了给并发面向对象程序设计定义一个公共的语义框架,人们分别以π演算和ａｃｔｏｒ模型为基础进行了研究。     

Optimizing Queries with Object Updates

Object-oriented databases (OODBs) provide powerful data abstractions and modeling facilities but they usually lack a suitable framework for query processing and optimization. Even though there is an increasing number of recent proposals on OODB query optimization, only few of them are actually focused on query optimization in the presence of object identity and destructive updates, features often supported by most realistic OODB languages. This paper presents a formal framework for optimizing object-oriented queries in the presence of side effects. These queries may contain object updates at any place and in any form. We present a language extension to the monoid comprehension calculus to express these object-oriented features and we give a formal meaning to these extensions. Our method is based on denotational semantics, which is often used to give a formal meaning to imperative programming languages. The semantics of our language extensions is expressed in terms of our monoid calculus, without the need of any fundamental change to our basic framework. Our method not only maintains referential transparency, which allows us to do meaningful query optimization, but it is also practical for optimizing OODB queries since it allows the same optimization techniques applied to regular queries to be used with minimal changes for OODB queries with updates.     

RQL: a recursive query language

Different classes of recursive queries in the relational databases are identified. It is shown that existing proposals to extend the relational query languages are either not powerful enough to express queries in many of these classes or use nonfirst normal form constructs. RQL, a recursive database query language that can be used to express recursive queries on all the classes identified, is presented. RQL is based on the relational algebra. In addition to functions that correspond to the standard and extended relational algebra operators, RQL supports functions required to express general recursive queries. The elements of RQL and the ways in which they are used to formulate complicated, but useful, recursive queries are described. The effects of the extensions embodied in RQL on the termination of recursive query evaluation are discussed     

How to Comprehend Queries Functionally

Compilers and optimizers for declarative query languages use some form of intermediate language to represent user-level queries. The advent of compositional query languages for orthogonal type systems (e.g., OQL) calls for internal query representations beyond extensions of relational algebra. This work adopts a view of query processing which is greatly influenced by ideas from the functional programming domain. A uniform formal framework is presented which covers all query translation phases, including user-level query language compilation, query optimization, and execution plan generation. We pursue the type-based design—based on initial algebras—of a core functional language which is then developed into an intermediate representation that fits the needs of advanced query processing. Based on the principle of structural recursion we extend the language by monad comprehensions (which provide us with a calculus-style sublanguage that proves to be useful during the optimization of nested queries) and combinators (abstractions of the query operators implemented by the underlying target query engine). Due to its functional nature, the language is susceptible to program transformation techniques that were developed by the functional programming as well as the functional data model communities. We show how database query processing can substantially benefit from these techniques.     

A Generalized Implementation Method for Relational Data Sublanguages

A set of primitive operations on tuples is derived; it is shown that these operations are necessary and sufficient for the implementation tion of any language equivalent in power to the relational algebra. The translation of queries from a variety of relational languages into these tuple operations is discussed and illustrated with several examples. A method is given for the conversion of such a translated query into a network of processes and files. An optimization algorithm which operates on this network is described and demonstrated. Using this method, many different relational languages can be implemented using the same data management software; furthermore, the underlying software can be changed without requiring any changes at the user interface. This approach should yield great benefits in reduced cost and increased flexibility of implementation.     

Database query languages and functional logic programming

Functional logic programming is a paradigm which integrates functional and logic programming. It is based on the use of rewriting rules for defining programs, and rewriting for goal solving. In this context, goals, usually, consist of equality (and, sometimes, inequality) constraints, which are solved in order to obtain answers, represented by means of substitutions. On the other hand, database programming languages involve a data model, a data definition language and, finally, a query language against the data defined according to the data model. To use functional logic programming as a database programming language, (1) we will propose a data model involving the main features adopted from functional logic programming (for instance, handling of partial and infinite data), (2) we will use conditional rewriting rules as data definition language, and finally, (3) we will deal with equality and inequality constraints as query language. Moreover, as most database systems, (4) we will propose an extended relational calculus and algebra, which can be used as alternative query languages in this framework. Finally, (5) we will prove that three alternative query languages are equivalent.     

UnQL: a query language and algebra for semistructured data based on structural recursion

Abstract. This paper presents structural recursion as the basis of the syntax and semantics of query languages for semistructured data and XML. We describe a simple and powerful query language based on pattern matching and show that it can be expressed using structural recursion, which is introduced as a top-down, recursive function, similar to the way XSL is defined on XML trees. On cyclic data, structural recursion can be defined in two equivalent ways: as a recursive function which evaluates the data top-down and remembers all its calls to avoid infinite loops, or as a bulk evaluation which processes the entire data in parallel using only traditional relational algebra operators. The latter makes it possible for optimization techniques in relational queries to be applied to structural recursion. We show that the composition of two structural recursion queries can be expressed as a single such query, and this is used as the basis of an optimization method for mediator systems. Several other formal properties are established: structural recursion can be expressed in first-order logic extended with transitive closure; its data complexity is PTIME; and over relational data it is a conservative extension of the relational calculus. The underlying data model is based on value equality, formally defined with bisimulation. Structural recursion is shown to be invariant with respect to value equality. Received: July 9, 1999 / Accepted: December 24, 1999     

Semantic and pragmatic processing in FIDO: A flexible interface for data-base operations

This article deals with a flexible natural language interface to access data stored in a relational data base. This interface may prove of great value to the less sophisticated user.The FIDO system (Flexible Interface for Database Operations) is presented; it accepts queries issued in natural language (Italian) and translates them into relational algebra operations. FIDO is composed of a parser (not described in the paper), a two-level semantic network, which (among other things) expresses the correspondence between the natural language terms and the conceptual database objects, and a translator/optimizer, which translates the conceptual query into its logical equivalent (i.e. into a query expressed in terms of stored relations and their attributes). The article describes the main characteristics of the semantic network and addresses, in greater detail, the problem of query translation and optimization.The flexibility of FIDO is due to the complete independence of the semantic knowledge source from the logical schema of the data base. In fact, the logical schema can be designed on the basis of considerations not related to the overall structure of FIDO (e.g. the presence of particular types of applications that have to be implemented in a particularly efficient way). In principle, the (relational) data base could be preexistent with respect to the adoption of FIDO, in that the data structures used by the translator/optimizer and described in this paper are able to describe the correspondence between the conceptual model of the domain and different logical schemas.