Discovering functional dependencies by sampling relations

Details Discovering functional dependencies by sampling relations Discovering functional dependencies by sampling relations

2011-01-18

2011-01-18

Pham, Khanh B (Department: 2166)

Data processing: database and file management or data structures

Database and file access

Query optimization

C707S713000

Reexamination Certificate

active

07873628

ABSTRACT:
To discover functional dependencies in a large relation, a sample of tuples from the relation is collected. The sample is examined to determine whether one or more candidate functional dependencies exist just within the sample as a nominal dependency. When a nominal dependency is found in the sample, than all the tuples in the relation are examined to verify whether the nominal dependency holds for the whole relation. Candidate functional dependencies are disqualified when either a nominal dependency is found or when it is verified as functional dependency that holds for the entire relation.

REFERENCES:
patent: 5481703 (1996-01-01), Kato
patent: 6012064 (2000-01-01), Gibbons et al.
patent: 6353826 (2002-03-01), Seputis
patent: 6496819 (2002-12-01), Bello et al.
patent: 6615206 (2003-09-01), Jakobsson et al.
patent: 6754652 (2004-06-01), Bestgen et al.
patent: 6801905 (2004-10-01), Andrei
patent: 6865567 (2005-03-01), Oommen et al.
patent: 6934695 (2005-08-01), Kase et al.
patent: 7007009 (2006-02-01), Bestgen et al.
patent: 7007032 (2006-02-01), Chen et al.
patent: 7010521 (2006-03-01), Hinshaw et al.
patent: 2005/0097072 (2005-05-01), Brown et al.
patent: 2005/0102325 (2005-05-01), Gould et al.
patent: 2005/0240615 (2005-10-01), Barsness et al.
Frank Olken et al., “Random Sampling from Databases—A Survey,” Mar. 22, 1994, pp. 1-54.
Frank Olken, “Random Sampling from Databases,” 1993, 172 pages.
Frank Olken et al., “Random Sampling from B+trees,” Proceedings of the International Conference on Very Large Data Bases, Amsterdam, 1989, 9 pages.
Dan E. Willard, “Optimal Sample Cost Residues for Differential Database Batch Query Problems,” Journal of the Association for Computing Machinery, vol. 38. No. 1, Jan. 1991, pp. 104-119.
Sumit Ganguly et al., “Bifocal Sampling for Skew-Resistant Join Size Estimation,” ACM SIGMOD '96, Montreal, Canada, ACM, 1996, pp. 271-281.
Peter J. Haas et al., “Fixed-Precision Estimation of Join Selectivity,” ACM, PODS, May 1993, Washington, D.C., pp. 190-201.
Yi-Leh Wu et al., “Applying the Golden Rule of Sampling for Query Estimation,” ACM SIGMOD 2001, May 21-24 Santa Barbara, California, pp. 449-460.
Peter J. Haas et al., “On the Relative Cost of Sampling for Join Selectivity Estimation,” SIGMODS/PODS '94, May 1994, Minneapolis, Minnesota, pp. 14-24.
Peter J. Haas et al., “Sequential Sampling Procedures for Query Size Estimation,” 1992 ACM SIGMOD, Jun. 1992, pp. 341-350.
Richard J. Lipton et al., “Practical Selectivity Estimation through Adaptive Sampling,” 1990, ACM, pp. 1-11.
Kenneth W. Ng et al., “On Reconfiguring Query Execution Plans in Distributed Object-Relational DBMS,” Dec. 14-16, 1998, 1998 International Conference on Parallel and Distributed Systems, Dec. 1998, 9 pages.
Chun-Nan Hsu et al., “Semantic Query Optimization for Query Plans of Heterogeneous Multidatabase Systems,” IEEE Transactions on Knowledge and Data Engineering, vol. 12, No. 6, Nov./Dec. 2000, pp. 959-978.
Fotis Barlos et al., “On Development of a Site Selection Optimizer for Distributed and Parallel Database Systems,” CIKM '93, Washington D.C., USA, pp. 684-693.
Siegfried Bell et al., “Discovery of Data Dependencies in Relational Databases,” Informatik VIII, University Dortmund, Germany, 6 pages.
Catherine Wyss et al., “Fast FDs: A Heuristic-Driven, Depth-First Algorithm for Mining Functional Dependencies from Relation Instances,” Computer Science Dept., Indiana University Bloomington, IN, USA, pp. 1-23.
Yka Huhtala et al., “TANE: An Efficient Algorithm for Discovering Functional and Approximate Dependencies,” The Computer Journal, vol. 42, No. 2, 1999, pp. 100-111.
Heikki Mannila et al., “Dependency Inference,” Proceedings of the 13thVLDB Conference, Brighton 1987, pp. 155-158.
Iztok Savnik and Peter A. Flach, “Bottom-up Induction of Functional Dependencies from Relations,” Jozef Stefan Institute, Ljubljana, Slovenija and Institute for Language Technology & Artificial Intelligence, Tilbury University, Tilburg, the Netherlands, 13 pages.

Affiliated with

Also associated with

Rating

Discovering functional dependencies by sampling relations does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Discovering functional dependencies by sampling relations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Discovering functional dependencies by sampling relations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2744456