Relational transducer
Model of computation used in databases
From Wikipedia, the free encyclopedia
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
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 ω
