We argue that database support for design processes is still inadequate, despite the many transaction models that have been put forth to fill this deficiency. In our opinion, substantial improvement is not to be had by introducing yet another transaction model, but by questioning the basic paradigm of transaction processing itself: Instead of the usual view of transactions as destructive operations replacing an outdated database state with a more current one, we propose to view design transactions as non-destructive operations importing additional knowledge about an essentially unchanging final design solution. This leads to a model of designing with constraints, and a natural way of concurrent design. We give a formal presentation of the model and then discuss implementation techniques for centralized and distributed constraint management.

We present a functional framework for descriptive computational complexity, in which the Regular, First-order, Ptime, Pspace, k-Exptime, k-Expspace (k/spl ges/1), and Elementary sets have syntactic characterizations. In this framework, typed lambda terms represent inputs and outputs as well as programs. The lambda calculi describing the above computational complexity classes are simply or let-polymorphically typed with functionalities of fixed order. They consist of: order 0 atomic constants, order 1 equality among these constants, variables, application, and abstraction. Increasing functionality order by one for these languages corresponds to increasing the computational complexity by one alternation. This exact correspondence is established using a semantic evaluation of languages for each fixed order, which is the primary technical contribution of this paper.

A new kind of data model has recently emerged in which the database is not constrained by a conventional schema. Systems like ACeDB, which has become very popular with biologists, and the recent Tsimmis proposal for data integration organize data in tree-like structures whose components can be used equally well to represent sets and tuples. Such structures allow great flexibility y in data representation.What query language is appropriate for such structures? Here we propose a simple language UnQL for querying data organized as a rooted, edge-labeled graph. In this model, relational data may be represented as fixed-depth trees, and on such trees UnQL is equivalent to the relational algebra. The novelty of UnQL consists in its programming constructs for arbitrarily deep data and for cyclic structures. While strictly more powerful than query languages with path expressions like XSQL, UnQL can still be efficiently evaluated. We describe new optimization techniques for the deep or "vertical" dimension of UnQL queries. Furthermore, we show that known optimization techniques for operators on flat relations apply to the "horizontal" dimension of UnQL.

We present a functional framework for database query languages, which is analogous to the conventional logical framework of first-order and fixpoint formulas over finite structures. We use atomic constants of order 0, equality among these constants, variables, application, lambda abstraction, and let abstraction; all typed using fixed order (≤ 5) functionalities. In this framework, proposed in [21] for arbitrary order functionalities, queries and databases are both typed lambda terms, evaluation is by reduction, and the main programming technique is list iteration. We define two families of languages: TLI=i or simply-typed list iteration of order i+3 with equality, and MLI=i or ML-typed list iteration of order i+3 with equality; we use i+3 since our list representation of databases requires at least order 3. We show that: FO-queries ⊆TLI=0 ⊆MLI=0 ⊆LOGSPACE-queries ⊆TLI=1 =MLI=1 = PTIME-queries ⊆ TLI2, where equality is no longer a primitive in TLI2. We also show that ML type inference, restricted to fixed order, is polynomial in the size of the program typed. Since programming by using low order functionalities and type inference is common in functional languages, our results indicate that such programs suffice for expressing efficient computations and that their ML-types can be efficiently inferred.

It is shown how to naturally embed, in the typed lambda -calculus with equality, many database query languages, including the relational calculus/algebra, inflationary Datalog, and the complex object calculus/algebra. The embeddings considered are such that a database is a lambda -term coding list of tuples and a query is a lambda -term which when applied to the input database normalizes to the output database. In addition, if the query expressed is a PTIME query, then the normal form can be computed in a number of reduction steps polynomial in the size of the input database. It is also shown that, for all PTIME queries, there is such an embedding in the order-three typed lambda -calculus with equality.>

Article Free Access Share on Tools for Datalog boundedness Authors: Gerd G. Hillebrand Brown Univ., Providence, RI Brown Univ., Providence, RIView Profile , Paris C. Kanellakis Brown Univ., Providence, RI Brown Univ., Providence, RIView Profile , Harry G. Mairson Brandeis Univ., Waltham, MA Brandeis Univ., Waltham, MAView Profile , Moshe Y. Vardi IBM Almaden Center, San Jose, CA IBM Almaden Center, San Jose, CAView Profile Authors Info & Claims PODS '91: Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systemsApril 1991 Pages 1–12https://doi.org/10.1145/113413.113414Published:01 April 1991Publication History 17citation342DownloadsMetricsTotal Citations17Total Downloads342Last 12 Months17Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF