Relational transducer

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,^[1][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^[3] for verification of transaction protocols.

References

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