Indexing, rewriting and efficient querying of relations...

Details Indexing, rewriting and efficient querying of relations... Indexing, rewriting and efficient querying of relations...

2006-03-21

2006-03-21

Corrielus, Jean M. (Department: 2162)

Data processing: database and file management or data structures

Database design

Data structure types

C100S102000, C100S104000

Reexamination Certificate

active

07016910

ABSTRACT:
The invention discloses methods and apparatus that facilitate efficient querying of tables referencing semistructured data such as digraphs and other domains with complex grouping structure. The invention methods enable meaningful indexing of the tables as well as rewriting of queries with respect to the structures. Dynamic schema extraction using proper coloring algorithms is disclosed that structures the semistructured data in such a way that complex set operations and grouping are replaced with traditional relational joins. This enables a relational database system to harness its entire query optimizing capability when querying tables referencing semistructured data.

REFERENCES:
patent: 5257365 (1993-10-01), Powers et al.
patent: 5608899 (1997-03-01), Li et al.
patent: 5664172 (1997-09-01), Antoshenkov
patent: 5799300 (1998-08-01), Agrawal et al.
patent: 5812840 (1998-09-01), Shwartz
patent: 5822751 (1998-10-01), Gray et al.
patent: 5832475 (1998-11-01), Agrawal et al.
patent: 5890151 (1999-03-01), Agrawal et al.
patent: 5893104 (1999-04-01), Srinivasan et al.
patent: 5905985 (1999-05-01), Malloy et al.
patent: 5918232 (1999-06-01), Pouschine et al.
patent: 5926818 (1999-07-01), Malloy
patent: 5926820 (1999-07-01), Agrawal et al.
patent: 5943668 (1999-08-01), Malloy et al.
patent: 5978796 (1999-11-01), Malloy et al.
patent: 6016497 (2000-01-01), Suver
patent: 6061676 (2000-05-01), Srivastava et al.
patent: 6094651 (2000-07-01), Agrawal et al.
patent: 6115714 (2000-09-01), Gallagher et al.
patent: 6160549 (2000-12-01), Touma et al.
patent: 6240407 (2001-05-01), Chang et al.
patent: 6247008 (2001-06-01), Cambot et al.
patent: 6289352 (2001-09-01), Proctor
patent: 6298342 (2001-10-01), Graefe et al.
patent: 6334182 (2001-12-01), Merchant et al.
patent: 6366904 (2002-04-01), BenHadda et al.
patent: 6397204 (2002-05-01), Liu et al.
patent: 6421656 (2002-07-01), Cheng et al.
patent: 6421665 (2002-07-01), Brye et al.
patent: 6477525 (2002-11-01), Bello et al.
patent: 6604099 (2003-08-01), Chung et al.
patent: 6654734 (2003-11-01), Mani et al.
patent: 2002/0120598 (2002-08-01), Shadmon et al.
patent: 2005/0050030 (2005-03-01), Gudbjartsson et al.
patent: 0 965 928 (1999-12-01), None
Nestorov et al., “Extracting Schema From Semistructured Data”, SIGMOD Conference 1998, pp. 295-306.
Harinarayan, V., et al., “Implementing Data Cubes Efficiently,” ACM, Jun. 1996 (pp. 205-216).
Gray, J., et al., “Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals,”Data Mining and Knowledge Discovery, Kluwer Academic Publishers, The Netherlands, 1997 (p. 29-53).
Saake, G., and Heuer, A., “Datenbanken: Implementierungstechniken,”MITP-Verlag, App. Publ., pp. 306-309 (1999).
Lenz, Hans-J. and Shoshani, Arie, “Summarizability in OLAP and Statistical Data Bases,”Proc. of the International Conference on Scientific and Statistical Database Management, 1997 (p. 132-143).
Mumick, I.S., et al., “Maintenance of Data Cubes and Summary Tables in a Warehouse.”ACM Proceedings of Sigmod, International Conference on Management of Data, 26(2), 1997 (p. 100-111).
Codd, E.F. et al., “Providing OLAP to User-Analysts: An IT Mandate,” E. F. Codd Associates (1993).
Codd, E.F., “A Relational Model of Data for Large Shared Data Banks,”Communications of the ACM, 13(6) : 377-387 (1970).
Agrawal, R. et al., “Modeling Multidimensional Databases,” Research Report, IBM Almaden Research Center.
Ramakrishnan, R. et al.,Database Management Systems, McGraw-Hill (1998).
Singh, H.S.,Data Warehousing: Concepts, Technologies, Implementations, and Management, Prentice Hall PTR (1998).
Chaudhuri, S. and D. Umeshwar, “An Overview of Data Warehousing and OLAP Technology,”SIGMOD Record, Association for Computing Machinery, 26(1):65-74, Mar. 1997.
International Search Report—PCT/US00/33983, Dec. 23, 2003, 2 pp.

Affiliated with

Also associated with

Rating

Indexing, rewriting and efficient querying of 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 Indexing, rewriting and efficient querying of relations..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Indexing, rewriting and efficient querying of relations... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3613268