Data processing: database and file management or data structures – Database and file access – Query optimization
Reexamination Certificate
2011-06-14
2011-06-14
Cottingham, John R. (Department: 2167)
Data processing: database and file management or data structures
Database and file access
Query optimization
C707S741000, C715S200000
Reexamination Certificate
active
07962473
ABSTRACT:
Techniques are provided for performing structural joins for answering containment queries. Such inventive techniques may be used to perform efficient structural joins of two interval lists which are neither sorted nor pre-indexed. For example, in an illustrative aspect of the invention, a technique for performing structural joins of two element sets of a tree-structured document, wherein one of the two element sets is an ancestor element set and the other of the two element sets is a descendant element set, and further wherein each element is represented as an interval representing a start position and an end position of the element in the document, comprises the following steps/operations. An index is dynamically built for the ancestor element set. Then, one or more structural joins are performed by searching the index with the interval start position of each element in the descendant element set.
REFERENCES:
patent: 5761652 (1998-06-01), Wu et al.
patent: 5781906 (1998-07-01), Aggarwal et al.
patent: 5806065 (1998-09-01), Lomet
patent: 5875445 (1999-02-01), Antonshenkov
patent: 5987468 (1999-11-01), Singh et al.
patent: 6289334 (2001-09-01), Reiner et al.
patent: 6289906 (2001-09-01), Vanden Dries et al.
patent: 6711563 (2004-03-01), Koskas
patent: 7010522 (2006-03-01), Jagadish et al.
patent: 7016904 (2006-03-01), Grove et al.
patent: 7219091 (2007-05-01), Bruno et al.
patent: 2003/0154189 (2003-08-01), Egilsson et al.
patent: 2004/0064441 (2004-04-01), Tow
patent: 2005/0071322 (2005-03-01), Chen et al.
patent: 2006/0184551 (2006-08-01), Tarachandani et al.
Wei Wang et al., PBiTree: Coding and Efficient Processing of Containment Joins, Mar. 2003, Proceedings of IEEE ICDE, pp. 1-12.
K.-L. Wu and P.S. Yu, “Efficient query monitoring using adaptive multiple key hashing”, Nov. 2002, In Proc. of ACM Int. Conf. on Information and Knowledge Management, pp. 447-484.
U.S. Appl. No. 10/982,570, filed Nov. 5, 2004, S-K. Chen et al.
A. Guttman, “R-trees: A Dynamic Index Structure for Spatial Searching,” Proceedings of the ACM SIGMOD, 1984.
E. Hanson, et al., “Selection Predicate Indexing for Active Databases Using Interval Skip Lists,” Information Systems, 21(3):269-298, 1996.
E. Hanson, et al., “A Predicate Matching Algorithm for Database Rule Systems,” Proceedings of ACM SIGMOD, 1990.
E.N. Hanson et al., “The Interval Skip List: A Data Structure for Finding All Intervals that Overlap a Point,” Technical Report TR92-016, Computer and Information Sciences Department, Florida, pp. 1-16, Jun. 1992.
C. Zhang et al., “On Supporting Containment Queries in Relational Database Management Systems,” Proceedings of ACM SIGMOD 2001.
D. Srivastava et al., “Structural Joints: A Primitive for Efficient XML Query Pattern Matching,” Proceedings of IEEE International Conference on Data Engineering, 2002.
S.-Y. Chien et al., “Efficient Structural Joins on Indexed XML Documents,” Proceedings of VLDB, 2002.
H. Jiang et al., “XR-tree: Indexing XML Data for Efficient Structural Joins” Proceedings of IEEE International Conference on Data Engineering, 2003.
W. Wang et al., “PBiTree: Coding and Efficient Processing of Containment Joins,” Proceedings of IEEE ICDE, 2003.
U.S. Appl. No. 10/673,651, filed Sep. 23, 2003, S-K. Chen et al.
C.P. Kolovoson et al., “Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data,” Procedures of ACM SIGMOD International Conference on Management of Data, Apr. 1991, pp. 139-147, vol. 20, No. 2.
S. Madden et al., “Continuously Adaptive Continuous Queries Over Streams,” Procedures of ACM SIGMOD International Conference on Management of Data, Jun. 2002, pp. 49-60.
Chen Shyh-Kwei
Wu Kun-Lung
Yu Philip Shi-Lung
Badawi Sherief
Cottingham John R.
International Business Machines - Corporation
Ryan & Mason & Lewis, LLP
Stock William
LandOfFree
Methods and apparatus for performing structural joins for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for performing structural joins for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for performing structural joins for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2654374