Data processing: database and file management or data structures – Database design – Database and data structure management
Reexamination Certificate
2007-07-31
2010-11-23
Jalil, Neveen Abel (Department: 2165)
Data processing: database and file management or data structures
Database design
Database and data structure management
Reexamination Certificate
active
07840609
ABSTRACT:
A method and apparatus are provided for using sibling-counts in XML indices to optimize single-path queries. Using a b-tree XML index with a SQL query logarithmically reduces the number of disk accesses by passing over index entries where it is determined that a match will not be found. However, because certain index entries are passed over, it is impossible to ascertain if a path expression occurs more than once in the XML index, as certain queries sometimes require. This hurdle can be overcome by maintaining a sibling count with each node entry in the XML index. Because the sibling count is stored with the index entry, the index will reveal whether the matching node is single or has other siblings. In additional to re-writing the original query for optimization by use of an XML index, it will be re-written to check for a single-path condition in the index.
REFERENCES:
patent: 5193533 (1993-03-01), Body et al.
patent: 5210686 (1993-05-01), Jernigan
patent: 5369763 (1994-11-01), Biles
patent: 5404513 (1995-04-01), Powers et al.
patent: 5410691 (1995-04-01), Taylor
patent: 5454101 (1995-09-01), Mackay et al.
patent: 5467471 (1995-11-01), Bader
patent: 5514112 (1996-05-01), Chu et al.
patent: 5524240 (1996-06-01), Barbara et al.
patent: 5530849 (1996-06-01), Hanushevsky et al.
patent: 5544360 (1996-08-01), Lewak et al.
patent: 5546571 (1996-08-01), Shan et al.
patent: 5568640 (1996-10-01), Nishiyama et al.
patent: 5643633 (1997-07-01), Telford et al.
patent: 5680614 (1997-10-01), Bakuya et al.
patent: 5701467 (1997-12-01), Freeston
patent: 5795322 (1998-08-01), Boudewijn
patent: 5838965 (1998-11-01), Kavanagh et al.
patent: 5842212 (1998-11-01), Balluvio et al.
patent: 5870590 (1999-02-01), Kita et al.
patent: 5878415 (1999-03-01), Olds
patent: 5917492 (1999-06-01), Bereiter et al.
patent: 5921582 (1999-07-01), Gusack
patent: 5964407 (1999-10-01), Sandkleiva
patent: 5974407 (1999-10-01), Sacks
patent: 5987506 (1999-11-01), Carter et al.
patent: 6038563 (2000-03-01), Bapat et al.
patent: 6055544 (2000-04-01), DeRose et al.
patent: 6061684 (2000-05-01), Glasser et al.
patent: 6101500 (2000-08-01), Lau
patent: 6111578 (2000-08-01), Tesler
patent: 6112209 (2000-08-01), Gusack
patent: 6128610 (2000-10-01), Srinivasan et al.
patent: 6141655 (2000-10-01), Johnson et al.
patent: 6154741 (2000-11-01), Feldman
patent: 6182121 (2001-01-01), Wlaschin
patent: 6192273 (2001-02-01), Igel et al.
patent: 6192373 (2001-02-01), Haegele
patent: 6199195 (2001-03-01), Goodwin et al.
patent: 6208993 (2001-03-01), Shadmone
patent: 6236988 (2001-05-01), Aldred
patent: 6263332 (2001-07-01), Nasr et al.
patent: 6269380 (2001-07-01), Terry et al.
patent: 6279006 (2001-08-01), Shigemi et al.
patent: 6279007 (2001-08-01), Uppala
patent: 6298349 (2001-10-01), Toyoshima et al.
patent: 6330573 (2001-12-01), Salisbury et al.
patent: 6343287 (2002-01-01), Kumar et al.
patent: 6356920 (2002-03-01), Vandersluis
patent: 6366934 (2002-04-01), Cheng et al.
patent: 6370537 (2002-04-01), Gilbert et al.
patent: 6427123 (2002-07-01), Sedlar
patent: 6470344 (2002-10-01), Kothuri et al.
patent: 6487546 (2002-11-01), Witkowski
patent: 6496842 (2002-12-01), Lyness
patent: 6519597 (2003-02-01), Cheng et al.
patent: 6539398 (2003-03-01), Hannan et al.
patent: 6604100 (2003-08-01), Fernandez et al.
patent: 6609121 (2003-08-01), Ambrosini et al.
patent: 6636845 (2003-10-01), Chau et al.
patent: 6643633 (2003-11-01), Chau et al.
patent: 6684227 (2004-01-01), Duxbury
patent: 6697805 (2004-02-01), Choquier et al.
patent: 6708186 (2004-03-01), Claborn et al.
patent: 6725212 (2004-04-01), Couch et al.
patent: 6772350 (2004-08-01), Belani et al.
patent: 6785673 (2004-08-01), Fernandez et al.
patent: 6826727 (2004-11-01), Mohr et al.
patent: 6836857 (2004-12-01), Ten-Hove et al.
patent: 6920457 (2005-07-01), Pressmar
patent: 7043488 (2006-05-01), Bauer et al.
patent: 7047253 (2006-05-01), Murthy et al.
patent: 7089239 (2006-08-01), Baer et al.
patent: 7097653 (2006-08-01), Freudenthal et al.
patent: 7107282 (2006-09-01), Yalamanchi
patent: 7120645 (2006-10-01), Manikutty et al.
patent: 7139746 (2006-11-01), Shin et al.
patent: 7162485 (2007-01-01), Gottlob et al.
patent: 7171404 (2007-01-01), Lindblad et al.
patent: 7171407 (2007-01-01), Barton et al.
patent: 7216127 (2007-05-01), Auerbach
patent: 2001/0037345 (2001-11-01), Kiernan et al.
patent: 2001/0049675 (2001-12-01), Mandler et al.
patent: 2002/0078068 (2002-06-01), Krishnaprasad et al.
patent: 2002/0103829 (2002-08-01), Manning et al.
patent: 2002/0143512 (2002-10-01), Shamoto et al.
patent: 2002/0152267 (2002-10-01), Lennon
patent: 2002/0156811 (2002-10-01), Krupa
patent: 2002/0184188 (2002-12-01), Mandyam et al.
patent: 2002/0184401 (2002-12-01), Kadel, Jr. et al.
patent: 2002/0188613 (2002-12-01), Chakraborty et al.
patent: 2003/0009361 (2003-01-01), Hancock et al.
patent: 2003/0065659 (2003-04-01), Agarwal et al.
patent: 2003/0078906 (2003-04-01), Ten-Hove et al.
patent: 2003/0093672 (2003-05-01), Cichowlas
patent: 2003/0101194 (2003-05-01), Rys et al.
patent: 2003/0131051 (2003-07-01), Lection et al.
patent: 2003/0140308 (2003-07-01), Murthy et al.
patent: 2003/0177341 (2003-09-01), Devillers
patent: 2003/0182624 (2003-09-01), Large
patent: 2003/0212662 (2003-11-01), Shin et al.
patent: 2003/0212664 (2003-11-01), Breining et al.
patent: 2004/0010752 (2004-01-01), Chan et al.
patent: 2004/0044659 (2004-03-01), Judd et al.
patent: 2004/0064466 (2004-04-01), Manikutty et al.
patent: 2004/0068494 (2004-04-01), Tozawa et al.
patent: 2004/0088320 (2004-05-01), Perry
patent: 2004/0088415 (2004-05-01), Chandrasekar et al.
patent: 2004/0167864 (2004-08-01), Wang et al.
patent: 2004/0205551 (2004-10-01), Santos
patent: 2004/0230667 (2004-11-01), Wookey
patent: 2005/0038688 (2005-02-01), Collins et al.
patent: 2005/0050016 (2005-03-01), Stanoi et al.
patent: 2005/0091188 (2005-04-01), Pal et al.
patent: 2005/0097084 (2005-05-01), Balmin et al.
patent: 2005/0120031 (2005-06-01), Ishii
patent: 2005/0228792 (2005-10-01), Chandrasekaran et al.
patent: 2005/0228818 (2005-10-01), Murthy et al.
patent: 2005/0229158 (2005-10-01), Thusoo et al.
patent: 2005/0257201 (2005-11-01), Rose et al.
patent: 2006/0235840 (2006-10-01), Manikutty et al.
patent: WO 01/42881 (2001-06-01), None
patent: WO 01/59602 (2001-08-01), None
patent: WO 01/61566 (2001-08-01), None
patent: WO 03/027908 (2003-04-01), None
Lo et al., XAS: A System for Accessing Componentized, Virtual XML Documents, May 2001, Proceedings of ICSE'01, IEEE Press, p. 493-502, <Retrieved from IEEE Explore May 4, 2009>.
Meyer et al, “GenDBDan open source genome annotation system for prokaryote genomes”, Apr. 2003, Nucleic Acids Research, p. 2187-2195.
Shah et al, “Pegasys: software for executing and integrating analyses of biological sequences”, Apr. 2004, BMC Bioinformatics, p. 1-16, <Retrieved from BioMed Central, May 4, 2009>.
Mungall et al, “An integrated computational pipeline and database to support whole-genome sequence annotation”, Dec. 2002, GenomeBiology.com p.1-11, <Retrieved from GenomeBiology May 4, 2002>.
Chen et al., “From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery, 2003”, Proceedings of the 29thVLDB Conference, pp. 1-12.
Girardot et al., “Millau: an encoding format for efficient representation and exchange of XMLover the Web”, IBM Almaden Research Center, 24 pages.
Shankar Pal et al., “Indexing XML Data Stored in a Relational Database”, Proceedings of the 30thVLDB Conference, 2004, 12 pages.
MacKenzie et al., “Finding Files”, FindUtils, Version 4.1.2, Source Code, GNU.org, Nov. 1997, source files, code. C, 22 pages.
Cormen et al., “Introduction to Algorithms”, MIT Press, 2001, 2ndEdition, 4 pages.
European Patent Office, “Communication pursuant to Article 94 (3) EPC”, European patent application 05732473.3-1225, dated Feb. 4, 2008, 7 pages.
State Intellectual Property Office of P.R.C., “Notification of the First Office Action”
Agarwal Nipun
Baby Thomas
Chandrasekar Sivasankaran
Murthy Ravi
Abel Jalil Neveen
Buckingham Kellye D
Hickman Palermo & Truong & Becker LLP
Oracle International Corporation
LandOfFree
Using sibling-count in XML indexes to optimize single-path... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Using sibling-count in XML indexes to optimize single-path..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Using sibling-count in XML indexes to optimize single-path... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4177246