The Experts below are selected from a list of 1467 Experts worldwide ranked by ideXlab platform

Sanjay Kumar Madria - One of the best experts on this subject based on the ideXlab platform.

  • a concurrency control algorithm for an open and safe Nested Transaction model formalization and correctness
    2003
    Co-Authors: Sanjay Kumar Madria, S. N. Maheshwari, B. Chandra
    Abstract:

    In this paper, we formalize and prove the correctness of a concurrency control algo- rithm for an open and safe Nested Transaction using I/O automaton model. The model uses the notion of a recovery point subTransaction in the Nested Transaction tree. Our Nested Transaction model uses a prewrite operation before an actual write operation to increase the concurrency. It is termed "open and safe" as prewrites allow early reads (before database writes on disk) without cascading aborts. In our model we have also modeled the buffer management operations as Nested Transactions, and the concurrency control algorithm controls their executions. Non-access subTransactions, objects and the scheduler are modeled as I/O automata with the help of some pre and post conditions. These conditions capture the operational semantics and behavior of each automaton dur- ing the execution of Transactions. While modeling we also take into account log activities, which occur during the execution of Transactions. We also briefly sketch the recovery algorithm. The correctness proof shows that the concurrency control algorithm for our model is serially correct. Our proof makes use of assertional reasoning and provides many interesting invariant, thus gives a better understanding of our Transaction model and the concurrency control algorithm. While proving correctness, we mapped our sys- tem to that of Moss's two phase locking system to show the relationships between the two algorithms.

  • Performance evaluation of linear hash structure model in a Nested Transaction environment
    Journal of Systems and Software, 2002
    Co-Authors: Malik Tubaishat, Sanjay Kumar Madria, Bharat Bhargava
    Abstract:

    We design and implement a linear hash algorithm in Nested Transaction environment to handle large amount of data with increased concurrency. Nested Transactions allow parallel execution of Transactions, and handle Transaction aborts, thus provides more concurrency and efficient recovery. We use object-oriented methodology in the implementation which helped in designing the programming components independently. In our model, buckets are modeled as objects and linear hash operations are modeled as methods. The papers contribution is novel in the sense that the system, to our knowledge, is the first to implement linear hashing in a Nested Transactions environment. We have build a system simulator to analyze the performance. A subtle benefit of the simulator is that it works as the real system with only minor changes.

  • virtual partition algorithm in a Nested Transaction environment and its correctness
    Information Sciences, 2001
    Co-Authors: Sanjay Kumar Madria, S. N. Maheshwari, B. Chandra
    Abstract:

    Abstract In this paper, we present a formal description of the virtual partition algorithm in a Nested Transaction environment and prove its correctness. We model the virtual partition algorithm in a Nested Transaction environment using the I/O automaton model. The formal description is used to construct a complete correctness proof that is based on standard assertional techniques and on a natural correctness condition, and takes advantage of the modularity that arises from describing the algorithm as Nested Transactions. Our presentation and proof treat issues of data replication entirely separately from issues of concurrency control. Moreover, we have identified that the virtual partition algorithm cannot be proven correct in the sense of Goldman's work [ACM Trans. Database Syst. 19(4) (1994) 537] on Gifford's quorum consensus algorithm using the serializability theorem defined by Fekete et al. [Atomic Transactions, Morgan-Kaufmann, USA, 1994]. Thus, we have stated a weaker notion of correctness conditions, which we call the reorder serializability theorem. We have shown that not all classes of replication algorithms can be proven in the way Goldman has presented the proof of Gifford's quorum consensus algorithm.

  • formalization and proof of correctness of the crash recovery algorithm for an open and safe Nested Transaction model
    International Journal of Cooperative Information Systems, 2001
    Co-Authors: Sanjay Kumar Madria, S. N. Maheshwari, B. Chandra, Bharat Bhargava
    Abstract:

    In this paper, we present, formalize and prove the correctness of recovery algorithm for our open and safe Nested Transaction model using I/O automaton model. Our Nested Transaction model uses the notion of a recovery point subTransaction in the Nested Transaction tree. It introduces a prewrite operation before each write operation to increase the potential concurrency. Our Transaction model is termed as "open and safe" as prewrites allow early reads (before database writes on disk) without cascading aborts. The systems restart and buffer management operations are modelled as Nested Transactions to exploit possible concurrency during restart. Each non-access Transaction, object, and the scheduler is modeled as I/O automaton. Each of these automata is specified with the help of some pre-and post-conditions. These pre-and post-conditions capture the operational semantics and the behavior of each automaton during recovery operations. Our proof technique makes use of assertional reasoning and provide many interesting invariant, thus gives a better understanding of our recovery algorithm.

  • An open and safe Nested Transaction model: concurrency and recovery
    Journal of Systems and Software, 2000
    Co-Authors: Sanjay Kumar Madria, S. N. Maheshwari, B. Chandra, Bharat Bhargava
    Abstract:

    In this paper, we present an open and safe Nested Transaction model. We discuss the concurrency control and recovery algorithms for our model. Our Nested Transaction model uses the notion of a recovery point subTransaction in the Nested Transaction tree. It incorporates a prewrite operation before each write operation to increase the potential concurrency. Our Transaction model is termed ‘‘open and safe’’ as prewrites allow early reads (before writes are performed on disk) without cascading aborts. The systems restart and buAer management operations are also modeled as Nested Transactions to exploit possible concurrency during restart. The concurrency control algorithm proposed for database operations is also used to control concurrent recovery operations. We have given a snapshot of complete Transaction processing, data structures involved and, building the restart state in case of crash recovery. ” 2000 Elsevier Science Inc. All rights reserved.

