Arrow Research search

Author name cluster

Ravi Sethi

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

10 papers
2 author rows

Possible papers

10

FOCS Conference 1981 Conference Paper

A model of concurrent database transactions (summary)

  • Ravi Sethi

When several transactions (processes) read and write items in a database, the question of consistency of the database arises. Consistency is maintained if transactions are serial: all actions of a transaction execute completely before the actions of the next transaction begin. A particular history of interleaved actions belonging to several transactions is correct if it is equivalent to a serial history. We provide a natural framework for studying serializability that encompasses models that have been considered in the literature. A history is represented by a dag in which there is a vertex for each instantaneous value taken by an item in the database. The main tool for determining serializability are "exclusion rules" which determine implied orderings between vertices. For example, a vertex that uses a value must be serialized before the value is overwritten. An exclusion closure -- the result of applying the rules as long as possible -- can be constructed in time cubic in the number of vertices. Since determining serializability is NP-complete, exclusion closures cannot always decide serializability, but useful sufficient conditions can be proven. Exclusion closures allow the largest known classes of polynomially serializable histories to be properly extended. When studying serializability it is not necessary to work solely with the dag containing instantaneous values of all items. Three abstractions of the dag are presented which correspond to models of transactions and to "version graphs" in the literature. Since serializability of histories is known to be NP-complete, subclasses of serializable histories have been studied. One such class consists of histories serializable in a strict sense: transactions that are already in serial in a history must remain in the same relative order. When there are no useless actions in a history, strict serializability can be determined in polynomial time. If useless actions are permitted then strict serializability becomes NP-complete. The above results apply to two step transactions in which there is a read step followed by a write step, Each step involves some subset of the items in the database. With multistep transactions strict serializability is NP-complete even if there are no useless actions.

Details

FOCS Conference 1976 Conference Paper

Assignment Commands and Array Structures

  • Peter J. Downey
  • Ravi Sethi

Straight line programs in which array elements can be referenced and set are considered. Two programs are equivalent if they compute the same expression as a function of the inputs. Testing the equivalence of programs with arrays is shown to be NP-complete, while programs without arrays can be tested for equivalence in linear time. Equivalence testing takes polynomial time when programs have either no references or no assignments to array elements.

Details

FOCS Conference 1976 Conference Paper

Complexity of Trie Index Construction (Extended Abstract)

  • Douglas Comer
  • Ravi Sethi

Trie structures are a convenient way of indexing files in which keys are specified by values of attributes. Records correspond to leaves in the trie. Retrieval proceeds by following a path from the root to a leaf, the choice of edges being determined by attribute values. The size of a trie for a file depends on the order in which attributes are tested. We show that determining minimal size tries is an NP-complete problem for several variants of tries. For tries in which leaf chains are deleted we show that determining the trie for which average access time is minimal is also an NP-complete problem. Our results hold even for files in which attribute values are chosen from a binary or ternary alphabet.

Details

FOCS Conference 1975 Conference Paper

Correct Computation Rules for Recursive Languages (Extended Abstract)

  • Peter J. Downey
  • Ravi Sethi

This paper considers simple LISP-like languages for the recursive definition of functions, focusing upon the connections between formal computation rules for calculation and the mathematical semantics of recursive definitions. A computation rule is correct when it is capable of computing the minimal fixpoint of a recursive definition. We give necessary and sufficient conditions for the correctness of rules under (a) all possible interpretations and (b) particular interpretations.

Details