Relational transducer explained

Relational transducers are a theoretical model for studying computer systems through the lens of database relations. This model extends the transducer model in formal language theory. They were first introduced in 1998 by Abiteboul et al for the study of electronic commerce applications.^[1] The computation model treats the input and output as sequences of relations. The state of the transducer is a state of a database and transitions through the state machine can be thought of as updates to the database state. The model was inspired by the design of active databases and motivated by a desire to be able to express business applications declaratively via logical formulas.

Applications

The relational transducer model has been applied to the study of computer network management,^[2] e-commerce platforms,^[3] and coordination-free distributed systems.^{[4] [5] [6] [7]}

Formal specification

A relational transducer has a schema made up of five components: In, State, Out, DB, and Log. In and Out represent the inputs to the system from users and the outputs back to the users respectively. DB represents the contents of the database and State represents the information that the system remembers. The Log contains the important subset of the inputs and outputs.

The relational schemas of each component are disjoint except for Log which is a subset of In ∪ Out.

A relational transducer over a relational transducer schema is made up of three parts:

• The schema
• A state transition function σ
• An output function ω

Related models

Models of computation extending on relational transducers have been developed including the Distributed Shared Relations model^[8] for synchronous distributed systems and the Abstract State Machine Transducer model for verification of transaction protocols.

Notes and References

1. Abiteboul . Serge . Vianu . Victor . Fordham . Brad . Yesha . Yelena . Relational Transducers for Electronic Commerce . Journal of Computer and System Sciences . 61 . 2 . 2000 . 10.1006/jcss.2000.1708 . 236–269. free .
2. Kohli, Madhur, and Jorge Lobo. "Policy based management of telecommunication networks." Policy Workshop 1999. 1999.
3. Spielmann . Marc . Verification of relational transducers for electronic commerce . Journal of Computer and System Sciences . 66 . 1 . 2003 . 10.1016/S0022-0000(02)00029-6 . 40–65.
4. Ameloot . Tom J. . Neven . Frank . Van den Bussche . Jan . Proceedings of the thirtieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems . Relational transducers for declarative networking . ACM . 2011-06-13 . 978-1-4503-0660-7 . 10.1145/1989284.1989321 . 283–292. 1012.2858 .
5. Ameloot . Tom J. . Van den Bussche . Jan . Proceedings of the 15th International Conference on Database Theory . Deciding eventual consistency for a simple class of relational transducer networks . ACM . 2012-03-26 . 978-1-4503-0791-8 . 10.1145/2274576.2274587 . 86–98. 1942/16394 . free .
6. Zinn . Daniel . Green . Todd J. . Ludäscher . Bertram . Proceedings of the 15th International Conference on Database Theory . Win-move is coordination-free (sometimes) . ACM . 2012-03-26 . 978-1-4503-0791-8 . 10.1145/2274576.2274588 . 99–113. 1312.2919 .
7. Baccaert . Tim . Ketsman . Bas . Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems . Distributed Consistency Beyond Queries . ACM . 2023-06-18 . 979-8-4007-0127-6 . 10.1145/3584372.3588657 . 47–58.
8. Interlandi, Matteo, Letizia Tanca, and Sonia Bergamaschi. "Datalog in Time and Space, Synchronously." AMW 1087 (2013).