Null values in nested relational databases

Summary The desire to extend the applicability of the relational model beyond traditional data-processing applications has stimulated interest in nested or non-first normal form relations in which the attributes of a relation can take on values which are sets or even relations themselves. In this paper, we study the role of null values in the nested relational model using an open world assumption. We extend the traditional theory and study the properties of extended operators for nested relations containing nulls. The no-information, unknown, and non-existent interpretation of nulls are discussed and the meaning of empty set is clarified. Finally, contrary to several previous results, we determine that the traditional axiomatization of functional and multivalued dependencies is valid in the presence of nulls.Currently with the Air Force Institute of Technology, AFIT/ENG, Wright-Patterson AFB, OH 45433, USAResearch partially supported by an IBM Faculty Development A ward and NSF grant DCR-8507224     

Infinitary rewriting: closure operators, equivalences and models

Infinitary Term Rewriting allows to express infinite terms and transfinite reductions that converge to those terms. Underpinning the machinery of infinitary rewriting are closure operators on relations that facilitate the formation of transfinite reductions and transfinite equivalence proofs. The literature on infinitary rewriting has largely neglected to single out such closure operators, leaving them implicit in definitions of (transfinite) rewrite reductions, or equivalence relations. This paper unpicks some of those definitions, extracting the underlying closure principles used, as well as constructing alternative operators that lead to alternative notions of reduction and equivalence. A consequence of this unpicking is an insight into the abstraction level at which these operators can be defined. Some of the material in this paper already appeared in Kahrs (2010). The paper also generalises the notion of equational model for infinitary rewriting. This leads to semantics-based notions of equivalence that tie in with the equivalences constructed from the closure operators.     

Uncertainty in a nested relational database model

Some database models have already been developed to deal with complex values but they have constrains that data stored is precise and queries are crisp. However, as many researchers have pointed out, there is a need to present, manipulate, and query complex and uncertain data of various non-traditional database applications such as oceanography, multimedia, meteorology, office automation systems, engineering designs, expert database systems and geographic information systems. In this paper, we present a logical database model, which is an extension of a nested relational data model (also known as an NF² data model), for representing and manipulating complex and uncertain data in databases. We also introduce a possible physical representation of such complex and uncertain values in databases and describe the query processing of the model that we discuss here.     

Addendum to Null values in nested relational databases

We define a new operator, decomposition projection, and show that extended projection is a precise generalization of decomposition projection with respect to unnesting, and that null-extended projection is a precise generalization of decomposition projection with respect to unnesting and PNF possibility function POSS.     

The similarity-aware relational database set operators

Identifying similarities in large datasets is an essential operation in several applications such as bioinformatics, pattern recognition, and data integration. To make a relational database management system similarity-aware, the core relational operators have to be extended. While similarity-awareness has been introduced in database engines for relational operators such as joins and group-by, little has been achieved for relational set operators, namely Intersection, Difference, and Union. In this paper, we propose to extend the semantics of relational set operators to take into account the similarity of values. We develop efficient query processing algorithms for evaluating them, and implement these operators inside an open-source database system, namely PostgreSQL. By extending several queries from the TPC-H benchmark to include predicates that involve similarity-based set operators, we perform extensive experiments that demonstrate up to three orders of magnitude speedup in performance over equivalent queries that only employ regular operators.     

Concerning ordered mutation testing of relational operators

The aim of this paper is to correct a misapprehension concerning mutation testing of relational operators in imperative programming languages. An apparently plausible, but fallacious argument is stated concerning the order in which mutants are best considered. Subsequently, a counter-example is presented which disproves the argument.     

Well-definedness and semantic type-checking for the nested relational calculus

The well-definedness problem for a programming language consists of checking, given an expression and an input type, whether the semantics of the expression is defined for all inputs adhering to the input type. A related problem is the semantic type-checking problem which consists of checking, given an expression, an input type, and an output type whether the expression always returns outputs adhering to the output type on inputs adhering to the input type. Both problems are undecidable for general-purpose programming languages. In this paper we study these problems for the Nested Relational Calculus, a specific-purpose database query language. We also investigate how these problems behave in the presence of programming language features such as singleton coercion and type tests.     

Time-based operators for relational algebra query languages

We present a new approach for historical relational algebra languages based upon generalized logic for Boolean and comparison operators and a temporal modification of the standard relational algebra operators. Historical versions of standard (snapshot) relational algebra operators based upon this generalized logic are presented. The temporal modification employs a logic that operates on sets of value/time-interval pairs and which can be applied to snapshot as well as historical databases. Our emphasis is that the generalized operators can be used to enrich existing historical query languages and to provide an easier and more natural time-based interface. Using the generalized operators, users can express their queries more naturally, succinctly and elegantly. Examples are presented which illustrate that the modified operators offer a good degree of flexibility in expressing different temporal requirements.     