Bharat Bhargava - One of the best experts on this subject based on the ideXlab platform.

  • Performance evaluation of linear hash structure model in a Nested Transaction environment
    Journal of Systems and Software, 2002
    Co-Authors: Malik Tubaishat, Sanjay Kumar Madria, Bharat Bhargava
    Abstract:

    We design and implement a linear hash algorithm in Nested Transaction environment to handle large amount of data with increased concurrency. Nested Transactions allow parallel execution of Transactions, and handle Transaction aborts, thus provides more concurrency and efficient recovery. We use object-oriented methodology in the implementation which helped in designing the programming components independently. In our model, buckets are modeled as objects and linear hash operations are modeled as methods. The papers contribution is novel in the sense that the system, to our knowledge, is the first to implement linear hashing in a Nested Transactions environment. We have build a system simulator to analyze the performance. A subtle benefit of the simulator is that it works as the real system with only minor changes.

  • formalization and proof of correctness of the crash recovery algorithm for an open and safe Nested Transaction model
    International Journal of Cooperative Information Systems, 2001
    Co-Authors: Sanjay Kumar Madria, S. N. Maheshwari, B. Chandra, Bharat Bhargava
    Abstract:

    In this paper, we present, formalize and prove the correctness of recovery algorithm for our open and safe Nested Transaction model using I/O automaton model. Our Nested Transaction model uses the notion of a recovery point subTransaction in the Nested Transaction tree. It introduces a prewrite operation before each write operation to increase the potential concurrency. Our Transaction model is termed as "open and safe" as prewrites allow early reads (before database writes on disk) without cascading aborts. The systems restart and buffer management operations are modelled as Nested Transactions to exploit possible concurrency during restart. Each non-access Transaction, object, and the scheduler is modeled as I/O automaton. Each of these automata is specified with the help of some pre-and post-conditions. These pre-and post-conditions capture the operational semantics and the behavior of each automaton during recovery operations. Our proof technique makes use of assertional reasoning and provide many interesting invariant, thus gives a better understanding of our recovery algorithm.

  • An open and safe Nested Transaction model: concurrency and recovery
    Journal of Systems and Software, 2000
    Co-Authors: Sanjay Kumar Madria, S. N. Maheshwari, B. Chandra, Bharat Bhargava
    Abstract:

    In this paper, we present an open and safe Nested Transaction model. We discuss the concurrency control and recovery algorithms for our model. Our Nested Transaction model uses the notion of a recovery point subTransaction in the Nested Transaction tree. It incorporates a prewrite operation before each write operation to increase the potential concurrency. Our Transaction model is termed ‘‘open and safe’’ as prewrites allow early reads (before writes are performed on disk) without cascading aborts. The systems restart and buAer management operations are also modeled as Nested Transactions to exploit possible concurrency during restart. The concurrency control algorithm proposed for database operations is also used to control concurrent recovery operations. We have given a snapshot of complete Transaction processing, data structures involved and, building the restart state in case of crash recovery. ” 2000 Elsevier Science Inc. All rights reserved.

  • design and implementation of linear hash algorithm in a Nested Transaction environment
    Database and Expert Systems Applications, 1999
    Co-Authors: Sanjay Kumar Madria, Malik Tubaishat, Bharat Bhargava
    Abstract:

    In this paper, we present a design and implementation of a linear hashing algorithm in Nested Transaction environment to handle large amount of data. Nested Transactions allow parallel execution of Transactions, and handle Transaction aborts, thus provides more concurrency and efficient recovery. We design a client/server model using layered system architecture. We have used object-oriented methodology in our system implementation that helps in designing and implementing the programming components independently. In our model, buckets are modeled as objects and linear hash operations are modeled as methods. These methods correspond to Nested Transactions and are implemented using multithreading paradigm.

  • crash recovery in an open and safe Nested Transaction model
    Database and Expert Systems Applications, 1997
    Co-Authors: Sanjay Kumar Madria, S. N. Maheshwari, B. Chandra, Bharat Bhargava
    Abstract:

    In this paper, we present an open and safe Nested Transaction model and discuss the crash recovery issues. We introduce the notion of a recovery point subTransaction in a Nested Transaction tree. We introduce prewrite operations to increase concurrency. Our model is open and safe as prewrites allow early reads (before database writes on disk) without cascading aborts. The systems restart and buffer management operations are modeled as Nested Transactions to exploit possible concurrency during restart. Our model is useful in handling long-duration Transactions.

