Operator for correlated predicates in a query

Details Operator for correlated predicates in a query Operator for correlated predicates in a query

1999-11-15

2003-05-06

Breene, John (Department: 2177)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000

Reexamination Certificate

active

06560595

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to databases and more particularly, to using a correlation operator &THgr; to correlate sub-queries.
BACKGROUND OF THE INVENTION
Database methodologies, developing for decades, now include relational, object-oriented, and heterogeneous types. Heterogeneous databases have arbitrarily structured records.
This application is commonly assigned with U.S. patent application Ser. No. 6,167,393 to Davis, III et al.
Ubiquitous personal computing, collaborative group computing, and highly integrated, distributed environments create new demands on databases. Databases store information, that is most useful when retrieved completely, reliably, and quickly.
Records (or combinations of records) in a database generally represent an object in the real world (a product, a customer, an employee, a business division, etc.). As such, a record typically consists of a collection of fields that represent attributes of the object. This collection of fields is not necessarily “complete,” but has been deemed sufficiently useful to describe the object and distinguish it from any other object represented in the database. Ultimately, the contents of these fields are the information that distinguish one object from another.
By way of example, traditionally, databases use schema to define record “types” or object classes. In such databases, a record type (or object class) is an abstraction or generalization about the collection of records in the database that represents the same “kind” of real world object. As such, a record “type” may be thought of as “meta-data,” or “data about data.” A record type typically defines certain relevant attributes and/or behaviors that are to be found in instances of that record type. For example, the record type “person” may specify that a “person” record contains attributes of height, weight, hair color, phone number, etc. The set of “person” records in the database is homogeneous in that each record contains exactly the same set of attributes (those that are defined in the “person” record type).
As an alternative to relational database structures, arbitrarily structured records can be used. In an arbitrarily structured record, repeating fields, missing fields, null-valued fields, and sub-record entities may exist. A database containing arbitrarily structured records presents numerous difficulties for a query engine designed to locate records within the database. An arbitrarily structured record might also include more than a single field having the same field identification or field name.
Internal self-description exists within arbitrarily structured records since no over-riding schema need exist, as compared with relational databases. Thus, data may not always be cleanly divided into homogenous tables, each having a single schema (record template), as required by the relational database model.
For example, a business organization may have some substantial structuring. Nevertheless, an address book might regard every company entity (e.g., company, division, department, unit, individual, etc.) as a contact, customer, client, or the like. Such a universal address book may need to accommodate all entities possessing an address and a phone number regardless of other attributes.
In searching a database, whether the database is relational, object-oriented, arbitrarily structured, or of some other type, data may need to be correlated. It may be necessary to identify a record in the database for which two properties exist, or two records that share a common property. For example, in searching a database of vehicles and their owners, a user may need to identify all owners who own a particular vehicle combination of make, model, color, year, etc. Or a user may need to identify all owners who own a particular combination of vehicles. A database can be manually correlated, but the process is cumbersome, requiring a high degree of skill from the user. Any user lacking the needed skill would be unable to complete the desired search.
SUMMARY OF THE INVENTION
A correlation operator &THgr; requires that the results of the sub-queries it has for an operand be correlated. The correlation operator &THgr; has an implied existential quantifier property (i.e., a “for some” property) and is satisfied if any record matches its sub-query. If no record is found that matches the correlation operator &THgr;'s sub-query, then the correlation operator &THgr; query fails. The implicit existential quantifier property of the correlation operator &THgr; can be converted into a universal quantifier property (i.e., a “for all” property) by transformation of the query.
The invention further includes an algebra for resolving the correlation operator &THgr; into flags attached to appropriate operators in the sub-query. After the correlation operator &THgr; is eliminated from the query, the query can be performed.
The correlation operator &THgr; can be inserted explicitly by the user if she knows what data she desires to be correlated. Alternatively, the correlation operator can be inserted by the schema automatically to improve the expected results of the query.


REFERENCES:
patent: 5367675 (1994-11-01), Cheng et al.
patent: 5548755 (1996-08-01), Leung et al.
patent: 5551031 (1996-08-01), Cheng et al.
patent: 5557791 (1996-09-01), Cheng et al.
patent: 5761657 (1998-06-01), Hoang
patent: 5822750 (1998-10-01), Jou et al.
patent: 5870739 (1999-02-01), Davis, III et al.
patent: 5873079 (1999-02-01), Davis, III et al.
patent: 5884304 (1999-03-01), Davis, III et al.
patent: 5905982 (1999-05-01), Carey et al.
patent: 6112198 (2000-08-01), Lohman et al.
patent: 6167393 (2000-12-01), Davis, III et al.
patent: 6341281 (2002-01-01), MacNicol et al.
Gray et al. “Data Cube: A Relational Aggregation Operator Genelizing Group-By, Cross-Tab, and Sub-Totals” Microsoft Technical Report, Feb. 1995, Revised Nov. 1995.*
Rao et al., “Reusing Invariants: A New Strategy for Correlated Queries” ACM SIGMOD Record, Proceedings of ACM SIGMOD international conference on Management of data Jun. 1998, pp. 37-48.*
Lin et al., “Processing OODB Queries by O-Algebra” Proceedings of the fifth international conference on Information and knowledge management Nov. 1996, pp. 134-142.*
Kifer et al., Querying Object-Oriented Database, ACM SIGMOD Jun. 1992, pp. 393-402.*
Jin, Beihong, “Translating object query language”, IEEE, Technology of Object-Oriented Languages and Systems, TOOLS 31. Proceedings, Sep. 22-25, 1999, pp.:380-385.

Affiliated with

Also associated with

Rating

Operator for correlated predicates in a query does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Operator for correlated predicates in a query, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Operator for correlated predicates in a query will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3089879