QBD*: a graphical query language with recursion

A system to query databases using diagrams as a standard user interface is proposed. The system, called Query by Diagram* (QBD*), makes use of a conceptual data model, a query language on this model, and a graphical user interface. The conceptual model is the entity-relationship model. The query language, whose expressive power allows recursive queries, supports visual interaction. The main characteristics of the interface are ease of use and the availability of a rich set of primitives for schema selection and query formulation. The expressive power of QBD* and G⁺, which are the only languages allowing recursive queries to be expressed graphically are compared     

基于递归和表函数的一到多数据转换研究

针对关系表达式难以进行无限制一到多数据转换的问题,通过关系代数的扩展表达一到多数据转换,采用递归查询和表函数实现无限制一到多数据转换,在每个输入元组上产生一个或者多个输出元组。递归查询通过创建初始结果,递归获取结果集,并返回最终结果集;表函数声明变量集合,使用过程体和游标循环访问表,迭代输出元组。实验分析不同参数影响因素下有限制和无限制转换的不同方法,结果表明扩展方法能够改善系统性能。     

Bounded regular path queries in view-based data integration

In this paper we study the problem of deciding boundedness of (recursive) regular path queries over views in data integration systems, that is, whether a query can be re-expressed without recursion. This problem becomes challenging when the views contain recursion, thereby potentially making recursion in the query unnecessary. We define and solve two related problems of boundedness of regular path queries. One of the problems asks for the existence of a bound, and the other, more restricted one, asks if the query is bounded within a given parameter. For the more restricted version we show it PSPACE complete, and obtain a constructive method for optimizing the queries. For the existential version of boundedness, we show it PTIME reducible to the notorious problem of limitedness in distance automata. This problem has received a lot attention in the formal language community, but only exponential time algorithms are currently known.     

Extending SQL with general transitive closure and extreme valueselections

Many recursive query processing applications are still poorly supported, partly because implementations of general recursive capabilities are inefficient and hard to understand for users, partly because the approaches do not integrate well with existing query languages. An extension is proposed of the database language SQL for the processing of recursive structures. The new constructs are integrated in the view definition mechanism of SQL. Therefore, users with knowledge of SQL can take advantage of the increased functionally without learning a new language. The construct is based on a generalization of transitive closure and is formally defined. Because of the importance of extreme value sections, special constructs are introduced for the selection of tuples with minimal or maximal values in some attributes. Applying these selections on recursively defined views constitutes nonlinear recursion. By the introduction of special constructs for these selections, dealing with general nonlinear recursion can be avoided     

Efficient algorithms for shortest distance queries on special classes of polygons

The problem of finding a rectilinear minimum bend path (RMBP) between two designated points inside a rectilinear polygon has applications in robotics and motion planning. In this paper, we present efficient algorithms to solve the query version of the RMBP problem for special classes of rectilinear polygons given their visibility graphs. Specifically, we show that given an unweighted graph G = (V, E), with ¦V¦ = N and ¦E¦ = M, algorithms to preprocess G in linear space and time such that the shortest distance queries — queries asking for the distance between any pair of nodes in the graph — can be answered in constant time and space are presented in this paper. For the case of a chordal graph G, our algorithms give a distance which is at most one away from the actual shortest distance. When G is a K-chordal graph, our algorithm produces an exact shortest distance in O(K) time. We also present a non-trivial parallel implementation of the sequential preprocessing algorithm for the CREW-PRAM model which runs in O(log² N) time using O(N + M) processors. After the preprocessing, we can answer the queries in constant time using a single processor.     

Algebraic optimization of recursive queries

Over the past few years, much attention has been paid to deductive databases. They offer a logic-based interface, and allow formulation of complex recursive queries. However, they do not offer appropriate update facilities, and do not support existing applications. To overcome these problems an SQL-like interface is required besides a logic-based interface.

In the PRISMA project we have developed a tightly-coupled distributed database, on a multiprocessor machine, with two user interfaces: SQL and PRISMAlog. Query optimization is localized in one component: the relational query optimizer. Therefore, we have defined an eXtended Relational Algebra that allows recursive query formulation and can also be used for expressing executable schedules, and we have developed algebraic optimization strategies for recursive queries. In this paper we describe an optimization strategy that rewrites regular (in the context of formal grammars) mutually recursive queries into standard Relational Algebra and transitive closure operations. We also describe how to push selections into the resulting transitive closure operations.

The reason we focus on algebraic optimization is that, in our opinion, the new generation of advanced database systems will be built starting from existing state-of-the-art relational technology, instead of building a completely new class of systems.     

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     

The power of inequality semijoins

Semijoin is a relational operator used in many relational query processing algorithms. Semijoins can be used to “reduce” the database by delimitting portions of the database that contain data relevant to a given query. For some queries, there exist sequences of semijoins that delimit the exact portions of the database needed to answer the query. Such sequences are called full reducers.

This paper considers a class of queries called natural inequality queries (NI queries), and characterizes a subclass for which full reducers exist. We also present an efficient algorithm that decides whether an NI query lies within this subclass, and constructs a full reducer for the query. The NI queries are a subset of the aggregate-free, conjunctive queries of QUEL, and permit join clauses to include <, , =, , >.     

Similarity-based ranking and query processing in multimedia databases

