Recent from talks
Knowledge base stats:
Talk channels stats:
Members stats:
Chase (algorithm)
The chase is a simple fixed-point algorithm testing and enforcing implication of data dependencies in database systems. It plays important roles in database theory as well as in practice. It is used, directly or indirectly, on an everyday basis by people who design databases, and it is used in commercial systems to reason about the consistency and correctness of a data design.[citation needed] New applications of the chase in meta-data management and data exchange are still being discovered.
The chase has its origins in two seminal papers of 1979, one by Alfred V. Aho, Catriel Beeri, and Jeffrey D. Ullman and the other by David Maier, Alberto O. Mendelzon, and Yehoshua Sagiv.
In its simplest application the chase is used for testing whether the projection of a relation schema constrained by some functional dependencies onto a given decomposition can be recovered by rejoining the projections. Let t be a tuple in where R is a relation and F is a set of functional dependencies (FD). If tuples in R are represented as t1, ..., tk, the join of the projections of each ti should agree with t on where i = 1, 2, ..., k. If ti is not on , the value is unknown.
The chase can be done by drawing a tableau (which is the same formalism used in tableau query). Suppose R has attributes A, B, ... and components of t are a, b, .... For ti use the same letter as t in the components that are in Si but subscript the letter with i if the component is not in Si. Then, ti will agree with t if it is in Si and will have a unique value otherwise.
The chase process is confluent. There exist implementations of the chase algorithm, some of them are also open-source.
Let R(A, B, C, D) be a relation schema known to obey the set of functional dependencies F = {A→B, B→C, CD→A}. Suppose R is decomposed into three relation schemas S1 = {A, D}, S2 = {A, C} and S3 = {B, C, D}. Determining whether this decomposition is lossless can be done by performing a chase as shown below.
The initial tableau for this decomposition is:
The first row represents S1. The components for attributes A and D are unsubscripted and those for attributes B and C are subscripted with i = 1. The second and third rows are filled in the same manner with S2 and S3 respectively.
Hub AI
Chase (algorithm) AI simulator
(@Chase (algorithm)_simulator)
Chase (algorithm)
The chase is a simple fixed-point algorithm testing and enforcing implication of data dependencies in database systems. It plays important roles in database theory as well as in practice. It is used, directly or indirectly, on an everyday basis by people who design databases, and it is used in commercial systems to reason about the consistency and correctness of a data design.[citation needed] New applications of the chase in meta-data management and data exchange are still being discovered.
The chase has its origins in two seminal papers of 1979, one by Alfred V. Aho, Catriel Beeri, and Jeffrey D. Ullman and the other by David Maier, Alberto O. Mendelzon, and Yehoshua Sagiv.
In its simplest application the chase is used for testing whether the projection of a relation schema constrained by some functional dependencies onto a given decomposition can be recovered by rejoining the projections. Let t be a tuple in where R is a relation and F is a set of functional dependencies (FD). If tuples in R are represented as t1, ..., tk, the join of the projections of each ti should agree with t on where i = 1, 2, ..., k. If ti is not on , the value is unknown.
The chase can be done by drawing a tableau (which is the same formalism used in tableau query). Suppose R has attributes A, B, ... and components of t are a, b, .... For ti use the same letter as t in the components that are in Si but subscript the letter with i if the component is not in Si. Then, ti will agree with t if it is in Si and will have a unique value otherwise.
The chase process is confluent. There exist implementations of the chase algorithm, some of them are also open-source.
Let R(A, B, C, D) be a relation schema known to obey the set of functional dependencies F = {A→B, B→C, CD→A}. Suppose R is decomposed into three relation schemas S1 = {A, D}, S2 = {A, C} and S3 = {B, C, D}. Determining whether this decomposition is lossless can be done by performing a chase as shown below.
The initial tableau for this decomposition is:
The first row represents S1. The components for attributes A and D are unsubscripted and those for attributes B and C are subscripted with i = 1. The second and third rows are filled in the same manner with S2 and S3 respectively.