Relational transducer

Last updated

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.

Contents

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:

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.

Related Research Articles

NonStop SQL is a commercial relational database management system that is designed for fault tolerance and scalability, currently offered by Hewlett Packard Enterprise. The latest version is SQL/MX 3.4.

<span class="mw-page-title-main">Database schema</span> Visual representation of database system relationships

The database schema is the structure of a database described in a formal language supported typically by a relational database management system (RDBMS). The term "schema" refers to the organization of data as a blueprint of how the database is constructed. The formal definition of a database schema is a set of formulas (sentences) called integrity constraints imposed on a database. These integrity constraints ensure compatibility between parts of the schema. All constraints are expressible in the same language. A database can be considered a structure in realization of the database language. The states of a created conceptual schema are transformed into an explicit mapping, the database schema. This describes how real-world entities are modeled in the database.

Datalog is a declarative logic programming language. While it is syntactically a subset of Prolog, Datalog generally uses a bottom-up rather than top-down evaluation model. This difference yields significantly different behavior and properties from Prolog. It is often used as a query language for deductive databases. Datalog has been applied to problems in data integration, networking, program analysis, and more.

<span class="mw-page-title-main">MonetDB</span> Open source column-oriented relational database management system

MonetDB is an open-source column-oriented relational database management system (RDBMS) originally developed at the Centrum Wiskunde & Informatica (CWI) in the Netherlands. It is designed to provide high performance on complex queries against large databases, such as combining tables with hundreds of columns and millions of rows. MonetDB has been applied in high-performance applications for online analytical processing, data mining, geographic information system (GIS), Resource Description Framework (RDF), text retrieval and sequence alignment processing.

Replication in computing involves sharing information so as to ensure consistency between redundant resources, such as software or hardware components, to improve reliability, fault-tolerance, or accessibility.

M. Dale Skeen is an American computer scientist. He specializes in designing and implementing large-scale computing systems, distributed computing and database management systems.

A fundamental problem in distributed computing and multi-agent systems is to achieve overall system reliability in the presence of a number of faulty processes. This often requires coordinating processes to reach consensus, or agree on some data value that is needed during computation. Example applications of consensus include agreeing on what transactions to commit to a database in which order, state machine replication, and atomic broadcasts. Real-world applications often requiring consensus include cloud computing, clock synchronization, PageRank, opinion formation, smart power grids, state estimation, control of UAVs, load balancing, blockchain, and others.

<span class="mw-page-title-main">Serge Abiteboul</span> French computer scientist

Serge Joseph Abiteboul is a French computer scientist working in the areas of data management, database theory, and finite model theory.

<span class="mw-page-title-main">Patricia Selinger</span> American computer scientist and IBM Fellow

Patricia G. Selinger is an American computer scientist and IBM Fellow, best known for her work on relational database management systems.

In computer science, streaming algorithms are algorithms for processing data streams in which the input is presented as a sequence of items and can be examined in only a few passes, typically just one. These algorithms are designed to operate with limited memory, generally logarithmic in the size of the stream and/or in the maximum value in the stream, and may also have limited processing time per item.

<span class="mw-page-title-main">Michael Stonebraker</span> American computer scientist (born 1943)

Michael Ralph Stonebraker is a computer scientist specializing in database systems. Through a series of academic prototypes and commercial startups, Stonebraker's research and products are central to many relational databases. He is also the founder of many database companies, including Ingres Corporation, Illustra, Paradigm4, StreamBase Systems, Tamr, Vertica and VoltDB, and served as chief technical officer of Informix. For his contributions to database research, Stonebraker received the 2014 Turing Award, often described as "the Nobel Prize for computing."

<span class="mw-page-title-main">Tomasz Imieliński</span> Polish-American computer scientist (born 1954)

Tomasz Imieliński is a Polish-American computer scientist, most known in the areas of data mining, mobile computing, data extraction, and search engine technology. He is currently a professor of computer science at Rutgers University in New Jersey, United States.

Dataspaces are an abstraction in data management that aim to overcome some of the problems encountered in data integration system. The aim is to reduce the effort required to set up a data integration system by relying on existing matching and mapping generation techniques, and to improve the system in "pay-as-you-go" fashion as it is used. Labor-intensive aspects of data integration are postponed until they are absolutely needed.

Patrick Eugene O'Neil was an American computer scientist, an expert on databases, and a professor of computer science at the University of Massachusetts Boston.

In relational database theory, a tuple-generating dependency (TGD) is a certain kind of constraint on a relational database. It is a subclass of the class of embedded dependencies (EDs).

In database theory, Imieliński–Lipski algebra is an extension of relational algebra onto tables with different types of null values. It is used to operate on relations with incomplete information.

<span class="mw-page-title-main">Witold Lipski</span> Polish computer scientist

Witold Lipski Jr. was a Polish computer scientist, and an author of two books: Combinatorics for Programmers and (jointly with Wiktor Marek Combinatorial analysis. Lipski, jointly with his PhD student, Tomasz Imieliński, created foundations of the theory of incomplete information in relational databases.

GQL is a proposed standard graph query language. In September 2019 a proposal for a project to create a new standard graph query language was approved by a vote of national standards bodies which are members of ISO/IEC Joint Technical Committee 1(ISO/IEC JTC 1). JTC 1 is responsible for international Information Technology standards. GQL is intended to be a declarative database query language, like SQL.

Daniel Abadi is the Darnell-Kanal Professor of Computer Science at University of Maryland, College Park. His primary area of research is database systems, with contributions to stream databases, distributed databases, graph databases, and column-store databases. He helped create C-Store, a column-oriented database, and HadoopDB, a hybrid of relational databases and Hadoop. Both database systems were commercialized by companies.

In database theory, the query evaluation problem is the problem of determining the answers to a query on a database. Research in database theory aims at determining the computational complexity of answering different kinds of queries over databases, in particular over relational databases.

References

  1. 1 2 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. 1 2 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". Proceedings of the thirtieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. ACM. pp. 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". Proceedings of the 15th International Conference on Database Theory. ACM. pp. 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)". Proceedings of the 15th International Conference on Database Theory. ACM. pp. 99–113. arXiv: 1312.2919 . doi:10.1145/2274576.2274588. ISBN   978-1-4503-0791-8.
  7. ↑ Baccaert, Tim; Ketsman, Bas (2023-06-18). "Distributed Consistency Beyond Queries". Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. ACM. pp. 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).
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.