Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-04-17
2004-04-27
Vu, Kim (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06728694
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates in general to database management systems performed by computers, and in particular, to a set containment join operation performed in an object/relational database management system.
2. Description of Related Art
(Note: This application references a number of different publications as indicated throughout the specification by reference numbers enclosed in brackets, e.g., [x]. A list of these different publications ordered according to these reference numbers can be found in the “Detailed Description of the Preferred Embodiment” in Section 6 entitled “References.” Each of these publications is incorporated by reference herein.)
The data modeling community has long realized that set-valued attributes provide a concise and natural way of modeling complex data [RKS88]. Recently, there has been a resurgence of interest in set-valued attributes from two different perspectives. First, commercial O/R DBMS's (Object/Relational DataBase Management Systems) are beginning to support set-valued attributes, which is likely to lead to their use in “real” applications. Second, the rise of XML (eXtensible Markup Language) as an important data standard increases the need for set-valued attributes, since it appears that set-valued attributes are key for the natural representation of XML data in O/R DBMS's [JAI99].
Unfortunately, although sets have been fairly well studied from a data-modeling viewpoint, very little has been published about the efficient implementation of operations on set-valued attributes. Thus, there is a need in the art for improved operations over set-valued attributes, and in particular, there is a need in the art for a set containment join operation.
SUMMARY OF THE INVENTION
The present invention discloses a method, apparatus, and article of manufacture for performing a novel partition-based set containment join algorithm, known as Set Partitioning Algorithm (SPA). The SPA is performed by a relational database management system to aggressively partition set-valued attributes into a very large number of partitions, in order to minimize the impact of excessive replication and improve performance.
REFERENCES:
patent: 5247696 (1993-09-01), Booth
patent: 5325525 (1994-06-01), Shan et al.
patent: 5522077 (1996-05-01), Cuthbert et al.
patent: 5701467 (1997-12-01), Freeston
patent: 5857180 (1999-01-01), Hallmark et al.
patent: 5960194 (1999-09-01), Choy et al.
patent: 5970490 (1999-10-01), Morgenstern
patent: 6003036 (1999-12-01), Martin
patent: 6016397 (2000-01-01), Ogasawara et al.
patent: 6226629 (2001-05-01), Cossock
“Synthesizing Transformations for Locality Enhancement of Imperfectly-Nested Loop Nests”—Nawaaz Ahmed, Nikolay Mateev and Keshav Pingali—Proceedings of the 14th International Conference on Supercomputing, ACM May 2000, (pps: 141-152).*
“Partition Based Spatial—Merge Join”—Jignesh M. Patel and David J. DeWitt, Computer Science Department, 1996 ACM 0-89791-794-4/96/0006, pp. 259-270.*
“Separation Set Partitioning: Algorithm to Partition Nonstrict Programs into Sequential Threads”—Changmo Yang, Hyeongseok Joo and Weonhee Yoo—1060-3425/97—1997 IEEE, pp. 626-627.*
“Global Analysis for Partitioning Non-Stric Programs into Sequential Threads”—Kenneth R. Traub and David E. Culler 1992 ACM LISP & F.P. 6/92/CA—1992 ACM 0-89791-483-X/92/0006/0342, pp. 324-334.*
“Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates”—Sven Helmer and Guido Moerkotte—Proceedings of 23rdVLDB conference, Athens, Greece, 1997, pp. 386-395.*
S. Helmer & G. Moerk, “Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates,” Proceedings of the 23rdVLDB Conference, Athens, Greece, 1997, pp. 386-395.
Naughton Jeffrey F.
Patel Jignesh M.
Ramasamy Karthikeyan
Gates & Cooper LLP
Ly Anh
NCR Corporation
Vu Kim
LandOfFree
Set containment join operation in an object/relational... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Set containment join operation in an object/relational..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Set containment join operation in an object/relational... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3218995