Atlas: a nested relational database system for text applications

Advanced database applications require facilities such as text indexing, image storage, and the ability to store data with a complex structure. However, these facilities are not usually included in traditional database systems. In this paper we describe Atlas, a nested relational database system that has been designed for text-based applications. The Atlas query language is TQL, an SQL-like query language with text operators. The query language is supported by signature file text indexing techniques, and by a parser that can be configured for different text formats and even some foreign languages. Atlas can also be used to store images and audio     

Attributed relational graph matching based on the nested assignment structure

In this paper, we propose a new ARG matching scheme based on the nested assignment structure to assess the similarity between two attributed relational graphs (ARGs). ARGs are represented by nodes and edges containing unary attributes and binary relations between nodes, respectively. The nested assignment structure consists of inner and outer steps. In the inner step, to form a distance matrix, combinatorial differences between every pair of nodes in two ARGs are computed by using an assignment algorithm. Then, in the outer step, a correspondence between nodes in the two ARGs is established by using an assignment algorithm based on the distance matrix. The proposed ARG matching scheme consists of three procedures as follows: first, in the initializing procedure, the nested assignment structure is performed to generate an initial correspondence between nodes in two ARGs. Next, the correspondence is refined by iteratively performing the updating procedure, which also utilizes the nested assignment structure, until the correspondence does not change. Finally, the verifying procedure can be performed in case that some nodes to be matched in the two ARGs are missing. From experimental results, the proposed ARG matching scheme shows superior matching performance and localizes target objects robustly and correctly even in severely noisy and occluded scenes.     

关系代数派生算子语义表达式间等价性证明

关系代数的派生算子在关系数据库查询语言中得到了广泛应用。它们的语义有两种常见的表示方式,一种是基于原始算子的表达式,一种是基于一阶逻辑的表达式。但有关的文献资料都没有给出这两种表达式等价性的严格证明。文章尝试通过一系列等价变换,证明派生算子语义的这两种表达式间的等价性。从派生算子(主要是除算子)语义的原始算子表达式出发,根据关系代数表达式的特点,通过一步步的等价变换,得到派生算子语义的一阶逻辑表达式。所使用的变换方法能为关系代数表达式的正确性证明打下基础。     

Extended relational operators for statistical data manipulations in medical databases

Conventional relational database management systems fail to address three features of statistical data management in a biomedical/clinical database, namely, that (1) statistical and medical data (SMD) require a great deal of space and need to be stored in a reduced form with minimal duplication; indeed, SMD have many derived/calculated and summary statistics that make the number of attributes in a relation (i.e., a set of records) grow rapidly and dynamically; (2) most SMD have hierarchical structures that are difficult to manage using the relational data model since SMD are stored in separate relations for duplication and space considerations; and (3) the management of SMD is made easier if it is possible to reorganize relations or group data, a capability lacking in conventional relational database management systems. In this paper, we (1) introduce five extended relational operators, (lattice) NEST, (lattice) UNNEST, MERGE, SPREAD, and GEN, to reorganize relations; (2) integrate the extended operators with conventional relational algebra and introduce the concept of the lattice relational model; and (3) give applications of the extended relational operators and the lattice relational model in solving the problems of statistical data manipulation in medical databases.     

Algebraic identities and query optimization in a parametric modelfor relational temporal databases

This paper presents algebraic identities and algebraic query optimization for a parametric model for temporal databases. The parametric model has several features not present in the classical model. In this model, a key is explicitly designated with a relation, and an operator is available to change the key. The algebra for the parametric model is three-sorted; it includes 1) relational expressions that evaluate to relations, 2) domain expressions that evaluate to time domains, and 3) Boolean expressions that evaluate to TRUE or FALSE. The identities in the parametric model are classified as weak identities and strong identities. Weak identities in this model are largely counterparts of the identities in classical relational databases. Rather than establishing weak identities from scratch, a meta inference mechanism, introduced in the paper, allows weak identities to be induced from their respective classical counterpart. On the other hand, the strong identities will be established from scratch. An algorithm is presented for algebraic optimization to transform a query to an equivalent query that will execute more efficiently     

Elimination of redundant operations in relational queries with general selection operators

