Thumbnail
Access Restriction
Subscribed

Author Sagiv, Yehoshua
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1991
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Chase ♦ Expanded cover ♦ Extension join ♦ Functional dependency ♦ Independent database scheme ♦ Join dependency ♦ Lossless join ♦ Null value ♦ Query evaluation ♦ Relational algebra ♦ Relational database ♦ Representative instance ♦ Restricted projection ♦ Tableau ♦ Union of tableaux
Abstract A simple characterization of independent database schemes is proved. An algorithm is given for translating a tableau $\textit{T},$ posed as a query on a representative instance, to a union of tableaux that is equivalent to $\textit{T},$ but can be applied directly to database relations. The algorithm may take exponential time (in the size of $\textit{T}$ and the database scheme), and it is applicable only to independent database schemes. If $\textit{T}$ is a just a projection of a representative instance, then the algorithm has a simpler form (which is still exponential in the worst case) and is polynomial in some cases.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1991-01-03
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 38
Issue Number 1
Page Count 42
Starting Page 120
Ending Page 161


Open content in new tab

   Open content in new tab
Source: ACM Digital Library