Algebraic query optimisation for database programming languages

A major challenge still facing the designers and implementors of database programming languages (DBPLs) is that of query optimisation. We investigate algebraic query optimisation techniques for DBPLs in the context of a purely declarative functional language that supports sets as first-class objects. Since the language is computationally complete issues such as non-termination of expressions and construction of infinite data structures can be investigated, whilst its declarative nature allows the issue of side effects to be avoided and a richer set of equivalences to be developed. The language has a well-defined semantics which permits us to reason formally about the properties of expressions, such as their equivalence with other expressions and their termination. The support of a set bulk data type enables much prior work on the optimisation of relational languages to be utilised. In the paper we first give the syntax of our archetypal DBPL and briefly discuss its semantics. We then define a small but powerful algebra of operators over the set data type, provide some key equivalences for expressions in these operators, and list transformation principles for optimising expressions. Along the way, we identify some caveats to well-known equivalences for non-deductive database languages. We next extend our language with two higher level constructs commonly found in functional DBPLs: set comprehensions and functions with known inverses. Some key equivalences for these constructs are provided, as are transformation principles for expressions in them. Finally, we investigate extending our equivalences for the set operators to the analogous operators over bags. Although developed and formally proved in the context of a functional language, our findings are directly applicable to other DBPLs of similar expressiveness. Edited by Matthias Jarke, Jorge Bocca, Carlo Zaniolo. Received September 15, 1994 / Accepted September 1, 1995     

On the intersection of regex languages with regular languages

In this paper we revisit the semantics of extended regular expressions (regex), defined succinctly in the 90s [A.V. Aho, Algorithms for finding patterns in strings, in: Jan van Leeuwen (Ed.), Handbook of Theoretical Computer Science, in: Algorithms and Complexity, vol. A, Elsevier and MIT Press, 1990, pp. 255–300] and rigorously in 2003 by Câmpeanu, Salomaa and Yu [C. Câmpeanu, K. Salomaa, S. Yu, A formal study of practical regular expressions, IJFCS 14 (6) (2003) 1007–1018], when the authors reported an open problem, namely whether regex languages are closed under the intersection with regular languages. We give a positive answer; and for doing so, we propose a new class of machines — regex automata systems (RAS) — which are equivalent to regex. Among others, these machines provide a consistent and convenient method of implementing regex in practice. We also prove, as a consequence of this closure property, that several languages, such as the mirror language, the language of palindromes, and the language of balanced words are not regex languages.     

Testing and verification aspects of Pascal-like languages

This paper addresses aspects of programming language design that affect the ease with which programs written in a language can be subjected to systematic testing and/or program verification. The discussion focuses of Pascal and on several languages that have been derived primarily from Pascal, particularly Euclid and PLAIN. Specific language issues addressed include translation-time checking, program readability, flow of control, support for program modularity, data flow, and program immutability. The relative ease of validating such programs is then determined by the style in which the programs are written. The paper presents some guidelines for writing programs in Pascal-like languages for testability and verifiability.     

Proceduralism and parallelism in specification languages

We discuss the advantages and limitations of the “nonprocedural” mode of expression, in the context of languages for programming, system specification, and database access. A language is introduced which has some relevance to all three of the above processes. The syntax of LEGOL is based on the relational algebra, but incorporates procedural control structures for use when the underlying application logic demands. Using this language, solutions can be suggested for some example stock-control problems which are difficult to handle in a purely non-procedural way.     

Extension of tabled 0L-systems and languages

This paper introduces a new family of languages which originated from a study of some mathematical models for the development of biological organisms. Various properties of this family are established and in particular it is proved that it forms a full abstract family of languages. It is compared with some other families of languages which have already been studied and which either originated from the study of models for biological development or belong to the now standard Chomsky hierarchy. A characterization theorem for context-free languages is also established.This research has been supported by NSF Grant GJ 998.     

A note on Parikh maps,abstract languages,and decision problems

We consider formulas similar to Presburger formulas, but extended by allowing the predicate | (for divides), but not allowing universal quantification of the resulting expressions. The solution sets for such formulas are known to be not semilinear, in general. We show that some results concerning decidability questions for classes of languages with effectively constructible semilinear Parikh maps can be extended to languages whose effectively constructible Parikh maps are solutions to these new formulas, which we call “modular”. We suggest that modularity may offer a natural extension of semilinearity, in which many previously established results may remain valid.     

McNaughton families of languages

In 1988 the Church–Rosser languages were introduced by McNaughton et al. as those languages that are recognized by finite, length-reducing and confluent string-rewriting systems using extra non-terminal symbols. Here we generalize this concept by considering classes of languages that are obtained by other types of string-rewriting systems. To honour Robert McNaughton's original contribution we call the resulting families of languages McNaughton families. Here it is shown that the concept of McNaughton families is as powerful as the notion of Turing machine or the notion of phrase-structure grammar. We investigate the relationships between the various McNaughton families, obtaining an extensive hierarchy of classes that includes many well-known language and complexity classes as well as some new classes. Further, we consider some closure and non-closure properties for those McNaughton families that are contained in the class of context-free languages, and we address the complexity of the fixed and the general membership problems for these families.     

Programming languages for fifth generation computers

Fifth Generation languages and computers, for use in the 1990's, may be based on significantly different concepts than traditional computing. There are four major categories of computing, each consisting of a programming style and corresponding computer. These are: procedural languages (and control flow computers); object-oriented languages (and actor computers); functional languages (and data flow or reduction computers); and logic languages (and logic computers). In the future any of these categories of languages may become “main-stream” programming styles. In this paper we briefly present these novel programming languages and examine their advantages and disadvantages for programming.     

Rule-based languages

The paper presents a survey of the main formal rule-based languages and semantics. Both procedural (fixpoint) and declarative (model-theoretic) semantics are defined and discussed, including inflationary and noninflationary fixpoint semantics, and the semi-positive, stratified and well-founded semantics. The relative expressive power and com-plexity of the various languages are provided. Nondeterministic rule-based languages are also discussed, and it is shown how nondeterminism can circumvent some difficulties concerning the expressive power of the deterministic languages. Finally, languages with value invention (in the spirit of object-creation in oodbs) are presented and issues of expressive power specific to such languages are discussed.     

Stochastic grammars and languages

This paper summarizes some recent results concerned with the extension of formal languages to their corresponding stochastic versions. Weighted grammars and languages are first defined, and stochastic grammars and languages are defined as a special case of weighted grammars and languages. Fuzzy grammars and languages, which have some properties similar to weighted grammars and languages, are also discussed. Stochastic automata are defined from the language recognition viewpoint. Languages accepted by stochastic finite-state and pushdown automata, with and without a cutpoint, are studied. Weighted and stochastic programmed and indexed grammars, and stochastic nested stack automata are defined. Finally, some decidability problems of stochastic (weighted, fuzzy) languages are discussed, and problems for further research are suggested.This work was supported by the National Science Foundation Grant GK-18225.     

The expressive power of temporal relational query languages

The authors consider the representation of temporal data based on tuple and attribute timestamping. They identify the requirements in modeling temporal data and elaborate on their implications in the expressive power of temporal query languages. They introduce a temporal relational data model where N1NF relations and attribute timestamping are used and one level of nesting is allowed. For this model, a nested relational tuple calculus (NTC) is defined. They follow a comparative approach in evaluating the expressive power of temporal query languages, using NTC as a metric and comparing it with the existing temporal query languages. They prove that NTC subsumes the expressive power of these query languages. They also demonstrate how various temporal relational models can be obtained from the temporal relations by NTC and give equivalent NTC expressions for their languages. Furthermore, they show the equivalence of intervals and temporal elements (sets) as timestamps in their model     

Growth properties of power-free languages

The aim of this paper is to survey the area formed by the intersection of two popular lines of research in formal language theory. The first line, originated by Thue in 1906, concerns repetition-free words and languages. The second line is the study of growth functions for words and languages; it can be traced back to the classical papers by Morse and Hedlund on symbolic dynamics (1938, 1940). Growth functions of repetition-free languages have been investigated since the 1980’s. Most of the results are obtained for power-free languages, but some ideas can be applied for languages avoiding patterns and Abelian-power-free languages as well.In this paper, we present key contributions to the area, its state of the art, and conjectures that suggest answers to some natural unsolved problems. Also, we pay much attention to the tools and techniques that made the progress in the area possible.     

Insertion languages

The operations of insertion ( ← ) and iterated insertion ( ←₁ ) are simple variants of Kleene's operations · and 1 [15] in a manner similar to the operations shuffle and iterated shuffle (see e.g. [13, 23, 20, 14]). Using the operation of iterated insertion, we can generate both the semi-Dyck and the two-sided Dyck languages from certain finite subsets of these languages. Thus the class of languages of the form $\text{S}{}^{\mathrm{\leftarrow }}{}^1$ for finite S forms a natural class of generalized Dyck languages. This class is equivalent to the class of pure unitary languages discussed in [6]. We investigate this class further, by examining for it the problems of equivalence, ambiguity, and determinism, all of which are easily decidable. On the other hand, we show that the problem “$\text{S}{}^{\mathrm{\leftarrow }}\text{1 ∩ T}{}^{\mathrm{\leftarrow }}\text{1 = {λ}?}$” is undecidable for finite, unambiguous S and T. Furthermore, by extending the regular expressions to include the operations ← and $\text{←}{}_1$, we obtain the class of insertion languages which generalizes both the regular languages and the Dyck languages, but is properly contained within the class of context-free languages. Our main result here is that the problem “$\text{L = ∑}{}^1\text{?}$” is undecidable for the class of insertion languages. From this result, it follows that the equivalence problem and the problem “IsL regular?” are also undecidable for this class.     

