serial

A Ruby script that takes a schedule of database transactions and outputs its serialization graph in the DOT language. If the schedule is serializable, it also outputs the graph of an equivalent serial schedule.

Usage

The script takes a schedule of database transactions as its single argument. A schedule is a sequence of commands; each command consists of an action, a transaction identifier, and the action object enclosed in parentheses or square brackets. Commands can optionally be separated by whitespace.

Valid actions include R (for read) and W (for write). Valid transaction identifiers include all non-negative integers. Valid objects include all letters of the Latin alphabet (A through Z). Anything else is ignored.

For example, any of the following commands:

ruby serial.rb R1[A]R2[A]W2[B]R1[D]W1[C]R3[B]R3[C]W3[D]W2[A]
ruby serial.rb 'R1(A)R2(A)W2(B)R1(D)W1(C)R3(B)R3(C)W3(D)W2(A)'
ruby serial.rb 'R1(A) R2(A) W2(B) R1(D) W1(C) R3(B) R3(C) W3(D) W2(A)'

Would result in the following output:

digraph serialization {
  rankdir = LR;

  T1 -> T2 [label="A"];
  T2 -> T3 [label="B"];
  T1 -> T3 [label="C, D"];
}

digraph serial {
  rankdir = LR;

  T1 -> T2 [label="A"];
  T2 -> T3 [label="B"];
}

Visualizing the output with Graphviz is easy:

ruby serial.rb R1[A]R2[A]W2[B]R1[D]W1[C]R3[B]R3[C]W3[D]W2[A] >example.dot
head -n 7 example.dot >serialization.dot
tail -n 6 example.dot >serial.dot
dot -T png -o serialization.png serialization.dot
dot -T png -o serial.png serial.dot

The serialization graph rendered with Graphviz:

And the serial graph:

Dependencies

Graph descriptions are in the DOT language. To turn them into images, you will need to have Graphviz installed.

License

The MIT License

Copyright (c) 2010 Aggelos Orfanakos

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Author

Aggelos Orfanakos, http://agorf.gr/