The optimization of relational expressions concerning the elimination of “redundant” operations has been dealt with sofar for a limited class of expressions that puts restrictions on the selection operators involved. We propose a solution for the case of arbitrary selection criteria.     

DFL: A dataflow language based on Petri nets and nested relational calculus

In this paper we propose DFL—a formal, graphical workflow language for dataflows, i.e., workflows where large amounts of complex data are manipulated, and the structure of the manipulated data is reflected in the structure of the workflow. It is a common extension of (1) Petri nets, which are responsible for the organization of the processing tasks, and (2) nested relational calculus, which is a database query language over complex objects, and is responsible for handling collections of data items (in particular, for iteration) and for the typing system. We demonstrate that dataflows constructed in a hierarchical manner, according to a set of refinement rules we propose, are semi-sound, i.e., initiated with a single token (which may represent a complex scientific data collection) in the input node, terminate with a single token in the output node (which represents the output data collection). In particular they never leave any “debris data” behind and an output is always eventually computed regardless of how the computation proceeds.     

Algebraic models of deviant modal operators based on de Morgan and Kleene lattices

An algebraic model of a kind of modal extension of de Morgan logic is described under the name MDS5 algebra. The main properties of this algebra can be summarized as follows: (1) it is based on a de Morgan lattice, rather than a Boolean algebra; (2) a modal necessity operator that satisfies the axioms N, K, T, and 5 (and as a consequence also B and 4) of modal logic is introduced; it allows one to introduce a modal possibility by the usual combination of necessity operation and de Morgan negation; (3) the necessity operator satisfies a distributivity principle over joins. The latter property cannot be meaningfully added to the standard Boolean algebraic models of S5 modal logic, since in this Boolean context both modalities collapse in the identity mapping. The consistency of this algebraic model is proved, showing that usual fuzzy set theory on a universe U can be equipped with a MDS5 structure that satisfies all the above points (1)-(3), without the trivialization of the modalities to the identity mapping. Further, the relationship between this new algebra and Heyting-Wajsberg algebras is investigated. Finally, the question of the role of these deviant modalities, as opposed to the usual non-distributive ones, in the scope of knowledge representation and approximation spaces is discussed.     

Optimizing relational queries in connection hypergraphs: nested queries, views, and binding propagations

We optimize relational queries using connection hypergraphs (CHGs). All operations including value-passing between SQL blocks can be set-oriented. By introducing partial evaluations, reordering operations can be achieved for nested queries. For a query using views, we merge CHGs for the views and the query into one CHG and then apply query optimization. Furthermore, we may simulate magic sets methods elegantly in a CHG. Sideways information-passing strategies (SIPS) in a CHG amount to partial evaluations of SIPS paths. We introduce the maximum SIPS strategy, which performs SIPS for all bindings and all SIPS paths for a query. The new method has several advantages. First, the maximum SIPS strategy can be more efficient than the previous SIPS based on simple heuristics. Second, it is conceptually simple and easy to implement. Third, the processing strategies may be incorporated with the search space for query execution plans, which is a proven optimization strategy introduced by System R. Fourth, it provides a general framework of query optimization and may potentially be used to optimize next-generation database systems. Received September 1, 1993 / Accepted January 8, 1996     

A priori identification of preferred alternatives of OWA operators by relational analysis of arguments

We present a reverse decision-aiding method that is distinct from previously reported ordered weighted averaging (OWA) aggregation methods. The proposed method is implemented in two phases. In the first phase, potentially best alternative, defined as one having any weighting vector that enables it to be at least as good as the others, is identified. In the second phase, the maximum and the minimum attitudinal characters for such an alternative are computed as the highest and the lowest values which it can attain under the weights-set identified in the first phase. These two phases are governed only by the relational analysis of input arguments, without soliciting the decision-maker to supply a specific attitudinal character. The proposed method can be applied to cases when it is difficult to obtain a precise attitudinal character and when, even if a precise one is obtained, the OWA operator weights are different, depending on the weights generating methods adopted. Further, if uncertain attitudinal character in the form of the interval number is available, its projection into the results of the proposed method yields less alternatives of consideration, in some cases, a single best alternative. The proposed method also allows for a priori identification of alternatives prone to change at a particular range of attitudinal character.     

Four equivalent equivalences of reductions

Two co-initial reductions in a term rewriting system are said to be equivalent if they perform the same steps, albeit maybe in a different order. We present four characterisations of such a notion of equivalence, based on permutation, standardisation, labelling and projection, respectively. We prove that the characterisations all yield the same notion of equivalence, for the class of first-order left-linear term rewriting systems. A crucial rôle in our development is played by the notion of a proof term.