An algebraic approach to data languages and timed languages

Algebra offers an elegant and powerful approach to understand regular languages and finite automata. Such framework has been notoriously lacking for timed languages and timed automata. We introduce the notion of monoid recognizability for data languages, which includes timed languages as special case, in a way that respects the spirit of the classical situation. We study closure properties and hierarchies in this model and prove that emptiness is decidable under natural hypotheses. Our class of recognizable languages properly includes many families of deterministic timed languages that have been proposed until now, and the same holds for non-deterministic versions.     

On function languages and parallel computers

This paper is a discussion of functional languages and parallel computers. It is aimed at an audience that has a background in computer architecture, but not necessarily in the area of functional languages. It therefore constitutes an introductory survey of functional languages, on the one hand, and a non-introductory discussion of parallel computers, on the other. The aim is to highlight some important issues regarding the use of adequacy of these languages and also on the design of parallel computers to interpret them. The concluding thesis of put forth is twofold: one, that to widen their scope of applicability, functional languages need to include more features of nondeterminism and may need to be integrated with features from conventional languages; two, that the right sort of architectures for such extended languages may well be less-specialised ones with a von Neumann flavour.     

Parallel programming with logic languages: A survey

Formal properties of logic languages are largely studied; however, their impact on the practice of software design and programming is currently minimal. In this paper we survey some interesting representatives of the family of logic languages aiming at comparing the different capabilities they offer for designing and programming parallel systems. The logic languages Prolog, Aurora, Flat Concurrent Prolog, Parlog, GHC, and DeltaProlog were chosen, because a suitable set of relevant examples has been published, mostly by the language designers themselves. A number of sample programs is used to expose and compare the languages with respect to their object oriented programming capabilities for multiprocess coordination, interprocess communication, and resource management. Special attention is devoted also to metaprogramming as well, seen as a useful technique for specifying and building the operating environments of the languages themselves. The paper ends with a discussion on positive and negative features found comparing these languages, and indicates some guidelines to be followed in the design of new logic languages.     

Non-determinism in logic-based languages

The use of non-determinism in logic-based languages is motivated using pragmatic and theoretical considerations. Non-deterministic database queries and updates occur naturally, and there exist non-deterministic implementations of various languages. It is shown that non-determinism resolves some difficulties concerning the expressive power of deterministic languages: there are non-deterministic languages expressing low complexity classes of queries/updates, whereas no such deterministic languages are known. Various mechanisms yielding non-determinism are reviewed. The focus is on two closely related families of non-deterministic languages. The first consists of extensions of Datalog with negations in bodies and/or heads of rules, with non-deterministic fixpoint semantics. The second consists of non-deterministic extensions of first-order logic and fixpoint logics, using thewitness operator. The expressive power of the languages is characterized. In particular, languages expressing exactly the (deterministic and non-deterministic) queries/updates computable in polynomial time are exhibited, whereas it is conjectured that no analogous deterministic language exists. The connection between non-deterministic languages and determinism is also explored. Several problems of practical interest are examined, such as checking (statically or dynamically) if a given program is deterministic, detecting coincidence of deterministic and non-deterministic semantics, and verifying termination for non-deterministic programs.Work supported by the Projet de Recherche Coordonnée BD3.Work supported in part by the National Science Foundation under grants IRI-8816078 and INT-8817874. The work was done in part while the author was visiting INRIA.     

有向图语言

经典形式语言有两条主线,就是自动机线索与形式文法线索。利用有向图理论和有向图半群理论建立了另一条线索——有向图语言,讨论了两类特殊的有向图语言——de Bruijn有向图语言和Kautz有向图语言,引入了连通语言及语言的直径等概念,计算出了de Bruijn有向图语言和Kautz有向图语言的直径。     

Strategical languages of infinite words

We deal in this paper with strategical languages of infinite words, that is those generated by a nondeterministic strategy in the sense of game theory. We first show the existence of a minimal strategy for such languages, for which we give an explicit expression. Then we characterize the family of strategical languages as that of closed ones, in the topological space of infinite words. Finally, we give a definition of a Nash equilibrium for such languages, that we illustrate with a famous example.