We demonstrate the power of object identities (oids) as a database query language primitive. We develop an object-based data model, whose structural part generalizes most of the known complex-object data models: cyclicity is allowed in both its schemas and instances. Our main contribution is the operational part of the data model, the query language IQL, which uses oids for three critical purposes: (1) to represent data-structures with sharing and cycles, (2) to manipulate sets, and (3) to express any computable database query. IQL can be type checked, can be evaluated bottom-up, and naturally generalizes most popular rule-based languages. The model can also be extended to incorporate type inheritance, without changes to IQL. Finally, we investigate an analogous value-based data model, whose structural part is founded on regular infinte trees and whose operational part is IQL.

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.

Indexing a class hierarchy, in order to efficiently search or update the objects of a class according to a (range of) value(s) of an attribute, impacts OODB performance heavily. For this indexing problem, most systems use the class hierarchy index (CH) technique of [15] implemented using B+-trees. Other techniques, such as those of [14, 18,31], can lead to improved average-case performance but involve the implementation of new data-structures. As a special form of external dynamic two-dimensional range searching, this OODB indexing problem is solvable within reasonable worst-case bounds [12]. Based on this insight, we have developed a technique, called indexing by class-division (CD), which we believe can be used as a practical alternative to CH. We present an optimized implementation and experimental validation of CD's average-case performance. The main advantages of the CD technique are: (1) CD is an extension of CH that provides a significant speed-up over CH for a wide spectrum of range queries--this speed-up is at least linear in the number of classes queried for uniform data and larger otherwise; and (2) CD queries, updates and concurrent use are implementable using existing B+-tree technology. The basic idea of class-division involves a time-space tradeoff and CD requires some space and update overhead in comparison to CH. In practice, this overhead is a small factor (2 to 3) and, in worst-case, is bounded by the depth of the hierarchy and the logarithm of its size.

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.>

We examine I/O-efficient data structures that provide indexing support for new data models. The database languages of these models include concepts from constraint programming (e.g., relational tuples are generalized to conjunctions of constraints) and from object-oriented programming (e.g., objects are organized in class hierarchies). Let n be the size of the database, c the number of classes, B the secondary storage page size, and t the size of the output of a query. Indexing by one attribute in the constraint data model (for a fairly general type of constraints) is equivalent to external dynamic interval management, which is a special case of external dynamic 2-dimensional range searching. We present a semi-dynamic data structure for this problem which has optimal worst-case space O(n/B) pages and optimal query I/O time O(logBn+t/B) and has O(logBn+(log2Bn)/B) amortized insert I/O time. If the order of the insertions is random then the expected number of I/O operations needed to perform insertions is reduced to O(logBn). Indexing by one attribute and by class name in an object-oriented model, where objects are organized as a forest hierarchy of classes, is also a special case of external dynamic 2-dimensional range searching. Based on this observation we first identify a simple algorithm with good worst-case performance for the class indexing problem. Using the forest structure of the class hierarchy and techniques from the constraint indexing problem, we improve its query I/O time from O(log2c logBn + t/B) to O(logB + log2B).

We study efficient deterministic executions of parallel algorithms on restartable fail-stop CRCW PRAMs.We allow the PRAM processors to be subject to arbitrary stop failures and restarts, that are determined by an on-lineThe lower bound also applies to the expected completed work of randomized algorithms that are subject to on-line adversaries.Finally, we desribe a simple on-line adversary that causes inefficiency in many randomized algorithms.

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

The concept of method schemas is proposed as a simple model for object-oriented programming with features such as classes with methods and inheritance, method name overloading, and late binding. An important issue is to check whether a given method schema can possibly lead to inconsistencies in some interpretations. The consistency problem for method schemas is studied. The problem is shown to be undecidable in general. Decidability is obtained for monadic and/or recursion-free method schemas. The effect of covariance is considered. The issues of incremental consistency checking and of a sound algorithm for the general case are briefly discussed.

We discuss the relationship between constraint programming and database query languages. We show that bottom-up, efficient, declarative database programming can be combined with efficient constraint solving. The key intuition is that the generalization of a ground fact, or tuple, is a conjunction of constraints. We describe the basic Constraint Query Language design principles, and illustrate them with four different classes of constraints: Polynomial, rational order, equality, and Boolean constraints.

Unary inclusion dependencies are database constraints expressing subset relationships. The decidability of implication for these dependencies together with embedded implicational dependencies, such as functional dependencies, are investigated. As shown by Casanova et al., the unrestricted and finite implication problems are different for the class of functional and unary inclusion dependencies; also, for this class and for any fixed k , finite implication has no k -ary complete axiomatization. For both of these problems, complete axiomatizations and polynomial-time decision procedures are provided: linear time for unrestricted implication and cubic time for finite implication. It follows that functional and unary inclusion dependencies form a semantically natural class of first-order sentences with equality, which although not finitely controllable, is efficiently solvable and docile. Generalizing from these results, it is shown that the interaction between functional and inclusion dependencies characterizes: (1) unrestricted implication of unary inclusion and all embedded implicational dependencies; (2) finite implication of unary inclusion and all full implicational dependencies; (3) finite implication of unary inclusion and all embedded tuple-generating dependencies. As a direct consequence of this analysis, most of the applications of dependency implication are extended, within polynomial-time, to database design problems involving unary inclusion dependencies. Such examples are tests for lossless joins and tests for complementarity of projective views. Finally, if one additionally requires that

The efficient parallel algorithms proposed for many fundamental problems, such as list ranking, computing preorder numberings and other functions on trees, or integer sorting, are very sensitive to processor failures.The requirement of efficiency (commonly formalized using Parallel-time x Processors as a cost measure) has led to the design of highly tuned PRAM algorithms which, given the additional constraint of simple processor failures, unfortunately become inefficient or even incorrect.We propose a new notion of robustness, that combines efficiency with fault tolerance.For the common case of fail-stop errors, we develop a general (and easy to implement) technique to make robust many efficient parallel algorithms, e.g., algorithms for all the problems listed above.More specifically, for any dynamic pattern of fail-stop errors with at least one surviving processor, our method increases the original algorithm cost by at most a multiplicative factor polylogarithmic in the input size.

We study the complexity of type inference for a core fragment of ML with lambda abstraction, function application, and the polymorphic let declaration. Our primary technical tool is the unification problem for a class of “polymorphic” type expressions. This form of unification, which we call polymorphic unification, allows us to separate a combinatorial aspect of type inference from the syntax of ML programs. After observing that ML typing is in DEXPTIME, we show that polymorphic unification is PSPACE hard. From this, we prove that recognizing the typable core ML programs is also PSPACE hard. Our lower bound stands in contrast to the common belief that typing ML programs is “efficient,” and to practical experience which suggests that the algorithms commonly used for this task do not slow compilation substantially.