B. Chandra - One of the best experts on this subject based on the ideXlab platform.

  • a concurrency control algorithm for an open and safe Nested Transaction model formalization and correctness
    2003
    Co-Authors: Sanjay Kumar Madria, S. N. Maheshwari, B. Chandra
    Abstract:

    In this paper, we formalize and prove the correctness of a concurrency control algo- rithm for an open and safe Nested Transaction using I/O automaton model. The model uses the notion of a recovery point subTransaction in the Nested Transaction tree. Our Nested Transaction model uses a prewrite operation before an actual write operation to increase the concurrency. It is termed "open and safe" as prewrites allow early reads (before database writes on disk) without cascading aborts. In our model we have also modeled the buffer management operations as Nested Transactions, and the concurrency control algorithm controls their executions. Non-access subTransactions, objects and the scheduler are modeled as I/O automata with the help of some pre and post conditions. These conditions capture the operational semantics and behavior of each automaton dur- ing the execution of Transactions. While modeling we also take into account log activities, which occur during the execution of Transactions. We also briefly sketch the recovery algorithm. The correctness proof shows that the concurrency control algorithm for our model is serially correct. Our proof makes use of assertional reasoning and provides many interesting invariant, thus gives a better understanding of our Transaction model and the concurrency control algorithm. While proving correctness, we mapped our sys- tem to that of Moss's two phase locking system to show the relationships between the two algorithms.

  • virtual partition algorithm in a Nested Transaction environment and its correctness
    Information Sciences, 2001
    Co-Authors: Sanjay Kumar Madria, S. N. Maheshwari, B. Chandra
    Abstract:

    Abstract In this paper, we present a formal description of the virtual partition algorithm in a Nested Transaction environment and prove its correctness. We model the virtual partition algorithm in a Nested Transaction environment using the I/O automaton model. The formal description is used to construct a complete correctness proof that is based on standard assertional techniques and on a natural correctness condition, and takes advantage of the modularity that arises from describing the algorithm as Nested Transactions. Our presentation and proof treat issues of data replication entirely separately from issues of concurrency control. Moreover, we have identified that the virtual partition algorithm cannot be proven correct in the sense of Goldman's work [ACM Trans. Database Syst. 19(4) (1994) 537] on Gifford's quorum consensus algorithm using the serializability theorem defined by Fekete et al. [Atomic Transactions, Morgan-Kaufmann, USA, 1994]. Thus, we have stated a weaker notion of correctness conditions, which we call the reorder serializability theorem. We have shown that not all classes of replication algorithms can be proven in the way Goldman has presented the proof of Gifford's quorum consensus algorithm.

  • formalization and proof of correctness of the crash recovery algorithm for an open and safe Nested Transaction model
    International Journal of Cooperative Information Systems, 2001
    Co-Authors: Sanjay Kumar Madria, S. N. Maheshwari, B. Chandra, Bharat Bhargava
    Abstract:

    In this paper, we present, formalize and prove the correctness of recovery algorithm for our open and safe Nested Transaction model using I/O automaton model. Our Nested Transaction model uses the notion of a recovery point subTransaction in the Nested Transaction tree. It introduces a prewrite operation before each write operation to increase the potential concurrency. Our Transaction model is termed as "open and safe" as prewrites allow early reads (before database writes on disk) without cascading aborts. The systems restart and buffer management operations are modelled as Nested Transactions to exploit possible concurrency during restart. Each non-access Transaction, object, and the scheduler is modeled as I/O automaton. Each of these automata is specified with the help of some pre-and post-conditions. These pre-and post-conditions capture the operational semantics and the behavior of each automaton during recovery operations. Our proof technique makes use of assertional reasoning and provide many interesting invariant, thus gives a better understanding of our recovery algorithm.

  • An open and safe Nested Transaction model: concurrency and recovery
    Journal of Systems and Software, 2000
    Co-Authors: Sanjay Kumar Madria, S. N. Maheshwari, B. Chandra, Bharat Bhargava
    Abstract:

    In this paper, we present an open and safe Nested Transaction model. We discuss the concurrency control and recovery algorithms for our model. Our Nested Transaction model uses the notion of a recovery point subTransaction in the Nested Transaction tree. It incorporates a prewrite operation before each write operation to increase the potential concurrency. Our Transaction model is termed ‘‘open and safe’’ as prewrites allow early reads (before writes are performed on disk) without cascading aborts. The systems restart and buAer management operations are also modeled as Nested Transactions to exploit possible concurrency during restart. The concurrency control algorithm proposed for database operations is also used to control concurrent recovery operations. We have given a snapshot of complete Transaction processing, data structures involved and, building the restart state in case of crash recovery. ” 2000 Elsevier Science Inc. All rights reserved.

  • on the correctnes of virtual partition algorithm in a Nested Transaction environment
    Advances in Databases and Information Systems, 1999
    Co-Authors: Sanjay Kumar Madria, S. N. Maheshwari, B. Chandra
    Abstract:

    In this paper, we model the virtual partition algorithm in a Nested Transaction environment using I/O automaton model. The formal description is used to construct a complete correctness proof that is based on standard assertional techniques and on a natural correctness condition, and takes advantage of modularity that arises from describing the algorithm as Nested Transactions. Our presentation and proof treat issues of data replication entirely separately from issues of concurrency control. Moreover, we have identified that virtual partition algorithm can not be proven correct in the sense of Goldman's work [7] on Gifford's Quorum Consensus Algorithm using the serializability theorem defined by Fekete et al.[4]. Thus, we have stated a weaker notion of correctness conditions, which we call reorder serializability theorem.