Since media-based evaluation yields similarity values, results to a multimedia database query, Q(Y₁,…,Y_n), is defined as an ordered list S_Q of n-tuples of the form X₁,…,X_n. The query Q itself is composed of a set of fuzzy and crisp predicates, constants, variables, and conjunction, disjunction, and negation operators. Since many multimedia applications require partial matches, S_Q includes results which do not satisfy all predicates. Due to the ranking and partial match requirements, traditional query processing techniques do not apply to multimedia databases. In this paper, we first focus on the problem of “given a multimedia query which consists of multiple fuzzy and crisp predicates, providing the user with a meaningful final ranking”. More specifically, we study the problem of merging similarity values in queries with multiple fuzzy predicates. We describe the essential multimedia retrieval semantics, compare these with the known approaches, and propose a semantics which captures the requirements of multimedia retrieval problem. We then build on these results in answering the related problem of “given a multimedia query which consists of multiple fuzzy and crisp predicates, finding an efficient way to process the query.” We develop an algorithm to efficiently process queries with unordered fuzzy predicates (sub-queries). Although this algorithm can work with different fuzzy semantics, it benefits from the statistical properties of the semantics proposed in this paper. We also present experimental results for evaluating the proposed algorithm in terms of quality of results and search space reduction.     

Structural Recursion as a Query Language on Lists and Ordered Trees

XML query languages need to provide some mechanism to inspect and manipulate nodes at all levels of an input tree. We investigate the expressive power provided in this regard by structural recursion. In particular, we show that the combination of vertical recursion down a tree combined with horizontal recursion across a list of trees gives rise to a robust class of transformations: it captures the class of all primitive recursive queries. Since queries are expected to be computable in at most polynomial time for all practical purposes, we next identify a restriction of structural recursion that captures the polynomial time queries. We also give corresponding results for list-based complex objects. S. Vansummeren is a postdoctoral Fellow of the Research Foundation—Flanders (FWO).     

On sets polynomially enumerable by iteration

Sets whose members are enumerated by some Turing machine are called recursively enumerable. We define a set to be polynomially enumerable by iteration if its members are efficiently enumerated by iterated application of some Turing machine. We prove that many complex sets—including all exponential-time complete sets, all NP-complete sets yet obtained by direct construction, and the complements of all such sets—are polynomially enumerable by iteration. These results follow from more general results. In fact, we show that all recursively enumerable sets that are ^p_1si-self-reducible are polynomially enumerable by iterations, and that all recursive sets that are ^p_1si-self-reducible are bi-enumerable. We also show that when the ^p_1si-self-reduction is via a function whose inverse is computable in polynomial time, then the above results hold with the polynomial enumeration given by a function whose inverse is computable in polynomial time. In the final section of the paper we show that no NP-complete set can be iteratively enumerated in lexicographically increasing order unless the polynomial time hierarchy collapses to NP. We also show that the sets that are monotonically bi-enumerable are “essentially” the same as the sets in parity polynomial time.     

The aditi deductive database system

Deductive databases generalize relational databases by providing support for recursive views and non-atomic data. Aditi is a deductive system based on the client-server model; it is inherently multi-user and capable of exploiting parallelism on shared-memory multiprocessors. The back-end uses relational technology for efficiency in the management of disk-based data and uses optimization algorithms especially developed for the bottom-up evaluation of logical queries involving recursion. The front-end interacts with the user in a logical language that has more expressive power than relational query languages. We present the structure of Aditi, discuss its components in some detail, and present performance figures.     

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     

Magic Sets Revisited

This paper distinguishes among three kinds of linear recursions:canonical strongly linear recursion(CSLR),non-interdependent linear recursion(NILR)and interdependent linear recurstion(ILR)and presents an optimal algorithm for each.First,for the CSLRs,the magic-set method is refined in such a way that queries can be evaluated efficiently.Then,for the NILRs and ILRs,the concept of query dependency graphs is introduced to partition the rules of a program into a set of CSLRs and the computation is elaborated so that the oplimization for CSLRs can also be applied.     

Moments of conjugacy classes of binary words

For each nonempty binary word w=c₁c₂c_q, where c_i{0,1}, the nonnegative integer ∑_i=1^q (q+1−i)c_i is called the moment of w and is denoted by M(w). Let [w] denote the conjugacy class of w. Define M([w])={M(u): u[w]}, N(w)={M(u)−M(w): u[w]} and δ(w)=max{M(u)−M(v): u,v[w]}. Using these objects, we obtain equivalent conditions for a binary word to be an -word (respectively, a power of an -word). For instance, we prove that the following statements are equivalent for any binary word w with |w|2: (a) w is an -word, (b) δ(w)=|w|−1, (c) w is a cyclic balanced primitive word, (d) M([w]) is a set of |w| consecutive positive integers, (e) N(w) is a set of |w| consecutive integers and 0N(w), (f) w is primitive and [w]St.     

Identification of partial disjunction, parity, and threshold functions

Let F be a class of functions obtained by replacing some inputs of a Boolean function of a fixed type with some constants. The problem considered in this paper, which is called attribute efficient learning, is to identify “efficiently” a Boolean function g out of F by asking for the value of g at chosen inputs, where “efficiency” is measured in terms of the number of essential variables. We study the query complexity of attribute-efficient learning for three function classes that are, respectively, obtained from disjunction, parity, and threshold functions. In many cases, we obtain almost optimal upper and lower bound on the number of queries.     

Query by diagram: A visual environment for querying databases

In recent years, several attempts have been made to define query languages characterized by both high expressive power and easy query formulation. Several issues concern graphical applications, based on the diagrammatic representation of a semantic model and visual interaction. This paper describes the architecture and the implementation of a graphical query system, based on the diagrammatic representation of entity relationship schemata. The query language underlying the system allows the formulation of recursive queries; moreover, user interaction in both managing diagrams and expressing queries is simplified by the presence of a fully visual environment and a rich set of interaction strategies.     

快速递推广义预测控制

本文利用反向递推方法对广义预测控制的准则函数进行变换，得出一种递推的快速ＧＰＳ算法。