We demonstrate the power of object identities (oid's) as a database query language primitive. We develop an object-based data model, whose structural part generalizes most of the known complex-object data models: cyclicity is allowed in both its schemas and instances. Our main contribution is the operational part of the data model, the query language IQL, which uses oid's for three critical purposes: (1) to represent data-structures with sharing and cycles, (2) to manipulate sets and (3) to express any computable database query. IQL can be statically type checked, can be evaluated bottom-up and naturally generalizes most popular rule-based database languages. The model can also be extended to incorporate type inheritance, without changes to IQL. Finally, we investigate an analogous value-based data model, whose structural part is founded on regular infinite trees and whose operational part is IQL.

Datalog is the language of logic programs without function symbols. It is used as a database query language. If it is possible to eliminate recursion from a Datalog program Π, then Π is said to be bounded. It is known that the problem of deciding whether a given Datalog program is bounded is undecidable, even for binary programs. We show here that boundedness is decidable for monadic programs, i.e., programs where the recursive predicates are monadic (the non-recursive predicates can have arbitrary arity). Underlying our results are new tools for the optimization of Datalog programs based on automata theory and logic. In particular, one of the tools we develop is a theory of two-way alternating tree automata. We also use our techniques to show that containment for monadic programs is decidable.

We present a randomized parallel algorithm for term matching. Let n be the number of nodes of the directed acyclic graphs (dags) representing the terms to be matched. Then our algorithm uses $O(\log ^2 n)$ parallel time and $M(n)$ processors, where $M(n)$ is the complexity of $n \times n$ matrix multiplication. The randomized algorithm is of the Las Vegas type, that is, the answer is always correct, although with small probability the algorithm might fail to produce an answer. The number of processors is a significant improvement over previously known bounds. Under various syntactic restrictions on the form of the input dags, only $O(n^2 )$ processors are required in order to achieve deterministic $O(\log ^2 n)$ parallel time. Furthermore, we reduce directed graph reachability to term matching using constant parallel time and $O(n^2 )$ processors. This is evidence that no deterministic algorithm can significantly beat the processor bound of our randomized algorithm. We also improve the P-completeness result of Dwork, Kanellakis, and Mitchell on the unification problem, showing that unification is P-complete even if both input terms are linear, i.e., no variable appears more than once in each term.

We consider the problem of propagating selections (i.e., bindings of variables) into logic programs. In particular, we study the class of binary chain programs and define selection propagation as the task of finding an equivalent program containing only unary derived predicates. We associate a context free grammar L(H) with every binary chain program H. We show that, given H propagating a selection involving some constant is possible iff L(H) is regular, and therefore undecidable. We also show that propagating a selection of the form p(X,X) is possible iff L(H) is finite, and therefore decidable. We demonstrate the connection of these two cases, respectively, with the weak monadic second order theory of one successor and with monadic generalized spectra. We further clarify the analogy between chain programs and languages from the point of view of program equivalence and selection propagation heuristics.

We represent a set of possible worlds using an incomplete information database. The representation techniques that we study form a hierarchy, which generalizes relations of constants. This hierarchy ranges from the very simple Codd-table, (i e , a relation of constants and distinct variables called nulls, which stand for values present but unknown), to much more complex mechanisms involving views on conditioned-tables, (i e , queries on Codd-tables together with conditions). The views we consider are the queries that have polynomial data-complexity on complete information databases. Our conditions are conjunctions of equalities and inequalities.(1) We provide matching upper and lower bounds on the data-complexity of testing containement, membership, and uniqueness for sets of possible worlds and we fully classify these problems with respect to our representation hierarchy. The most surprising result in this classification is that it is complete in P2p, whether a set of possible worlds represented by a Codd-table is a subset of a set of possible worlds represented by a Codd-table with one conjuction of inequalities.(2) We investigate the data-complexity of querying incomplete information databases. We examine both asking for certain facts and for possible facts. Our approach is algebraic but our bounds also apply to logical databases. We show that asking for a certain fact is coNP-complete, even for a fixed first order query on a Codd-table. We thus strengthen a lower bound of [16], who showed that this holds for a Codd-table with a conjunction of inequalities. For each fixed positive existential query we present a polynomial algorithm solving the bounded possible fact problem of this query on conditioned-tables. We show that our approach is, in a sense, the best possible, by deriving two NP-completeness lower bounds for the bounded possible fact problem when the fixed query contains either negation or recursion.

We investigate the parallel computational complexity of recursive rule queries.These queries are a subset of first-order relational queries augmented with recursion.They form an important psrt of the PROLOG language aud can be eva!uated in PTIME.In [32] Sagiv has shown that it is decidable whether a typed recursive rule query is equivalent to a first-order relational query.We present an alternative proof of this fact We demonstrate a "gap" theorem for these queries.We provide two classes of queries, which can be evaluated in NC, using a logarithmic number of iterations of a first-order query.Finally, we give various, syntactically tight, queries which are logspace-complete in ETIME and cannot be evaluated in this fashion.

Article On the analysis of cooperation and antagonism in networks of communicating processes Share on Authors: Paris C. Kanellakis Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MAView Profile , Scott A. Smolka Department of Computer Science, SUNY at Stony Brook, Stony Brook, NY Department of Computer Science, SUNY at Stony Brook, Stony Brook, NYView Profile Authors Info & Claims PODC '85: Proceedings of the fourth annual ACM symposium on Principles of distributed computingAugust 1985 Pages 23–38https://doi.org/10.1145/323596.323599Online:01 August 1985Publication History 6citation77DownloadsMetricsTotal Citations6Total Downloads77Last 12 Months3Last 6 weeks1 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 SiteGet Access

Article Free Access Share on Partition semantics for relations Authors: Stavros S. Cosmadakis View Profile , Paris C. Kanellakis View Profile , Nicolas Spyratos View Profile Authors Info & Claims PODS '85: Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systemsMarch 1985 Pages 261–275https://doi.org/10.1145/325405.325452Published:25 March 1985Publication History 8citation94DownloadsMetricsTotal Citations8Total Downloads94Last 12 Months10Last 6 weeks6 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

ISIS IS an experimental system for graphically manlpulatmg a database The system 1s based on a simply specified high-level semantic data model It demonstrates the capablbtles of a workstation environment by mtegratmg three aspects of database programming m one graphical setting Namely, it permits database constructlon and modification, it allows browsing at the schema and data levels, and provides a graphical query language In all of these activities it maintains uniform graphlcal representations and consistent user mteractlon techniques

We present a novel way to formulate database dependencies as sentences of first-order logic, using equational statements instead of Horn clauses. Dependency implication is directly reduced to equational implication. Our approach is powerful enough to express functional and inclusion dependencies, which are the most common database constraints. We present a new proof procedure for these dependencies. We use our equational formulation to derive new upper and lower bounds for the complexity of their implication problems.

We present a formal framework for distributed databases, and we study the complexity of the concurrency control problem in this framework. Our transactions are partially ordered sets of actions, as opposed to the straight-line programs of the centralized case. The concurrency control algorithm, or scheduler, is itself a distributed program. Three notions of performance of the scheduler are studied and interrelated: (1) its parallelism, (2) the computational complexity of the problems it needs to solve and (3) the cost of communication between the various parts of the scheduler. We show that the number of messages necessary and sufficient to support a given level of parallelism is equal to the minimax value of a combinatorial game. We show that this game is PSPACE-complete. It follows that, unless $\text{NP} = \text{PSPACE}$, a scheduler cannot simultaneously minimize communication and be computationally efficient. This result, we argue, captures the quantum jump in complexity of the transition from centralized to distributed concurrency control problems.

We present a new graph theoretic approach to the implication problem for functional (FD) and inclusion (IND) dependencies. Using this methodology we prove decidability for the case of typed IND's and acyclic FD's. We provide new lower bounds for the implication of typed, acyclic IND's and FD's --- NP-hardness and PSPACE-hardness for bounded domains. Finally, we show that there is no k-ary complete axiomatization for implication of FD's, even when we have pairwise consistency, i.e., all possible typed IND's hold.

We examine the problem of concurrency control when the database management system supports multiple versions of the data. We characterize the limit of the parallelism achievable by the multiversion approach and demonstrate the resulting space-parallelism trade-off.

We examine the computational complexity of testing finite state processes for equivalence, in the Calculus of Communicating Systems (CCS). This equivalence problem in CCS is presented as a refinement of the familiar problem of testing whether two nondeterministic finite state automata (n.f.s.a.) accept the same language. Three notions of equivalence, proposed for CCS, are investigated: (1) observation equivalence, (2) congruence, and (3) failure equivalence. We show that observation equivalence (@@@@) can be tested in cubic time and is the limit of a sequence of equivalence notions (@@@@k), where, @@@@1 is the familiar n.f.s.a. equivalence and, for each fixed k, @@@@k is PSPACE-complete. We provide an O(nlogn) test for congruence for n state processes of bounded fanout, by extending the algorithm that minimizes the states of d.f.s.a.'s. Finally, we show that, even for a very restricted type of process, testing for failure equivalence is PSPACE-complete.

We study the interaction between unary inclusion dependencies (UIND's) and other known classes of dependencies, in the context of both unrestricted and finite implication. We provide complete axiomatizations for unrestricted and finite implication of UIND's and functional dependencies, and polynomial-time algorithms for the inference problems. The inference problem becomes, however, NP-hard, if we require that some attribute have a bounded domain. We show that for unrestricted implication, the interaction between UIND's and unary functional dependencies completely characterizes the interaction between UIND's and embedded implicational dependencies. Also, for finite implication, the interaction between UIND's and unary functional dependencies completely characterizes the interaction between UIND's and full implicational dependencies (but not UIND's and embedded implicational dependencies).

We examine the problem of determining whether a set of locked transactions, accessing a distributed database, is guaranteed to produce only serializable schedules. For a pair of transactions we prove that this concurrency control problem (which is polynomially solvable for centralized databases) is in general coNP-complete. We employ a new graph-theoretic technique and provide an efficient test for the special case of databases distributed between two sites only.

We examine the problem of concurrency control when the database management system supports multiple versions of the data. We characterize the limit of the parallelism achievable by the multiversion approach and demonstrate the resulting space-parallelism tradeoff.

We present a formal framework for distributed databases, and we study the complexity of the concurrency control problem in this framework. Our transactions are partially ordered sets, of actions, as opposed to the straight-line programs of the centralized case. The concurrency control algorithm, or scheduler, is itself a distributed program. Three notions of performance of the scheduler are studied and interrelated: (i) its parallelism, (ii) the computational complexity of the problems it needs to solve, and (iii) the cost of communication between the various parts of the scheduler. We show that the number of messages necessary and sufficient to support a given level of parallelism is equal to the minmax value of a combinatorial game. We show that this game is PSPACE-complete. It follows that, unless NP=PSPACE, a scheduler cannot simultaneously minimize communication and be computationally efficient. This result, we argue, captures the quantum jump in complexity of the transition from centralized to distributed concurrency control problems.

We examine the problem of scheduling 2-machine flowshops in order to minimize makespan, using a limited amount of intermediate storage buffers.Although there are efficient algorithms for the extreme cases of zero and infinite buffer capacities, it is shown that all the intermediate (finite-capacity) cases are NP-complete.Exact bounds are proved for the relative improvement of execution times when a given buffer capacity is used.An efficient heuristic for solving the I-buffer problem is also analyzed, and it is shown that it has a ~ worst-case performance.Furthermore, it is shown that the "no-wait" (i.e., zero buffer) flowsbop scheduling problem with four machines is NP-complete.This partly settles a well-known open question, although the 3-machine case is left open here.