Paris C. Kanellakis

I&C Journal 1996 Journal Article

Database Query Languages Embedded in the Typed Lambda Calculus

• Gerd G. Hillebrand
• Paris C. Kanellakis
• Harry G. Mairson

We investigate the expressive power of the typedλ-calculus when expressing computations over finite structures, i. e. , databases. We show that the simply typedλ-calculus can express various database query languages such as the relational algebra, fixpoint logic, and the complex object algebra. In our embeddings, inputs and outputs areλ-terms encoding databases, and a program expressing a query is aλ-term which types when applied to an input and reduces to an output. Our embeddings have the additional property that PTIME computable queries are expressible by programs that, when applied to an input, reduce to an output in a PTIME sequence of reduction steps. Under our database input-output conventions, all elementary queries are expressible in the typedλ-calculus and the PTIME queries are expressible in the order-5 (order-4) fragment of the typedλ-calculus (with equality).

SODA Conference 1990 Conference Paper

A Data Structure for Arc Insertion and Regular Path Finding

• Adam L. Buchsbaum
• Paris C. Kanellakis
• Jeffrey Scott Vitter

I&C Journal 1990 Journal Article

CCS expressions, finite state processes, and three problems of equivalence

• Paris C. Kanellakis
• Scott A. Smolka

We examine the computational complexity of testing finite state processes for equivalence in Milner's Calculus of Communicating Systems (CCS). The equivalence problems in CCS are presented as refinements of the familiar problem of testing whether two nondeterministic finite automata (NFA) are equivalent, i. e. , accept the same language. Three notions of equivalence proposed for CCS are investigated, namely, observational equivalence, strong observational equivalence, and failure equivalence. We show that observational equivalence can be tested in polynomial time. As defined in CCS, observational equivalence is the limit of a sequence of successively finer equivalence relations, ≈ k, where ≈1 is nondeterministic finite automaton equivalence. We prove that, for each fixed k, deciding ≈ k is PSPACE-complete. We show that strong observational equivalence can be decided in polynomial time by reducing it to generalized partitioning, a new combinatorial problem of independent interest. Finally, we demonstrate that testing for failure equivalence is PSPACE-complete, even for a very restricted type of process.

STOC Conference 1988 Conference Paper

Decidable Optimization Problems for Database Logic Programs (Preliminary Report)

• Stavros S. Cosmadakis
• Haim Gaifman
• Paris C. Kanellakis
• Moshe Y. Vardi

STOC Conference 1985 Conference Paper

Equational Theories and Database Constraints

• Stavros S. Cosmadakis
• Paris C. Kanellakis

STOC Conference 1983 Conference Paper

Unary Inclusion Dependencies have Polynomial Time Inference Problems (Extended Abstract)

• Paris C. Kanellakis
• Stavros S. Cosmadakis
• Moshe Y. Vardi

FOCS Conference 1981 Conference Paper

The Complexity of Distributed Concurrency Control

• Paris C. Kanellakis
• Christos H. Papadimitriou

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.