Article

Estimating the size of generalized transitive closures

Authors:

R. J. Lipton,

J. F. NaughtonAuthors Info & Claims

VLDB '89: Proceedings of the 15th international conference on Very large data bases

Pages 165 - 171

Published: 01 July 1989 Publication History

Abstract

No abstract available.

References

[1]

[AJ87] Rakesh Agrawal, H. V. Jagadish: Direct Algorithms for Computing the Transitive Closure of Database Relations. VLDB 1987: 255-266.

Digital Library

Google Scholar

[2]

[Chr83] Stavros Christodoulakis: Estimating Block Transfers and Join Sizes. SIGMOD Conference 1983: 40-54.

Digital Library

Google Scholar

[3]

[Dem80] Robert Demolombe: Estimation of the Number of Tuples Satisfying a Query Expressed in Predicate Calculus Language. VLDB 1980: 55-63.

Google Scholar

[4]

[HOT88] Wen-Chi Hou, Gultekin özsoyoglu, Baldeo K. Taneja: Statistical Estimators for Relational Algebra Expressions. PODS 1988: 276-287.

Digital Library

Google Scholar

[5]

[Ioa86] Yannis E. Ioannidis: On the Computation of the Transitive Closure of Relational Operators. VLDB 1986: 403-411.

Digital Library

Google Scholar

[6]

[IR88] Yannis E. Ioannidis, Raghu Ramakrishnan: Efficient Transitive Closure Algorithms. VLDB 1988: 382-394.

Digital Library

Google Scholar

[7]

[IW87] Yannis E. Ioannidis, Eugene Wong: Query Optimization by Simulated Annealing. SIGMOD Conference 1987: 9-22.

Digital Library

Google Scholar

[8]

[KBZ86] Ravi Krishnamurthy, Haran Boral, Carlo Zaniolo: Optimization of Nonrecursive Queries. VLDB 1986: 128-137.

Digital Library

Google Scholar

[9]

[LMR87] Hongjun Lu, Krishna P. Mikkilineni, James P. Richardson: Design and Evaluation of Algorithms to Compute the Transitive Closure of a Database Relation. ICDE 1987: 112-119.

Digital Library

Google Scholar

[10]

[LN89] Richard J. Lipton and Jeffrey F. Naughton. Estimating the size of the transitive closure of a digraph. Submitted for publication, May 1989.

Google Scholar

[11]

[Lu87] Hongjun Lu: New Strategies for Computing the Transitive Closure of a Database Relation. VLDB 1987: 267-274.

Digital Library

Google Scholar

[12]

[Lyn88] Clifford A. Lynch: Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distribution of Column Values. VLDB 1988: 240-251.

Digital Library

Google Scholar

[13]

[Nau87] Jeffrey F. Naughton: One-Sided Recursions. PODS 1987: 340-348.

Digital Library

Google Scholar

[14]

[NSRU89] Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Evaluation of Right-, Left-, and Mult-Lineare Rules. SIGMOD Conference 1989: 235-242.

Digital Library

Google Scholar

[15]

[PSC84] Gregory Piatetsky-Shapiro, Charles Connell: Accurate Estimation of the Number of Tuples Satisfying a Condition. SIGMOD Conference 1984: 256-276.

Digital Library

Google Scholar

[16]

[RHDM86] Arnon Rosenthal, Sandra Heiler, Umeshwar Dayal, Frank Manola: Traversal Recursion: A Practical Approach to Supporting Recursive Applications. SIGMOD Conference 1986: 166-176.

Digital Library

Google Scholar

[17]

[Row83] Neil C. Rowe: Top-Down Statistical Estimation on a Database. SIGMOD Conference 1983: 135-145.

Digital Library

Google Scholar

[18]

[SG85] David E. Smith, Michael R. Genesereth: Ordering Conjunctive Queries. Artif. Intell. 26(2): 171-215(1985).

Digital Library

Google Scholar

[19]

[SG88] Arun N. Swami, Anoop Gupta: Optimization of Large Join Queries. SIGMOD Conference 1988: 8-17.

Digital Library

Google Scholar

Cited By

View all

Borassi MNatale E(2019)KADABRA is an ADaptive Algorithm for Betweenness via Random ApproximationACM Journal of Experimental Algorithmics10.1145/328435924(1-35)Online publication date: 20-Feb-2019
https://dl.acm.org/doi/10.1145/3284359
Heise AKasneci GNaumann FLi JWang XGarofalakis MSoboroff ISuel TWang M(2014)Estimating the Number and Sizes of Fuzzy-Duplicate ClustersProceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management10.1145/2661829.2661885(959-968)Online publication date: 3-Nov-2014
https://dl.acm.org/doi/10.1145/2661829.2661885
Ghazal ASeid DCrolotte AAl-Kateb MCandan KChen YSnodgrass RGravano LFuxman A(2012)Adaptive optimizations of recursive queries in teradataProceedings of the 2012 ACM SIGMOD International Conference on Management of Data10.1145/2213836.2213966(851-860)Online publication date: 20-May-2012
https://dl.acm.org/doi/10.1145/2213836.2213966
Show More Cited By

