Estimating the size of generalized transitive closures
作者： J. F. Naughton , R. J. Lipton
DOI:
关键词:
摘要: We present a framework for the estimation of size binary recursively defined relations. show how can be used to provide estimating algo rithms transitive closure and generalizations closure, also that bounded degree relations, algorithm runs in linear time. Such algorithms are essential if database systems support recursive relations or fixpoints able optimize queries avoid infeasible computations.
acm.org参考文章(18)
Robert Demolombe, Estimation of the number of tuples satisfying a query expressed in predicate calculus language very large data bases. pp. 55- 63 ,(1980)
Carlo Zaniolo, Ravi Krishnamurthy, Haran Boral, Optimization of Nonrecursive Queries very large data bases. pp. 128- 137 ,(1986)
Yannis E. Ioannidis, Raghu Ramakrishnan, Efficient Transitive Closure Algorithms very large data bases. pp. 382- 394 ,(1988)
Hongjun Lu, New Strategies for Computing the Transitive Closure of a Database Relation very large data bases. pp. 267- 274 ,(1987)
H. V. Jagadish, Rakesh Agrawal, Direct Algorithms for Computing the Transitive Closure of Database Relations very large data bases. pp. 255- 266 ,(1987)
Yannis E. Ioannidis, On the Computation of the Transitive Closure of Relational Operators very large data bases. pp. 403- 411 ,(1986)
Clifford A. Lynch, Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distribution of Column Values very large data bases. pp. 240- 251 ,(1988)
Neil C. Rowe, Top-down statistical estimation on a database Proceedings of the 1983 ACM SIGMOD international conference on Management of data - SIGMOD '83. ,vol. 13, pp. 135- 145 ,(1983) , 10.1145/582192.582217
Wen-Chi Hou, Gultekin Ozsoyoglu, Baldeo K. Taneja, Statistical estimators for relational algebra expressions symposium on principles of database systems. pp. 276- 287 ,(1988) , 10.1145/308386.308455
Gregory Piatetsky-Shapiro, Charles Connell, Accurate estimation of the number of tuples satisfying a condition Proceedings of the 1984 ACM SIGMOD international conference on Management of data - SIGMOD '84. ,vol. 14, pp. 256- 276 ,(1984) , 10.1145/602259.602294