S. N. Maheshwari - One of the best experts on this subject based on the ideXlab platform.

  • a concurrency control algorithm for an open and safe Nested Transaction model formalization and correctness
    2003
    Co-Authors: Sanjay Kumar Madria, S. N. Maheshwari, B. Chandra
    Abstract:

    In this paper, we formalize and prove the correctness of a concurrency control algo- rithm for an open and safe Nested Transaction using I/O automaton model. The model uses the notion of a recovery point subTransaction in the Nested Transaction tree. Our Nested Transaction model uses a prewrite operation before an actual write operation to increase the concurrency. It is termed "open and safe" as prewrites allow early reads (before database writes on disk) without cascading aborts. In our model we have also modeled the buffer management operations as Nested Transactions, and the concurrency control algorithm controls their executions. Non-access subTransactions, objects and the scheduler are modeled as I/O automata with the help of some pre and post conditions. These conditions capture the operational semantics and behavior of each automaton dur- ing the execution of Transactions. While modeling we also take into account log activities, which occur during the execution of Transactions. We also briefly sketch the recovery algorithm. The correctness proof shows that the concurrency control algorithm for our model is serially correct. Our proof makes use of assertional reasoning and provides many interesting invariant, thus gives a better understanding of our Transaction model and the concurrency control algorithm. While proving correctness, we mapped our sys- tem to that of Moss's two phase locking system to show the relationships between the two algorithms.

  • virtual partition algorithm in a Nested Transaction environment and its correctness
    Information Sciences, 2001
    Co-Authors: Sanjay Kumar Madria, S. N. Maheshwari, B. Chandra
    Abstract:

    Abstract In this paper, we present a formal description of the virtual partition algorithm in a Nested Transaction environment and prove its correctness. We model the virtual partition algorithm in a Nested Transaction environment using the I/O automaton model. The formal description is used to construct a complete correctness proof that is based on standard assertional techniques and on a natural correctness condition, and takes advantage of the modularity that arises from describing the algorithm as Nested Transactions. Our presentation and proof treat issues of data replication entirely separately from issues of concurrency control. Moreover, we have identified that the virtual partition algorithm cannot be proven correct in the sense of Goldman's work [ACM Trans. Database Syst. 19(4) (1994) 537] on Gifford's quorum consensus algorithm using the serializability theorem defined by Fekete et al. [Atomic Transactions, Morgan-Kaufmann, USA, 1994]. Thus, we have stated a weaker notion of correctness conditions, which we call the reorder serializability theorem. We have shown that not all classes of replication algorithms can be proven in the way Goldman has presented the proof of Gifford's quorum consensus algorithm.

  • formalization and proof of correctness of the crash recovery algorithm for an open and safe Nested Transaction model
    International Journal of Cooperative Information Systems, 2001
    Co-Authors: Sanjay Kumar Madria, S. N. Maheshwari, B. Chandra, Bharat Bhargava
    Abstract:

    In this paper, we present, formalize and prove the correctness of recovery algorithm for our open and safe Nested Transaction model using I/O automaton model. Our Nested Transaction model uses the notion of a recovery point subTransaction in the Nested Transaction tree. It introduces a prewrite operation before each write operation to increase the potential concurrency. Our Transaction model is termed as "open and safe" as prewrites allow early reads (before database writes on disk) without cascading aborts. The systems restart and buffer management operations are modelled as Nested Transactions to exploit possible concurrency during restart. Each non-access Transaction, object, and the scheduler is modeled as I/O automaton. Each of these automata is specified with the help of some pre-and post-conditions. These pre-and post-conditions capture the operational semantics and the behavior of each automaton during recovery operations. Our proof technique makes use of assertional reasoning and provide many interesting invariant, thus gives a better understanding of our recovery algorithm.

  • An open and safe Nested Transaction model: concurrency and recovery
    Journal of Systems and Software, 2000
    Co-Authors: Sanjay Kumar Madria, S. N. Maheshwari, B. Chandra, Bharat Bhargava
    Abstract:

    In this paper, we present an open and safe Nested Transaction model. We discuss the concurrency control and recovery algorithms for our model. Our Nested Transaction model uses the notion of a recovery point subTransaction in the Nested Transaction tree. It incorporates a prewrite operation before each write operation to increase the potential concurrency. Our Transaction model is termed ‘‘open and safe’’ as prewrites allow early reads (before writes are performed on disk) without cascading aborts. The systems restart and buAer management operations are also modeled as Nested Transactions to exploit possible concurrency during restart. The concurrency control algorithm proposed for database operations is also used to control concurrent recovery operations. We have given a snapshot of complete Transaction processing, data structures involved and, building the restart state in case of crash recovery. ” 2000 Elsevier Science Inc. All rights reserved.

  • on the correctnes of virtual partition algorithm in a Nested Transaction environment
    Advances in Databases and Information Systems, 1999
    Co-Authors: Sanjay Kumar Madria, S. N. Maheshwari, B. Chandra
    Abstract:

    In this paper, we model the virtual partition algorithm in a Nested Transaction environment using I/O automaton model. The formal description is used to construct a complete correctness proof that is based on standard assertional techniques and on a natural correctness condition, and takes advantage of modularity that arises from describing the algorithm as Nested Transactions. Our presentation and proof treat issues of data replication entirely separately from issues of concurrency control. Moreover, we have identified that virtual partition algorithm can not be proven correct in the sense of Goldman's work [7] on Gifford's Quorum Consensus Algorithm using the serializability theorem defined by Fekete et al.[4]. Thus, we have stated a weaker notion of correctness conditions, which we call reorder serializability theorem.

Nudt Changsha - One of the best experts on this subject based on the ideXlab platform.