Index Terms

Estimating the size of generalized transitive closures

Recommendations

Complements and transitive closures

The complement of the transitive closure of the complement of a transitive relation is transitive. We prove this fact in three ways, analyze the underlying structure and consider various refinement's and applications.
Estimating the size of the transitive closure in linear time
SFCS '94: Proceedings of the 35th Annual Symposium on Foundations of Computer Science

Computing transitive closure and reachability information in directed graphs is a fundamental graph problem with many applications. The fastest known algorithms run in O(sm) time for computing all nodes reachable from each of 1/spl les/s/spl les/n ...
Computing transitive closures of hedge transformations
VECoS'07: Proceedings of the First international conference on Verification and Evaluation of Computer and Communication Systems

We consider the framework of regular hedge model checking where configurations are represented by trees of arbitrary arities, sets of configurations are represented by regular hedge automata, and the dynamic of a system is modeled by a term rewriting ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

VLDB '89: Proceedings of the 15th international conference on Very large data bases

July 1989

467 pages

ISBN:1558601015

Chairman:
Reind P. van de Riet
Vrije Univ., Amsterdam, The Netherlands

Publisher

Morgan Kaufmann Publishers Inc.

San Francisco, CA, United States

Publication History

Published: 01 July 1989

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

32
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Borassi MNatale E(2019)KADABRA is an ADaptive Algorithm for Betweenness via Random ApproximationACM Journal of Experimental Algorithmics10.1145/328435924(1-35)Online publication date: 20-Feb-2019
https://dl.acm.org/doi/10.1145/3284359
Heise AKasneci GNaumann FLi JWang XGarofalakis MSoboroff ISuel TWang M(2014)Estimating the Number and Sizes of Fuzzy-Duplicate ClustersProceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management10.1145/2661829.2661885(959-968)Online publication date: 3-Nov-2014
https://dl.acm.org/doi/10.1145/2661829.2661885
Ghazal ASeid DCrolotte AAl-Kateb MCandan KChen YSnodgrass RGravano LFuxman A(2012)Adaptive optimizations of recursive queries in teradataProceedings of the 2012 ACM SIGMOD International Conference on Management of Data10.1145/2213836.2213966(851-860)Online publication date: 20-May-2012
https://dl.acm.org/doi/10.1145/2213836.2213966
Liang SKifer M(2012)Deriving predicate statistics for logic rulesProceedings of the 6th international conference on Web Reasoning and Rule Systems10.1007/978-3-642-33203-6_11(139-155)Online publication date: 10-Sep-2012
https://dl.acm.org/doi/10.1007/978-3-642-33203-6_11
Alahakoon TTripathi RKourtellis NSimha RIamnitchi A(2011)K-path centralityProceedings of the 4th Workshop on Social Network Systems10.1145/1989656.1989657(1-6)Online publication date: 10-Apr-2011
https://dl.acm.org/doi/10.1145/1989656.1989657
Liang SKifer MKutsia TSchreiner WFernández M(2010)Deriving predicate statistics in datalogProceedings of the 12th international ACM SIGPLAN symposium on Principles and practice of declarative programming10.1145/1836089.1836095(45-56)Online publication date: 26-Jul-2010
https://dl.acm.org/doi/10.1145/1836089.1836095
Sereni DAvgustinov Pde Moor OLakshmanan LNg RShasha D(2008)Adding magic to an optimising datalog compilerProceedings of the 2008 ACM SIGMOD international conference on Management of data10.1145/1376616.1376673(553-566)Online publication date: 9-Jun-2008
https://dl.acm.org/doi/10.1145/1376616.1376673
Becchetti LCastillo CDonato DBaeza-YATES RLeonardi S(2008)Link analysis for Web spam detectionACM Transactions on the Web10.1145/1326561.13265632:1(1-42)Online publication date: 3-Mar-2008
https://dl.acm.org/doi/10.1145/1326561.1326563
Bader DKintali SMadduri KMihail M(2007)Approximating betweenness centralityProceedings of the 5th international conference on Algorithms and models for the web-graph10.5555/1777879.1777889(124-137)Online publication date: 11-Dec-2007
https://dl.acm.org/doi/10.5555/1777879.1777889
Donato DPaniccia MSelis MCastillo CCortese GLeonardi SCastillo CChellapilla KDavison B(2007)New metrics for reputation management in P2P networksProceedings of the 3rd international workshop on Adversarial information retrieval on the web10.1145/1244408.1244421(65-72)Online publication date: 8-May-2007
https://dl.acm.org/doi/10.1145/1244408.1244421
Show More Cited By

Abstract

References

Cited By

Index Terms

Recommendations

Complements and transitive closures

Estimating the size of the transitive closure in linear time

Computing transitive closures of hedge transformations

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations