text:
Data processing system and method for retrieving and entity specified in a search path record from a relational databaseDownload PDF
- Publication number
- Authority
- Grant status
- Grant
- Patent type
- Prior art keywords
- table
- entity
- means
- relation
- data
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/30—Information retrieval; Database structures therefor ; File system structures therefor
- G06F17/30286—Information retrieval; Database structures therefor ; File system structures therefor in structured data stores
- G06F17/30587—Details of specialised database models
- G06F17/30595—Relational databases
- G06F17/30604—Entity relationship models
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S707/00—Data processing: database and file management or data structures
- Y10S707/953—Organization of data
- Y10S707/954—Relational
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S707/00—Data processing: database and file management or data structures
- Y10S707/99931—Database or file accessing
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S707/00—Data processing: database and file management or data structures
- Y10S707/99931—Database or file accessing
- Y10S707/99932—Access augmentation or optimizing
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S707/00—Data processing: database and file management or data structures
- Y10S707/99931—Database or file accessing
- Y10S707/99933—Query processing, i.e. searching
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S707/00—Data processing: database and file management or data structures
- Y10S707/99931—Database or file accessing
- Y10S707/99933—Query processing, i.e. searching
- Y10S707/99934—Query formulation, input preparation, or translation
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S707/00—Data processing: database and file management or data structures
- Y10S707/99951—File or database maintenance
- Y10S707/99952—Coherency, e.g. same view to multiple users
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10T428/00—Stock material or miscellaneous articles
- Y10T428/10—Liquid crystal optical display having layer of specified composition
- Y10T428/1005—Alignment layer of specified composition
This application is a division of application Ser. No. 08/083,361 08/083,861, filed Jun. 28, 1993, now abandoned U.S. Pat. No. 5,604,899, which issued on Feb. 18, 1997, which is a continuation of Ser. No. 07/526,424, filed May 21, 1990, now abandoned.
1. Cross Reference to Microfiche Appendix
This application includes a plurality of computer program listings (modules) in the form of a Microfiche Appendix which is being filed concurrently herewith as 1162 frames (not counting target and title frames) distributed over 20 sheets of microfiche in accordance with 37 C.F.R. §1.96. The disclosed computer program listings are incorporated into this specification by reference but it should be noted that the source code and/or the resultant object code of the disclosed program modules are subject to copyright protection, The copyright owner has no objection to the facsimile reproduction by anyone of the patent document (or the patent disclosure as it appears in the files or records of the U.S. Patent and Trademark Office) for the sole purpose of studying the disclosure but otherwise reserves all other rights to the disclosed computer program modules including the right to reproduce said computer program modules in machine-executable form.
2. Field of Invention
The present invention relates generally to computer database management systems and more specifically to apparatus and methods for modifying and searching through large scale databases at high speed. 3. Description of Related Art
Modern computer systems are capable of storing voluminous amounts of information in bulk storage means such as magnetic disk banks. The volume of stored information can be many times that of the textual information stored in a conventional encyclopedia or in the telephone directory of a large city. Moreover, modern computer systems can sift through the contents of their built storage means at extremely high speed, accessing as many as one million bytes of information or more per second (a byte is a string of eight bits, equivalent to approximately one character of text in layman's terms). Despite this capability, it may take an undesirably long time (i.e., hours or days) to retrieve desired pieces of information. In commercial settings such as financial data store facilities, there will be literally billions of pieces of information that could be sifted through before the right one or more pieces of information are found. Thus, even at speeds of one million examinations per second, it can take thousands of seconds (many hours) to retrieve a desired piece of information. Efficient organization of the stored information is needed in order to minimize retrieval time.
The methods by which pieces of information are organized within a computer, searched through or reorganized, often parallel techniques used by older types of manual information processing systems. A well known example of a manual system is the index card catalog found in public libraries. Such as card catalog consists of a large number of uniformly dimensioned paper cards which are serially stacked in one or more trays. The cards are physically positioned such that each card is directly adjacent to no more than two others (for each typical examination there is a preceding card, the card under examination and a following card in the stack). On the front surface of each index card a librarian enters, in left to right sequence; the last name of an author, the first name of the author, the title of a single book which the author wrote and a shelf number indicating the physical location within the library where the one book may be found. Each of these four entries may be referred to as a "column" entry. Sufficient surface area must be available on each card to contain the largest of conceivable entries.
After the entries are made, the index cards are stacked one after the next in alphabetical order, according to the author's last name and then according to the author's first name and then by title. This defines a "key-sequenced" type of database whose primary sort key is the author's name. The examination position of each card is defined relative to the contents of preceding and following cards in the stack. That is, when cards are examined, each intermediate card is examined immediately after its alphabetically preceding card and immediately before its alphabetically succeeding card. When a new book is acquired, the key-sequenced database is easily "updated" by inserting a new card between two previously created cards. Similarly, if a book is removed from the collection, its card is simply pulled from the card stack to reflect the change.
If a library user has an inquiry respecting the location of a particular book or the titles of several books written by a named author, the librarian may quickly search through the alphabetically ordered set of index cards and retrieve the requested information. However, if a library user has an inquiry which is not keyed to an author's name, the search and retrieval process can require substantially more time; the worst case scenario being that for each inquiry the librarian has to physically sift through and examine each card in the entire catalog. As an example of such a scenario, suppose that an inquiring reader asks for all books in the library where the author's first name is John and the title of the book contains the word "neighbor" or a synonym thereof. Although it is conceptually possible to answer this inquiry using the information within the catalog, the time for such a search may be impractically long, and hence, while the information is theoretically available, it is not realistically accessible.
To handle the more common types of inquires, libraries often keep redundant sets of index cards. One set of cared is sorted according to author names and another set is sorted according to the subject matter of each book. This form of redundant storage is disadvantageous because the size of the card catalog is doubled and hence, the cost of information storage is doubled. Also, because two index cards must be generated for each new book added to the collection the cost of updating the catalog is also doubled.
The size of a library collection tends to grow over time as more and more books are acquired. During the same time, more and more index cards are added to the catalog. The resulting stack of cards, which may be viewed as a kind of "database", therefore grows both in size and in worth. The "worth" of the card-based system may be defined in part as the accumulated cost of all work that is expended in creating each new index card and in inserting the card into an appropriate spot in the stack.
As time goes by, not only does the worth and size of the database grow, but new technologies, new rules, new services, etc., begin to emerge and the information requirements placed on the system change. Some of these changes may call for a radical reorganization of the card catalog system. In such cases, a great deal of work previously expended to create the catalog system may have to be discarded and replaced with new work.
For the sake of example, let it be supposed that the library acquires a new microfilm machine which stores copies of a large number of autobiographies. The autobiographies discuss the life and literary works of many authors whose books are kept in the library. Let it further be supposed that the original, first card catalog system is now required to cross reference each book to the microfilm location (or plural locations) of its author's (or plural authors') autobiographies. In such a case, the card catalog system needs to be modified by adding at least one additional column of information to each index card to indicate the microfilm storage locations of the relevant one or more autobiographies.
We will assume here that there is not enough surface area available on the current index cards for adding the new information. Larger cards are therefore purchased, the information from the old cards is copied to the new cards, and finally, the new microfilm cross referencing information is added to the larger cards. This type of activity will be referred to here as "restructuring" the database.
Now let us suppose, that as more time goes by, an additional but previously unanticipated, cross indexing category is required because of the introduction of a newer technology or a new government regulation. It might be that the just revised and enlarged second card system does not have the capacity to handle the demands of the newer technology or regulation. In such a situation, a third card system has to be constructed from scratch. The value of work put into the creation of the just-revised second system is lost. As more time passes and further changes emerge in technology, regulations, etc., it is possible that more major organizational changes will have to be made to the catalog system. Time after time, a system will be built up only to be later scrapped because it fails to anticipate a new type of information storage and retrieval operation. This is quite wasteful.
Although computerized database systems are in many ways different from manual systems, the computerized information storage and retrieval systems of the prior art are analogous to manual systems in that the computerized databases require similar restructuring every time a new category of information relationships or a new type of inquiry is created.
At a fundamental level, separate pieces of information are stored within a computerized database system as a large number of relatively short strings of binary bits where each string has finite length. The bit stings are distributed spacially within a tangible medium of data storage such as an array of magnetic disks, optical devices or other information representing means capable of providing mass storage. Each bit is represented by a magnetic flux reversal, an optical perturbation and/or more other variance in the physical attributes of a data storage medium. A transducer or amplifier means converts these variances into signals (e.g., electrical, magnetic, or optical) which can be processed on a digital data processing machine. Each string of bits is often uniquely identified by its physical location or by a logical storage address. Some bit strings may function as address pointers, rather than as the final pieces of "real" information which a database user wishes to obtain. The address pointers are used to create so-called "threaded list" organizations of data wherein logical links between a first informational "object" (first piece of real data) and a second informational "object" (second piece of real data) are established by a chain of direct or indirect address pointers. The user-desired objects of real information themselves can be represented by a collection of one or more physically or logically connected strings.
Typically, "tables" of information are created within the mass storage means of the computerized system. A horizontal "row" of related objects, which is analogous to a single card in a card catalog system, may be defined by placing the corresponding bit strings of the objects in physical or address proximity with each other. Logical interconnections may be defined between different rows by using ancillary pointers (which are not considered here as the "real" data sought by a database user). A serial sequence of "rows" (analogous to a stack of cards) is then defined by linking one row to another according to a predefined sorting algorithm using threaded list techniques.
A vast number of different linking "threads" may be defined in this way through a database table having millions or billions of binary information bits. Unlike manual systems, the same collection of rows (which replaces the manual stack of cards) can be simultaneously ordered in many different ways by utilizing a multiplicity of threaded paths so that redundant data storage is not necessary. Searches and updates may be performed by following a prespecified thread from one row to the next until a sought piece of information (or its address) is found within a table. A threaded-list type of table can be "updated" in a manner similar to manual card system by breaking open a logical thread within the list, at a desired point, and inserting a new row (card) or removing an obsolete row at the opened spot.
Tables are often constructed according to a "key-sequenced" approach. One column of a threaded-list table is designated as the sort-key column and the entries in that column are designated as "sort keys". Address pointers are used to link one row of the table to another row according to a predefined sequencing algorithm which orders the entries (sort-keys) of the sort column as desired (i.e., alphabetically, numerically or otherwise). Once a table is so sorted according to the entries of its sort column, it becomes a simple task to search down the sort column looking for an alphabetically, numerically or otherwise ordered piece of data. Other pieces of data which are located within the row of each sort key can then be examined in the same sequence that each sort key is examined. Any column can serve as the sort column and its entries as the sort keys. Thus a table having a large plurality of columns can be sorted according to a large number of sorting algorithms.
The key-sequencing method gives tremendous flexibility to a computerized database but not without a price. Each access to the memory location of a list-threading address pointer or to the memory location of a sort-key or to the memory area of "real" data which is located adjacent to a sort-key takes time. As more and more accesses are required to fetch pointers and keys leading to the memory location of a piece of sought-after information ("real data"), the response time to an inquiry increases and system performance suffers.
There is certain class of computerized databases which are referred to as "relational databases". Such database systems normally use threaded list techniques to define a plurality of key-sequenced "tables". Each table contains at least two columns. One column serves as the sort column while a second or further columns of the table store either the real data that is being sought or additional sort-key data which will ultimately lead to a sought-after piece of real data. The rows of the table are examined in an ordered fashion according to the contents of the sort column. Target data is located by first threading down the sort column and thus moving through the chain of rows within a table according to a prespecified sort algorithm until a specific sort-key is found. Then the corresponding row is examined horizontally and the target data (real data or the next key) is extracted from that row.
An example of "real" data would be the full-legal names of unique persons such as in the character strings, "Mr. Harry W. Jones", "Mrs. Barbara R. Smith", etc. The sort-key can be a number which is stored adjacent to the full name and which sequences the names (real data) according to any of a wide variety of ordering patterns including by age, by height, by residential address, alphabetically, etc. Because the real data (e.g., full name of a person) is stored in a separate column, it is independent from the sort key data. A large varicty of different relations can therefore be established between a first piece of real data (e.g., a first person's name) and a second piece of real data (e.g., a second person's name) simply by changing the sort keys that are stored in the separate sort column (e.g., who is older than whom, who is taller, etc.). Plural orderings of the real data can be obtained at one time by providing many columns in one table, by storing alternate keys in the columns and by choosing one or more of these columns as the primary sort key column.
Relational database systems often include tables that do not store real data in a column adjacent to their sort-key column, but rather store a secondary key number which directs a searcher to a row in another key-sequenced table where a matching key number is held together with either a piece of sought-after real data or yet another forward referencing key number (e.g., an entry which in effect says "find the row which holds key number x of yet another table for further details"). With this indirect key-sequenced approach, a large number of tables can be simultaneously updated by changing one entry in a "base" table.
Relational database tables are normally organized to create implied set and subset "relations" between their respective items of pre-stored information. The elements of the lowest level subsets are stored in base tables and higher level sets are built by defining, in other tables, combinations of keys which point to the base tables. The implied relations between elements cannot be discerned by simply inspecting the raw data of each table. Instead, relations are flushed out only with the aid of an access control program which determines in its randomly-distributed object code, which table to examine first and what column to look at before beginning to search down the table's column for a key number and, when that key number is found, what other column to look at for the real data or a next key number. Relations between various "entities" of a relational database are implied by the sequence in which the computer accesses them.
By way of a concrete example, consider a first relational table (Names-Table) which lists the names of a large number of people in telephone directory style. Each name (each separate item of real data) is paired to a unique key number and the rows of this Names-Table are stored sequentially according to the key number. A second relational table may be provided in the database (Cars-Table) which lists automobile (vehicle) identification numbers (VIN) each paired in its row with a second key number. If the second key number is matched by a corresponding key number in the first table, then a relationship might be implied between the entries of the two separate tables (Names-Table and Cars-Table). The "implied" relationship might be one of an infinite set of possibilities. The relationship could be, for example, that the car listed in the second table is "owned" by the person whose name is found next to a matching key in the first table. On the other hand, it might be implied that the matched person in the first table "drives" the car, or "cleans" the car or has some other relation to the car. It is left to the access control program to define what the relationship is between entities in the first table and entities in the second table.
It can be seen that relational database systems offer users a great deal of flexibility since an infinite number of relations may be defined (implied). Economy in maintaining (updating) the database is also provided since a change to a base table propagates through all other tables which reference the base table. The access control program of the database system can include information-updating modules which, for example, change the key number in the second table (Cars-Table) whenever ownership of a car changes. If the name of the new owner is already in the first table (Names-Table), it does not have to be typed a second time into a new storage area and thus, extra work and storage redundancy are avoided. The vehicle identification number (VIN) remains unchanged. Minimal work is thus expended on updating the database.
Despite these advantages, relational database systems suffer from expandability and restructuring problems similar to those of the above-described manual system. Sometimes the rows within a particular table have to be altered to add additional columns. This is not easily done. Suppose for example, that a new government regulation came into being, mandating that vehicles are to always be identified not only by a vehicle identification number (VIN) but also by the name and location of the factory where the vehicle was assembled. If spare columns are not available in the Cars-Table, the entire database may have to be restructured to create extra room in the storage means (i.e. the disk bank) for adding the newly required columns. New key numbers will have to be entered into the new columns of each row (e.g., a new "factory of assembly" key number) and sorted in order to comply with the newly mandated regulation. New search and inquiry routines will have to be written for handling the newly structured tables.
In the past, much of this restructuring work was done by reprogramming the computer at the object code or source code level. This process relied heavily on an expert programming staff. It was time consuming, costly and prone to programming errors. Worst of all, it had to be redone time and again as new informational requirements emerged just after a last restructuring project was completed. There is a need in the industry for a database management system which provides quick responses to inquires and which can also be continuously updated or restructured without reprogramming at the source or object code level.
It is an objective of the present invention to provide a database system which is capable of storing voluminous amounts of information, sifting through the information at high speed, and is at the same time easily expandable or restructurable to take on new forms of entities and relationships.
In accordance with a first aspect of the invention, an entity definition table (ENT.DEF) is defined within the memory means of a computer system to store the name of an allowed entity type (class) and the name of a single other table (Entity-instances Table or "EiT" for short) where instances of the allowed entity type may be stored. A separate relationships definition table (REL.DEF) is defined in the memory means to list in each row of the table: (a) the name of an allowed relations type, (b) the name of a single Relation-instances Table (RiT) where instances of the allowed relationship type may be stored, (c) the name of a primary (head) entity type to which the relation type may apply and (d) the names of one or more secondary (tail) entity types to which the named relationship may apply. Each row of the Relation-instances Table (RiT) is provided with at least one primary pointer which points to the storage location of a first instance of the primary entity type and at least one secondary pointer which points to the storage location of a corresponding first instance of the secondary entity type. Each row of the Relation-instances Table (RiT) further includes a pointer to a relationship-defining row in the REL.DEF table. The pointer can be the name of an applicable relation type as recorded in the REL.DEF table. Relationships between instances of a primary entity and a secondary entity are thus expressly defined by entries in the Relation-instances Table (RiT). Adding new rows to this Relation-instances Table (RiT) allows for the addition of new relations. Adding new rows to the REL.DEF table allows for the creation of new classes (types) of relationships. Since relation-defining table can be updated using a fixed set of update modules, reprogramming at the source or assembly level is not needed for restructuring the schema of the database.
The invention will be described with reference to the following figures in which:
The following includes a detailed description of the best mode or modes presently contemplated by the inventor for carrying out the invention. It is to be understood that these modes are merely exemplary of the invention. The detailed description is not intended to be taken in a limiting sense.
Referring to
To access a particular string of data 130d stored within the bulk storage means 130, the CPU 110 must provide a corresponding address signal 131s (
Referring still to
It should be understood that neither the object code 120d of the first memory means 120 nor the data code 130d of the mass storage means 130 is in human-readable form. A translation machine is needed to convert the binary bit strings of either memory means (120 or 130) into a form which might be understandable to an experienced computer programmer or to a lay computer user.
The object code 120d of the access control program is produced by first generating (e.g., manually writing and encoding) a source code listing 112 whose lines of information 112d are usually understandable only to a highly trained computer programmer. The source code listing 112 which is written in an assembly level or higher level language (e.g., C, COBOL, FORTRAN, PASCAL, etc.) is transformed into machine-readable form, and passed through a first translation machine which may be referred to as a compiler (or assembler) means 114. The compiler means 114 produces the machine-readable object code 120d according to instructions provided by a machine readable version of the source code listing 112. After it is stored in the first memory means 120, the object code 120d is expressed as machine detectable alternations (ones and zeros) in a physical attribute (e.g., voltage) of the medium which makes up the first memory means 120. In this form, the object code 120d is more readily convertible into data signals 122s which are understandable to the CPU 110 than into information which is understandable to a lay (non-programmer) person. It is highly improbable that a lay person will ever wish to access or understand or modify the object code 120d stored within the first memory means 120.
The information strings 130d within the bulk storage means 130 are similarly expressed as alternations in the physical property of the storage medium making up the second memory means 130. Some of the data strings 130d represent "real" data which a lay-user may wish to access while others of the strings 130d represent "ancillary" data such as sequencing keys, threading pointers or control codes which a lay-user is not interested in. The object code 120d of the control program defines which is which.
When "real" data is to be extracted from the data strings 130d within the bulk storage means 130, read and understood by a lay person, a translation process similar to compilation (or more correctly de-complication) needs to take place. Just like the compiler means 114 functions as a man-to-machine translator, the combination of the first memory means 120 and the CPU 110 defines a second man-to-machine search-and-translate machine 115 which is used to search through parts of the bulk stored data 130d, extract relevant pieces of "real" data and convert the extracted data from machine-readable form into human-readable form. The human-readable output of the second translation machine 115 may be produced in the form of a query output listing 150 (e.g., on paper or on a video screen) as indicated in FIG. 1A.
If a lay user (defined here as someone other than a person who is an expert programmer familiar with details of the source listing 112) wishes to obtain useful ("real") information from the bulk storage means 130, the lay user will normally supply a query input 140, in a form dictated by a so-called "structured query language" (SQL) to the CPU 110. (In the illustrated example the user inputs the request string "Please find all books having attribute xxx," where xxx could be the relations "author's last name=Jones".) The combination of the CPU 110 and first memory means 120 (which combination forms the second search-and-translate machine 115) process this query input 140 and in response, produces a series of address signals 131s which are sent to the bulk storage means 130 and processes a series of data retrievals 132s which eventually lead to the production of a corresponding query output listing 150. (In the example, it would be a listing of all books whose author's name is "Jones".) The access control program 120d is charged with the task of enabling various types of queries 140 and making sure that the queries do not violate basic rules of logic.
When the information 130d within the bulk storage means 130 needs to be updated, by for example adding new books, a similar exchange occurs between the translating machine 115 and a lay user. The lay user supplies an update input 160, again as dictated by a pre-specified structured query language (SQL), and in response, the translating machine 115 rearranges the data 130d within the bulk storage means 130 to achieve the requested update.
Referring to
The name threading pointer 232 is located directly adjacent to the author's name subsection 231 within the address space of Record No. 1, as indicated by address proximity link P11 and thus, there is an "implied" logical connection between the data contents of boxes 231 and 232. The book's title subsection 233 is located directly adjacent to the name threading pointer 232 as indicated by address proximity link P12. The combined, proximity linkage, P11-P12, "implies" a relationship between the contents of boxes 231 and 233, namely that they apply to various attributes of a common book. This format repeats for data subportions 234-236. Only boxes 231, 233 and 235 contain "real" data which is useful to a lay person. The other boxes 232, 234 and 236 of Record No. 1 contain "ancillary" data which is useful to the search machine 115 but does not provide the kind of "real" information sought by an inquiring lay person.
The implied relations between the "real" data boxes, 231, 233 and 235 of Record No. 1, arise only after "meaning" is assigned to all the boxes 231-236. Such "meaning" comes from the operation of the search-and-translation machine 115 (FIG. 1). To understand this concept, assume that an automated "searching" machine (computer) 115/200 of embodiment 200 is examining the data string 230 held within the single Record No. 1. Assume further that this searching machine 115/200 includes means for assigning appropriate "meanings" to each of the data subportions contained in each of subsections 231-236 to thereby designate some as containing "real" data and others as containing "ancillary" (e.g., pointer) data. In that case the search machine 115/200 can scan horizontally across the record, parse the data string 230 into subsections of appropriate size and extract the name of the book's author, the book's title and the location of the book within the library, as desired. On the other hand, if the searching machine 115/200 does not possess information which tells it that box 232 is a threading pointer, box 233 is a title, etc., then all boxes will look alike to the search machine, there will be no "meaning" assigned and the search machine 115/200 will not be able to extract a desired piece of data. Thus, while not shown in
The title threading pointers (234, 244, 254) of each record may be used to form a different key-sequenced path in which books are examined according to subject matter or alphabetically according to the book's title or according to some other ordering algorithm. The location threading pointers (236, 246, 256) can be similarly used to create a key-sequenced list which will identify what book is physically located next to what other book on the library's shelves.
For the sake of illustrative simplicity, only one threading pointer (i.e., 232) is shown attached to each real data item (i.e. 231) of each record, but it should be apparent that the author's name 231 may have many threading pointers, one for threading alphabetically according to last name, and others for threading according to additional relations such as geographic location, age, number of published books and so forth. It is up to the computer programmer and the access control program 120d to assign "meaning" to each box and thus determine whether that box will function as a storage area for real data or for ancillary data such as pointer data.
The records of
Referring to a second embodiment 260 shown in
The relative-table organization is somewhat similar to the way that index cards are physically ordered in a manual library system according to author's last name, except that the library catalog tray should now be visualized as having sequentially arranged grooves define on their bottom-inner surfaces. Each groove is numbered according to its absolute position and only one card can be slotted into each groove. With this system, each card can be immediately located by its groove number rather than by thumbing through the information of all previous cards. If a groove number is known, substantial time can be saved in locating the corresponding card and obtaining the information written on its face. If the groove number is not known, the same relative-table organization can be searched by sequentially thumbing through the trays and examining the cards according to a key-sequenced approach in order to find a desired card even through the cards are stored in grooves. The relative-table organizing method is not mutually exclusion of a key-sequenced examination method. There is a difference between a purely key-sequenced table and a relative table, however. A relative-table organized system is not as easily updated as is a purely key-sequenced system. In the relative table system, a new card cannot be inserted between two cards which already fill adjacent slots. This inflexibility has led many in the database management field away from the relative-table method and towards purely key-sequenced systems since the latter can accept any number of new cards for insertion between old cards.
It should be noted that while the relative table organization 130b of
Rows are illustrated to extend horizontally (in the "x" direction) in
A first of the key-sequenced tables, 310 (also labeled "Table of Names"), is shown to have two columns. One (right side) column 312 holds "real" data representing the names of various persons while a preceeding (left side) column 311 holds unique key-numbers, 1, 2, 3, . . . , N, N+1, N+2, . . . , each associated with a unique name of a person. The association of a person's name to a key-number is "implied" by the fact that the key number 1, 2, 3, . . . , N, . . . , is located in the same row of table 310 as is the corresponding "Person's Name". Each key-number of left column 311 is referred to as a "Name Identification Number" (abbreviated here as N-IDN). Table 310 is shown to have been pre-sorted according to the N-IDN's of column 311. The sorting method is indicated in
To find the name of a person within table 310 whose associated identification number is known to be N, one normally starts at row number 1 of the left column 311, where the N-IDN of the first person's name is stored and treads downwardly (in the y direction) through the threaded-list pointers (not shown) associated with this sort column 311, testing each corresponding entry of column 311 for a match until the position holding the number N is found. Then one moves horizontally (in the x direction) across that row to the right column 312 to extract the name associated with the Nth name identification number (N-IDN).
When an automated search machine 115 performs this thread and test process, it must retrieve data from the memory area 130c at least N times before the target data (Person's-Name) is retrieved. The time for retrieving the target data is thus at least N times the access delay period (e.g., the t2-t1 period of
The N-IDN field of each row is generally made much shorter in bit length than its associated Person's-Name field. The N-IDN can be viewed therefore as an abbreviation of a person's full name. The first table 310 can be viewed as a conversion list or look-up table which allows one to easily convert a given abbreviation (N-IDN) into a full name.
A second, separate, table 320 (also labeled as "Table of Locations") is shown to contain two similar columns. Right column 322 stores "Home Addresses" in full while left column 321 holds unique, Home-Identification-Numbers (abbreviated H-IDN) which are generally shorter in bit length than the associated "Home-Address" fields. The H-IDN'S thus can serve as abbreviations for the full address fields. Table 320 is ordered numerically according to the H-IDN's as indicated by the legend "KSO" over column 321. The table 320 can therefore easily serve as part of an H-IDN abbreviation to full address converting means.
Since many people often live at a single home address, it is plausible that a single home address will be shared by persons of different names. Relational database theory recognizes this and teaches to separate information (e.g., home address) than might be shared by many entities away from any unique one of those entities (e.g., persons's name). Table 310 is accordingly separated from table 320. Concurrently, it should be possible to relate a person's full name to a full home address without having to repeatedly duplicate the full name string or full address sting within the bulk storage means 130. The data organization 300 shown in
Third table 330 comprises three vertical columns, 331, 332 and 333. Left column 331 holds Person Identification Numbers (P-IDN's), 1, 2, 3, . . . , P. The rows of third table 330 are sorted using the P-IDN's as the sort key. For each row of the third table 330, the second column 332 contains a Name-IDN and the third column 333 contains a Home-IDN. Each Name-IDN of third table 330 (for example, at row 4 of table 330 whose column 332 contains the value "N") should have in the left column 311 of the Names table 310 a matching key number (e.g., the number N which is pointed to by arrow L41). Thus an N-IDN stored in the third table 330 can be used to indicate the row within the first table 310 where a person's full name may be found. Each Home-IDN of the third table 330 should similarly have a matching key number (e.g., the number 2 which is pointed to by arrow L43) within left column 321 of the second "Locations" table 320 at whose row a corresponding full home address may be found.
Each row (e.g., row 4) within the third table 330 implicitly creates a set of logical links or "relations", L41-P42-L43 which join a person's name to a particular home address. These links, L41, P42 and L43 are represented in
A number of advantages come from organizing the tables of data storing area 300 separately according to relational database theory. Storage space is conserved in cases where plural entities of a first type (person) are related to a common entity of a second type (home address). The same Home-IDN can appear many times down column 333 without consuming large amounts of memory space while the actual full address is stored only once in second table 320. When a person moves to a new home address, the corresponding Home-IDN in column 333 can be easily altered to point to a new position within the second table 320 which contains the new home address (e.g., H+1) thereby implying the new person-to-address relation. If a person changes their name (i.e., by way of marriage) the home address can remain the same. Only the first table 310 needs to be modified and updating work is thus minimized. Also, the basic listings "Names" 310 and "Addresses" 320 can be used to imply a wide variety of "relations" other than a relation between a person's name and his/her home address using the same abbreviated set of identification numbers (IDN's).
By way of example, assume that the first three tables, 310, 320 and 330, are used by a business institution (company) to keep track of the names of their employees and the corresponding home addresses of these employees. Let it be supposed that many employees need to commute to work by a privately-owned car. Some employees drive their own car, some drive a car owned by another employee and some are merely passengers. Let it be further assumed that after tables 310, 320, 330 are defined in a mass storage means 130, the company decides to also keep track of which person drives which car, which person is a passenger in which car and further, who the owner of the car is.
A fourth table 340 (Table of Drivers) may be constructed as shown in
Referring to row D of table 340, it can be seen that one implied link L44 identifies driver D as being the person of P-IDN=4 who has the name implied by earlier link L41 and the home address implied by earlier link L43. Proximity link P45 implies that driver D drives the car having C-IDN=2. The latter number implies a logical link L46 to row 2 of table 350 which holds the serial number (SN) of the driven car. By way of another proximity link, P47, in row 2 of the same fifth table 350, a further logical link, L48, indicates that the owner of car C-IDN=2 is the person P-IDN=P of table 320. It was assumed by the structure of table 359 that each car can have only one owner and one serial number.
Consider, however, what happens if a new government regulation comes into being allowing for more than one owner per car or requiring multiple identification numbers for each car. The fifth table 350 may have to be restructured to add new columns (i.e., 354, 355, etc.; not shown) which would allow for the implication of such new relations. This means that the access control modules 120d* which define the "meaning" of each data field (subsection) within table 350 would have to be revised. Referring back to
A newer form of database organization, referred to sometimes as the "object oriented" approach, has been proposed to solve some of the problems associated with reorganizing and updating previous database systems. According to the object-oriented approach, encapsulation bubbles are defined to hide from external view, data which is encapsulated within the bubble. Each bubble is referred to as an "object" and the encapsulated information of the object is referred to as the object's "attributes." One bubble may encapsulate a second bubble which in turn encapsulates third, fourth and further bubbles so that a relatively complex data structure may be defined. Objects can be assigned to "classes" and by such assignment they can be made to automatically "inherit" the attributes of other objects in the same class, even when the class attributes are changed after creation of the objects.
There is still controversy in the field over what constitutes "object oriented" and how such a concept may be practically applied to database management systems. Experimental versions of object-oriented systems are often too slow in performing update and inquiry servicing to be practical in commercial settings. The present invention takes an approach which might be considered a partial hybrid of the object-oriented approach and the earlier-described relational database methodology. It provides a database system which is capable of operating at commercially acceptable speeds and which is easily restructured as well as updated. The invention will be explained first conceptually and then by concrete examples.
Referring to
Each entity bubble may contain one or more "instances" of the entity class (i.e., Customer, Address, Account) which it represents. By way of example, let it be assumed that there are three customers whose names are "Customer-A", "Customer-B" and "Customer-C". Let it be further supposed that because of a peculiar rule, the Customer bubble (also labeled as entity class "E-1") is restricted to contain the name of only one customer at a time, say "Customer-B", while the address bubble (E-2) can at the same time contain many "addresses", each corresponding to that Customer-B. If Customer-B is a person, the address instances might be summer-home and winter-home addresses. If Customer-B is the name of a business having a chain of stores, the plural addresses in the second bubble (E-2) might be the mailing addresses of those stores. The name "Customer-B" is an example of a first instance, I1/E1, of the E-1 entity class and is illustrated conceptually in
Until now we have been visualizing the instances, I1/E1, I1/E2, I2/E2, I3/E2 and I1/E3 of respective entity classes, E-1, E-2 and E-3 as isolated spheres floating separate from one another, without identifying any specific relation between the instances. The present invention treats "relations" as being objects of equal substance to the entities they tie together. There are relation "classes" and instances of a specified relation class. Three arrow-shaped bubbles, R-1, R-2 and R-3, are shown in
In more concrete terms, the top relation bubble R-1 is shown to have the meaning string "'s business". The substring, "'s" is a head character-string while the substring "business" is a tail character string. By itself, the meaning-string ('s business) appears to be nonsensical, but in conjunction with the class names its head and tail entities, E-1 ("Customer") and E-2 ("Address"), this first relations bubble, R-1, forms the relational phrase: "The Customer's business Address". Instance I1/E1 is a specific customer's name (i.e., "Customer-B") and instances I1/E2, I2/E2 and I3/E2 are now defined as specific instances of that customer's business addresses (i.e., the addresses of individual stores in a chain of stores owned by Customer-B).
Of importance, it is to be noted that the first entity bubble, E-1 (Customer), does not itself encapsulate the attribute of possession as indicated by the apostrophed head character-string "'s". Instead, that attribute of possession is encapsulated by the first relationship bubble, R-1. Furthermore, the second entity, E-2 (Address), does not encapsulate the modifying attribute "business". Instead that attribute is also encapsulated by the relation bubble R-1. Thus, each entity bubble (E-1, E-2, E-3) is free of any narrowing attributes or modifiers and instead, represents a relatively broad and generic listing of data items which can come under the heading of either "Customer" or "Address" or "Account". The advantage of this structure will become apparent shortly.
Consider for a moment what happens if the meaning-string in relation bubble R-1 is changed from "'s business" to "'s headquarters". Under this circumstance, the rules change. The address bubble (E-2) should be restricted to at any one time contain only a single instance (e.g., I1/E2) representing the "Customer's headquarters Address" rather than many instances. Presumably each customer can have only one headquarters address. Thus, the "cardinality" of relations bubble R-1 must be changed from its earlier one-to-many {1:m} format, as was possible with business addresses, to a one-to-one setting {1:1}. According to the invention, each relation bubble, R-x, has a cardinality rule (e.g., {1:1} and {1:m}) associated with its body B as well as a meaning- string (e.g., "'s business").
Consider, next what happens in a business database if users are allowed to enter a customer name but leave out the mailing address or telephone number of that customer. Most companies operate under a strict rule which requires its office workers to record at least one forwarding address or telephone number when the name of a new customer is entered. To enforce this requirement, each relation bubble (R-1) further incorporates a mandatory-coupling character which can be either "Y" or "N" (representing yes or no). If it is required that at least one instance (I1/E2) of a tail entity class E-2 should be created whenever an instance (I1/E1) of a head entity class E-1 is created, then the mandatory-coupling character of relation bubble R-1 is set to "Y". This indicates that instance I1/E1 should not exist without instance I1/E1. The "MC" lightning bolt shown emanating from I1/E1 represents this mandatory coupling of instances. On the other hand, if such coupling is not mandatory, the coupling character is set to "N" and there is no "MC" connection.
As further examples of the concepts behind the invention, the second relation bubble, R-2, is shown to contain in FIG. 4A the meaning string, "'s owning", the cardinality rule, {1:1}, and the mandatory-coupling character, "Y" presumably every account should have an owner). The third relation bubble, R-3, is shown to contain the meaning string, "'s statement mailing", the cardinality rule, {1:1}, and the mandatory-coupling character, "N" (presumably an account holder can pick up his/her statement rather than having it mailed). Instances of entity E-1 which satisfy the relationship created by relation bubble R-2 are read as "The Account's owning Customer". Instances of entity E-2 which comply with the relationship created by relation bubble R-3 satisfy the descriptive phrase, "Account's statement mailing Address", or stated otherwise, the address to which account statements are mailed for the particular instance I1/E3 of the Account entity class E-3.
By changing the meaning-string within a relation bubble R-x, it is possible to create new relational phrases although the Head and Tail entity classes remain the same. By changing either or both of the Head and Tail entity classes (E-h or E-t), it is possible to again create new relational phrases although the relation bubble R-x remains unchanged.
Consider what happens for example when the meaning-string of relation bubble R-3 is changed to the phrase: "which is managed at bank branch having". Then the combination of the class names or meanings associated with entity bubble E-3, relation bubble R-3 and entity bubble E-2 provides for an inquiry path allowing one to find the Account which has a specific bank branch address as its managing branch. Consider what happens if the tail portion T of relation bubble R-3 where moved from E-2 to a new entity bubble (not shown) which is labeled "Managing Officer" rather than "Address". Then the relational phrase becomes "Account which is managed at bank branch having [this person as its] Managing Officer". It can be seen that an entirely different inquiry path is formed with each change of a head entity type, tail entity type or relation type.
Inquiry paths can be defined to extend through pluralities of entity and relation bubbles as well as between just two entity bubbles. Still referring to
Relation bubbles (R-x) do not have to be single tailed. Referring to
With the above-mentioned conceptual models in mind, a concrete embodiment of the invention now will be constructed piece by piece. Referring to
For expedience sake, a matrix notation is used here to identify the columns of table 500 with letters, a, b, c, . . . , etc. and the rows with a numeral preceeded by a period. The symbol 500a.1 thus refers to the box in table 500 at column 500a and row 500.1.
As further seen in
In the corresponding right column 500b of the ENT.DEF table 500 there is stored, for each slot (.1, .2, .3, .4, etc.) the name of a single other table where instances of the named entity class are stored. The abbreviation "EiT" (Entity-instances-Table) will be used here to mean the table where instances of the entity class are stored. Again by way of example, box 500b.1 is shown to reference an EiT called "T.Companies" as the single table where instances of the entity class "Customer" are stored. The entry in box 500b.2 is "T.Addresses" and the entry in box 500b.3 is "T.Accounts". Note that the entry in box 500b.4 is "T.Companies" just as it is for box 500b.1. Instances belonging to two different entity classes (e.g., "CU" and "SU") may be stored in one instances table (EiT) under situations where the data structures of the instances are compatible to the structure of that EiT (e.g., the entity instances table has enough columns of appropriate widths to support the description of each entity instance).
Each entity class can be referenced not only by its abbreviated name (e.g., EA="AD") but also by the slot number (e.g., slot .2) where it is stored in the entity definition table 500. The slot number may function as an "entity type number" (abbreviated here as ETN) for numerically identifying its corresponding entity class. Alteratively, an additional "type number" column (not shown) may be added to the ENT.DEF table, 500, unique type number may then be entered into each row of the type number column and these can serve as the ETN's. Thus, the "Address" entity class may be referenced not only by the abbreviation EA="AD" but also by an entity type number whose value, ETN=2. For the relative table organization (RTO) shown in
Referring next to
The left-most column 600a holds a two character abbreviation representing the class name and/or meaning-string of a relation bubble. The mnemonic, RA, will be used here to designate such a relationship abbreviation. By way of example, box 600a.1 holds the abbreviation "-BU-" which represents the meaning-string "'s Business". (Hyphens embrace the relation abbreviations here to distinguish them from entity abbreviations [EA's].) Box number 600a.2 stores the abbreviation "-OW-" to represent the meaning-string "'s Owning". Box number 600a.3 stores the abbreviation "-SM-" to represent the meaning-sting "'s Statement Mailing". Box number 600a.4 holds the abbreviation "-HQ-" to represent the meaning-string "'s Main Headquarters".
Each row of the REL.DEF table 600 may also identified numerically by a "relationship type number" (RTN) which in the illustrated example happens to be the sane as the slot number (.1, .2, .3, etc.) where its corresponding two character code (-BU-, -OW-, -SM-, etc.) is stored. Alternatively, a type number column (not shown) may be added to the REL.DEF table 600 and unique RTN's may be assigned according to any desired, unique number generating scheme, such as according the alphabetic ordering of the RA's. In the latter case, the RTN's can also function as sort keys for ordering the rows of the REL.DEF table (using threaded list techniques) alphabetically according to relationship class names (RA's). Thus, when given a specific RTN, one can quickly calculate the physical or sequence to the logical address in the REL.DEF table 600 where details about the corresponding relation class are stored so as to quickly retrieve those details.
In the second column 600b of the REL.DEF table, there is stored, for each slot (.1, .2, .3, etc.), the name of a single table where instances of the named relation class are stored. The mnemonic, "RiT" (Relation instances Table), is used here to represent such a table. By way of example, the entries in boxes 600b.1, 600b.2, 600b.3 and 600b.4 are respectively: "T.Rel-1", "T.Rel-2", "T.Rel-3" and "T.Rel-1". Note that the entries of box numbers 600b.1 and 600b.4 are the same. Compatible instances of two different relation classes may be represented by two corresponding rows of data stored in a common relation-instances holding table (RiT).
The third column 600c of the REL.DEF table stores the type number (ETNh) of a head entity (E-h). Here, the entity type number (ETNh) is the same as an ETN assigned to a corresponding row in the ENT.DEF table 500 where the abbreviated class name (EA) of that head entity bubble is stored. Similarly, the fourth column 600d of the REL.DEF table stores the type number (ETNt1) of a corresponding first tail entity (E-t1).
Note that the first three rows (600.1, 600.2 and 600.3) in
Similarly, row number 600.2, columns c, a, d correspond to the relationship descriptor phrase "Account's owning Customer". Box 600b.2 tells us that instances of this relation are stored in table T.Rel-2. Row number 600.3 likewise corresponds to the relationship describing phrase "Account's statement mailing Address" and tells us that instances of this relation are found in the T.Rel-3 table.
The REL.DEF table 600 can be updated indefinitely by adding new rows to its bottom so as to encompass a great number of further relation classes. There is no need to physically order the data describing each of the relational classes and thus descriptions of new classes can be added to the bottom or other empty slots of the REL.DEF table 600 sporadically as the need arises over time. Relation classes which become obsolete can be deleted to leave behind an empty slot. Similarly, there is no need to order the entity classes defined by the ENT.DEF table 500. The ENT.DEF table can be updated by arbitrarily adding new entity class describing rows to its bottom or other empty slots or by deleting obsolete entries as the need arises. Accordingly, when demands on the database system of the invention change over time, new relation classes may be defined in combination with new head and tail entity classes. The schema of the invention can be continuously restructured as the need arises simply by updating the REL.DEF and ENT.DEF tables, 600 and 500.
The fifth columnar region 600e of
Extension region 600e is shown to include a tail activating column 606 which functions as a mask to activate or deactivate each of the corresponding tail entity columns 600d, 602-605. In the illustrated example, a dark filled circle means that the corresponding tail entity of that slot (row) is active while an unshaded circle means that the respective tail entity is deactivated. As an alternate embodiment, the mask column 606 may be dispensed with and the lack of an ETN entry (or a "null" entry) in a box of columns 602-605 will be regarded as indicating a deactivated tail while the inclusion of an ETN value will be regarded as indication an active tail. When two or more tail entities are activated, the relation bubble takes on a multi-tailed form such as shown in
Returning to
Referring to
The broader view 700 reveals a third table 730 which is labeled in
Columns 730a and 730b in combination identify particular instances of a head entity class (Head Ei) while columns 730d and 730e in combination identify particular instances of a tail entity class (Tail Ei). Referring specifically to box number 730a.2 of the T.REL-1 table 730, the "CU" (or alternatively ETNh=.1) entry of this box directs the data retrieval machine 815 of the invention to a first section 500.1 of the ENT.DEF table where there is stored the name of a first table (EiT-1="T.Companies") where instances of this names entity class ("CU") are stored. The logical link from third table (RiT) 730 to table area 500.a is labeled as L731. The link from table area 500.1 to the first table (EiT-1) 710 is labeled as L751.
The second column 730b of the T.REL-1 table holds the slot number or "Entity-instance Number" (EiN=.5 of box 730b.2 for example) of the indirectly referenced Entity-instances table (T.Companies 710) within which a specific instance (Ei="Expert Electronics") of the named head entity class (EA="CU") is stored. In this example, box number 710a.5 of the first EiT 710 contains the name "Expert Electronics" and this name-string is the entity instance referenced by the "CU.5" entries of boxes 730a.2 and 730b.2. The link from box 730b.2 to box 710a.5 is labeled as logical link L732.
Referring to columns 730d and 730e of slot number 730.2, a similar linkage is created to the instance of a tail entity class. In the illustrated example, the "AD" entry of box 730d.2 points to a second section 500.2 of the ENT.DEF table (thereby defining link L733) where a second pointer is found to a second Entity-instances Table (EiT-2) which in this example is the T.Addresses table 720 (thereby defining link L752). Box 730a.2 holds the slot number (.4) of the indirectly referenced table 720 in which the target data "555 Transistor Lane" is stored (thereby defining link L734). Thus, the illustrated Relationship-instances Table (RiT) 730 defines a connecting relationship (extending from the arrowhead of L732 to row 730.2 to the arrowhead of L734) which joins the instance "Expert Electronics" of entity class "Customer" (CU) with the instance "555 Transistor Lane" of the "Address" (AD) entity class. Each row of the RiT 730 is referred to as a "Relation-instance" (abbreviated as Ri) and the slot number of that row defines a corresponding "Relation-instance Number" (RiN). (while not shown, it is within the contemplation of the invention to add a "instance number" column to any of tables 710, 720 or 730 so as to uniquely identify their rows by arbitrarily assigned instance numbers, EiN or RiN, rather than relying on an RTO slot number, but the RTO slot number approach is believed to result in faster data access.) Columns 730a-730b accordingly define the head portion of a "Relation-instance" (Ri) and columns 730d-730e define a tail portion of the relations-instance (as conceptually shown in FIG. 4A). Column 730c, as will now be seen, defines the body portion of each Relation-instance (Ri).
Referring to the middle column, 730c, of the T.REL-1 table 730, this column holds an identifier pointing to a corresponding row in the REL.DEF table 600 where the relationship class of the instant relationship (Ri) is defined. For the sake of illustrative clarity, the RA of each relation class is shown entered in column 730c. It is within the contemplation of the invention to alternatively enter the corresponding slot number, RTN, of the REL.DEF table 600 so as to speed the access time of the retrieval machine 815. By way of example, the entry "-BU-" in box 730c.2 indicates that the relationship between the head instance, Customer.5, and the tail instance, Address.4, is the "'s Business" meaning-string associated with slot 600.1 of the REL.DEF table (FIG. 6).
The relation instances table, T.REL-1 730, may contain many rows, each of which has the identical head entity-instance entries (in col.s 730a and 730b), identical tail entity-instance entries (in col.s 730d and 730e), but different relationship-defining entries (e.g., -BU-, -HQ-, -OW-, etc.) in column 730c. Each of these almost identical rows would represent a different Relation-instance (Ri). As an example, the address instance AD.4 might be the "Business" address of customer instance CU.5 as shown in slot 730.2. But it may also be the headquarters address "-HQ-" of that same customer CU.5 as shown in slot 730.6. Each of these is considered a different relation instance (Ri). The T.REL-1 table 730 is accordingly shown to include two separate row entries: 730.2=CU.5-BU-AD.4 and 730.6=CU.5-HQ-AD.4. A relational query which asks the question, "What is the headquarters address of my customer, Expert Electronics!" would be answered by accessing row 730.6 of the T.REL-1 table 730. The slightly different relational query, "What are all the business addresses of my customer, Expert Electronics!" would be answered by accessing all rows in the T.REL-1 table 730 beginning with the entries, "CU.5-BU-", which in the illustrated case includes rows 730.2 and 730.5.
With the illustrated structuring of a Relation-instances Table (RiT 730), all sorts of relational inquiries can be answered by starting with a known first instance of a first entity class, irrespective of whether the class is a head entity class or tail entity class, and searching through the RiT 730 to locate all relationship-instances (Ri's) of which that starting instance is a member. Once the matching Ri rows are found within a designated Relation-instances Table (RiT), it becomes a simple matter to scan horizontally across the row from the starting instance through the relation descriptor of column 730c to find the corresponding, but until now, unknown instances of the opposed tail and head entity classes.
The uncovered instances can then serve as stepping stones for answering further parts of a compound query. Consider for example the two-level query, "What are all the business addresses of my customer Expert Electronics, and once you know that, what other customers use those addresses as their business addresses!" There may be a plurality of business addresses satisfying the first part (Level-1) of the question and each such answer would serve as a new stepping stone leading to the answers which satisfy the second part (Level-2) of the question.
In accordance with the invention compound queries are answered by defining one or more question lines in an inquiry-definition (INQ.DEF) table 740. Each question line is identified as belonging to either a one level question or to a particular level of a compound question. A first column 740a of the INQ.DEF table is provided for holding the entity type numbers (ETN) of one or more entity classes, regardless of whether they are known at the start of a query. A second column 740b of the INQ.DEF table is provided for holding corresponding instance-identification numbers (EiN), again regardless of whether they are known at the start of a query. A third column 740c is provided for holding one or more relation type numbers (RTN) while a fourth column 740d is provided for holding corresponding relation-instance numbers (RiN), some of which may be known and others not known at the start of a query. Fifth column 740e defines the level of each question row relation to preceding question rows.
An RTN value, which if known, is entered in a box of third column 740C in order to indicate to the retrieval machine 815 a corresponding row in the REL.DEF table 600 from which the retrieval machine 815 can obtain the name of the single table (RiT-x) where all instances of the named relation type (RTN) reside. The identified table, RiT-x, can then be searched for one or more Ri rows which hold information relevant to a posed query. When found, the RiN values of those rows are entered into one or more boxes of fourth column 740d. The specific Ri rows (e.g., row 730.2) which are fully specified by filled in RTN-RiN data pairs of the INQ.DEF table 740 can then be accessed to direct the retrieval machine 815 to the corresponding head and tail entity instances of interest (e.g., the CU.5 and AD.4; instances which are related to one another by the -BU- entry of box 730c.2).
If a specific Ri row is not fully identified at the beginning of a query within a row of the INQ.DEF table 740 by a completed RTN-RiN pair, the Ri row or rows of interest can be nonetheless located by partially filling in a row within the INQ.DEF table 740 and then searching the REL.DEF or ENT.DEF tables for additional information. Row 740.2 of the INQ.DEF table is shown to have the question line, "!!.!-HQ-!" which may mean "Please identify the Headquarters addresses of all my customers". In such a case, all rows of the T.REL-1 table 730 which have the entry -HQ- in their middle column 730c would provide the required information. Each such -HQ- row of RiT 730 would pair an identified instance of a Customer (head Ei) with an identified instance of a headquarters Address (Tail(1) Ei). It is to be appreciated that for cases of multi-tailed relation classes, the corresponding RiT would have columns for identifying the other tail entity instances (e.g. Tail(2) Ei, Tail(3) Ei, etc., not shown).
Sometimes a question is more specific. By way of example, let it be assumed that an inquiring user has a specific but fragmentary piece of starting information such as the street address "555 Transistor Lane". The inquiring user wishes to find out the names of one or more companies for whom "555 Transistor Lane" is a "Business Address". The user identifies the fragmentary information to the data retrieval machine 815 as belonging to the "Address" entity class. In response, the machine 815 searches through the ENT.DEF table 500 to locate the entity type number "ETN" of the named class and the Entity-instances Tale "EiT" where all instances of this "Address" entity class are stored. It should be recalled that the illustrated relative-table organization "RTO" of the ENT.DEF table 500 is not mutually exclusive of a key-sequenced organization "KSO". According to the invention, the EA column 500a of the ENT.DEF table is threaded alphabetically so that the row of a desired entity class (e.g., EA ="AD") can be easily found using known key-sequenced search algorithms. A different table (not shown) can serve as an abbreviation to full name look-up table for converting between the entity name abbreviation (EA) and the full name or narrative description of the entity class (ECN) if desired or, alteratively, the ENT.DEF table 500 may include one or more additional columns (not shown) for providing this search and conversion function.
Once the corresponding type number (ETN) of the entity class is identified, in this case ETN=.2 referencing slot 500.2, the retrieval machine 815 places this first puzzle piece into an appropriate box of the INQ.DEF table. In this example it will be box 740a.3 of INQ.DEF question line 740.3 which is for illustrative purposes filled with the corresponding EA="AD".
The retrieval machine 815 then obtains from box 500b.2 of the ENT.DEF table the name of the corresponding EiT where it is to search for the occurrence of the fragmentary information "555 Transistor Lane". The EiT's can be key-sequence organized (KSO) in addition to their RTO structuring to facilitate such searching. After the corresponding EiT (in this case, the T.Addresses table 720) is searched and the row of the fragmentary information is found, its corresponding EiN, in this case .4, is entered as an entity-instance number (EiN) in box 740b.3 of the INQ.DEF table 740.
The earlier found entity type number (ETN) which corresponds to EA="AD" now combines with the EiN=.4 of INQ.DEF row 740.3 to define the "starting instance" for resolving question line 740.3. The starting instance is AD.4.
The relationship type number (RTN) of the relationship under question (-BU-) is entered in box 740c.3. If the RTN value is not known, the REL.DEF table 600 is first searched to generate the appropriate RTN. While not shown, the REL.DEF table or some other table will includes a full name or narrative column for converting between a relationship's full name/description and its abbreviated form (RA). Box 740d.3 is now the last puzzle piece to be filled in as indicated by a question mark in FIG. 7.
Since the ETN.EiN-RTN- entries of boxes 740a.3, 740b.3 and 740c.3 are now all known, the retrieval machine 815 searches through the corresponding RiT (T.REL-1 table 730) to locate all relation-instances (Ri') which have the corresponding ETN plus Ein in the tail entity instances columns 730d and 730e and the corresponding RTN in column 730c. The REL.DEF table 600 identifies the starting entity class of the AD.4-BU-! question as being a tail entity. (When there is more than one tail entity, the RiT will have plural columns for identifying first, second, etc. tail instances and the REL.DEF table 600 will specify which of these tail columns is to be searched.) In the illustrated example, row 730.2 of the T.REL-1 table will be found to have matching information. The retrieval machine 815 can now fill the last empty box 740d.3 of the INQ.DEF row 740.3 with the information RiN=.2. Once question row 740.3 is completely filled, the retrieval machine 815 may use the information of this INQ.DEF row 740.3 to retrieve the detailed information about the head entity instance, Ei="Expert Electronics" from table row 710a.5 of the T.Companies table.
The ETN.EiN identifiers of the uncovered Level-1 answer, "Expert Electronics" can now serve as stepping stones which fuel a second part of a compound query. For example, the full query might have been "Who has business address, 555 Transistor Lane and what bank accounts belong to the entity or entities that satisfy the first part of this question!" The first part is defined here as "Level-1" of the question and the second part as "Level-2". Column 740e of the INQ.DEF table is shown to identify the level number. Referring to a feedback link L744 shown in
Referring to
Since the REL.DEF and ENT.DEF tables may be expanded as desired by adding new entries to empty middle or bottom slots found within them, a lay user can create new entities, new relation classes and restructure the schema of explicitly-defined relationships and entities forever without having to reprogram the database system 800 at the source or object code level. Instead, the lay user supplies schema restructuring commands, in an appropriate structured language, as indicated at 870 for restructuring the schema whenever needed. The access control program 820d of the retrieval machine 815 may remain fixed while the entity-to-explicit-relationship schema or region 130-RP is forever changed. Accordingly, object-code compilation 814 needs to occur only once. This source code listing 812 of this access control program needs to be developed and debugged only once. Substantial cost savings are realized, especially as time progresses and new entity-relationship schemas are required.
In some commercial applications, the ENT.DEF table and REL.DEF table may be relatively short, having for example less than 1000 rows each (e.g., the ENT.DEF table may have 30 rows or less and the REL.DEF table may have approximately 100 rows or less). For suchy cases it has been found advantageous to "copy" the ENT.DEF and REL.DEF tables from the bulk storage means 130* to a higher speed memory area within first memory means 120 in order to shorten processing time. The copied versions of the ENT.DEF and REL.DEF tables can be purely-key-sequenced if an additional "type number" column is added for storing the respective ETN's and RTN's of each row. The higher data access speed of the first memory means 120 more than compensates for any speed reduction which might be caused by switching to a purely key-sequenced organization. These "mirror" copies of the ENT.DEF and REL.DEF tables are then accessed by the CPU 110 in place of the original ENT.DEF and REL.DEF tables. It is advisable to periodically check the original ENT.DEF and REL.DEF tables for possible revisions, since lay users may update that original tables at any time, and when such revisions are detected, to immediately recopy the ENT.DEF and REL.DEF tables into the first memory means 120 so that the mirror tables faithfully reproduce the contents of the original tables.
The CPU 110 in combination with the various modules of the object code 820d can be visualized as one or more machine means for performing data-altering functions as specified by the object code 820d. A Microfiche Appendix is included here listing sample modules written in Tandem COBOL'85™ and TANDEM SCREEN COBOL™ for execution on a Tandem NONSTOP™ computer system running under Tandem NonSTOP SQL™, TMF™, Pathway™, SCOBOLX™ and Guardian™ systems (all available from Tandem Computers of Cupertino, Calif.). It is to be understood that the sample modules disclosed in the Microfiche Appendix are merely exemplary. The invention may be practiced using different computer hardware and/or software.
Referring to
Relationship inquiry in general is a two step operation: path selection (to create an Inquiry) and inquiry execution. On a Path Selection screen (not shown) the operator selects starting and optionally ending entity types and supplies detailed description of the path to follow. Each path is defined in terms of:
- a starting entity type to initiate the query path,
- a connecting relationship type which will lead to an intermediate entity type and then to anther connecting relationship type and another intermediate entity type, and so forth until
- a last connecting relationship type leads to a terminating entity type
Taking out all but the key words from the above, we get the form structure:
- <starting entity type>
- <connecting relationship type><intermediate entity type>
- <connecting relationship type><intermediate entity type>
- <connecting relationship type><terminating entity type>
A single inquiry definition may initiate several parallel paths which extend from a starting entity type to an ending entity type. When the ending entity type has not been specified in the header of the path-selecting screen then all these parallel paths can end with different entity types. For example, an inquiry to show a person's total involvement with all accounts held at a bank could be defined as shown in the following Table I:
Person —>
Person —>
Person —>
Person —>
Card Holder
Person —>
Group Member
Person —>
Group Member
Card Holder
Each of the above lines is a separate path generated by one inquiry form. The results of the inquiry would show all Accounts a Person had influence over, either directly or as a member of a partnership.
For simplicity the above inquiry is shown on the screen as in the following Table II:
Account Holder
Loan Guarantor
Card Holder
Group Member
Joint Party
Account Holder
Card Holder
Note that level numbers are used to determine which entity types are intermediate to a path, which entity types terminate a path, and which relationship types commence a new parallel path. A line containing a level number which is the same as that of an immediately previous line indicates a parallel path separate from the previous line. A level number greater than that on the previous line indicates the entity on the previous line is an intermediate entity (i.e. the path is an association, and will follow several relationship links before terminating the path.)
Once a set of paths have been stored as an inquiry and recorded in the system it may be executed. Each unique set of inquiries is given a unique name, stored as such in the inquiry-definition table (INQ.DEF) and may be recalled for execution repeatedly at any time without need to go through the path selection process again. Before executing the predefined inquiry, the operator must select one or more starting entity instances for which the query is to run. Hence for each execution of an inquiry, the operator must choose which occurrence of the Starting Entity Type to use. Using the previous sample inquiry to investigate persons of the names, "John Smith" and "Bill Brown", the operator would execute the same inquiry once using "John Smith" as the Starting Entity instance and once using "Bill Brown" as the Starting Entity instance.
The Inquiry is executed by examining each of the defined paths in turn. Starting with the selected entity and following the first relationship, a list of intermediate (or target) entities is assembled. For each of the intermediate entities the next leg of the path is followed through the level 2 relationship etc. until the inquiry operation arrives at the ending entity type at which time the results of the entire path (with all intermediate entities and relationships) may be displayed to the operator.
If the ending entity type has been specified during inquiry definition, then at execution time the operator may select not only the starting entity occurrence of interest but also the occurrence of an ending entity. In this case the inquiry will return results from only the paths that satisfy this termination condition.
Reusable inquiry sets would normally only be created by privileged users. However, each inquiry set that is created for subsequent executions may be given its own security settings and attached to its own menu. Hence where sensitive data was involved, normal operators would be given access to only those inquiry sets they specifically need for their day to day business operations.
Despite its complexity, the inquiry engine 900 of the invention can operate at high speed because the EiT and RiT structures, while they may be large in size rely on relative tables. Relative table structures have always offered high performance for Random memory access (as opposed to key-sequenced access) but presented many complications and difficulties in other areas of use (e.g. updating). Because of this, conventional wisdom has been to use purely Key-Sequenced structures almost exclusively. Key-Sequenced structures pay performance penalties for the use of extra indexing levels.
The first problem with Relative structures was that with some early versions, deleted row locations (or slots) could not be re-used without file (table) reorganization. Reorganization of Relative structures in this case meant compressing the file (table) to regain unused slots. This process can change the relative addresses from their original values, which can cause corruption of the database. Reorganizion is no longer required because Relative structures such as offered in Tandem's NonSTOP SQL™ system allow deleted row slots to be reused immediately. The Tandem system actually ensures that vacated slots are used again and again. Relative tables in NonSTOP SQL™ can be partitioned and re-partitioned without risk of corrupting the database, but table compression is no longer necessary or allowed. Partitioning a table means that the table can be split across a plurality of data storage devices, usually disks, transparent to the object code of the application program running under NonSTOP SQL™.
The second problem with Relative structures was implementing meaningful keys that allowed access to the data in a sequence based on indicative data, such as numerical order of account number or alphabetical order of customer name. However, by using Alternate Key index tables it is possible to provide meaningful sequential access of entities stored within Relative Tables.
The Relationships Processor or "engine" of the present invention is a "Closed Loop" system in that all explicit schema definitions are stored within the system. The finite set of tables and their meanings are also defined within the system. This provides an infrastructure that makes the Table Structures transparent to users and developers. Hence, Relative tables can be used for performance improvements while avoiding any usability penalties that once existed.
Hence this invention has gone against conventional attitudes because of new data processing techniques used by the invention.
The above advances in Relative structure techniques, coupled with the closed loop nature of the Relationships Processor has allowed Relative tables to be used in a controlled and meaningful way, destroying the premise that Key-Sequenced structures are the best way to store relationships.
A benchmark was run on a Tandem NonSTOP SQL™ system to test the system's performance capabilities. The benchmark was to stimulate the normal processing requirements of an extremely large bank's Customer Information System.
The database used 14 Gigabytes of disk storage space, and was populated with 5 million Customers, 7 million Cards, 9 million Addresses, 10 million Accounts and 67 million relationships.
The benchmark simulated 1000 simultaneous users (tellers), with each user executing 100 typical on-line transactions.
The invented system achieved a rate of 64 transactions per second with less than 2.6 second response time for 90% of all transactions which included all screen formatting. This is quite remarkable for a database system of this size and complexity.
The invented system was also benchmarked for batch processing at rates of hundreds of transactions per second. This shows that the system is able to process inquiries at commercially acceptable rates.
Referring to
After termination, the results of the inquiry loop are fed through signal bus 911 to an abbreviated results compiling means 915 which orders the results according to their level number and interrelation. By way of example, a first Level-2 inquiry may produce intermediate answer, Ei-2a. That intermediate answer together with its forward-connecting relation (RTN2) may produce a plurality of intermediate answers at Level-3, namely, Ei-32a.1, Ei-32a.2, etc. Each of these Level-3 answers may then result in a larger plurality of Level-4 answers (not shown) and so forth. Likewise the Level-2 answer Ei-2b may produce a plurality of Level-3 answers, Ei-32b.1, Ei-32b.2, Ei-32b.3, etc. Each of these answers is recorded as a paired set of an entity class number ETN and an entity instance number EiN. The abbreviated results are then expanded into user-understandable results by sending an entity type number signal, sETNx to the entity definition means 950 and a corresponding entity instance signal, sEiN to the entity storage means 920. In response the entity storage means 920 then produces detailed information from the referenced entity instances tables. Often, the database user may not wish to see all of the detailed information within a row, but rather wishes to see only prespecified columns of the referenced row and wishes the data to be displayed according to a predetermined display format. The details filter 985 filters out information from undesired columns and orders the remaining data according to a predetermined display format selected by the user. The desired "real" information then appears in the selected format on display means 990.
Referring to
A variety of modifications will become apparent to those skilled in the art in light of the above description. The scope of the claimed invention is accordingly, defined, not by any specific embodiment described herein, but rather by the following claims.
Claims (16)
Priority Applications (4)
|Application Number
|Priority Date
|Filing Date
|US52642490 true
|US08083861 US5604899A (en)
|Data relationships processor with unlimited expansion capability
|US08439013 US5617567A (en)
|Data processing system and method for retrieving and entity specified in a search path record from a relational database
|US11152833 USRE40526E1 (en)
|Data processing system and method for retrieving and entity specified in a search path record from a relational database
Applications Claiming Priority (1)
|Application Number
|Priority Date
|Filing Date
|US11152833 USRE40526E1 (en)
|Data processing system and method for retrieving and entity specified in a search path record from a relational database
Related Parent Applications (1)
|Application Number
|Priority Date
|Filing Date
|US08439013 Reissue US5617567A (en)
|Data processing system and method for retrieving and entity specified in a search path record from a relational database
Publications (1)
|Publication Number
|Publication Date
|USRE40526E1 true USRE40526E1 (en)
Family Applications (9)
|Application Number
|Priority Date
|Filing Date
|US08083861 Expired - Lifetime US5604899A (en)
|Data relationships processor with unlimited expansion capability
|US08439076 Expired - Lifetime US5652882A (en)
|Data processing system and method for detecting mandatory relations violation in a relational database
|US08439013 Expired - Lifetime US5617567A (en)
|Data processing system and method for retrieving and entity specified in a search path record from a relational database
|US08439207 Expired - Lifetime US5675779A (en)
|Data processing system and method for maintaining cardinality in a relational database
|US08862176 Expired - Lifetime US5826259A (en)
|Easily expandable data processing system and method
|US11152835 Expired - Fee Related USRE40520E1 (en)
|Easily expandable data processing system and method
|US11152833 Expired - Lifetime USRE40526E1 (en)
|Data processing system and method for retrieving and entity specified in a search path record from a relational database
|US11152839 Expired - Lifetime USRE40063E1 (en)
|Data processing and method for maintaining cardinality in a relational database
|US11152838 Expired - Lifetime USRE40235E1 (en)
|Data processing system and method for detecting mandatory relations violation in a relational database
Family Applications Before (6)
|Application Number
|Priority Date
|Filing Date
|US08083861 Expired - Lifetime US5604899A (en)
|Data relationships processor with unlimited expansion capability
|US08439076 Expired - Lifetime US5652882A (en)
|Data processing system and method for detecting mandatory relations violation in a relational database
|US08439013 Expired - Lifetime US5617567A (en)
|Data processing system and method for retrieving and entity specified in a search path record from a relational database
|US08439207 Expired - Lifetime US5675779A (en)
|Data processing system and method for maintaining cardinality in a relational database
|US08862176 Expired - Lifetime US5826259A (en)
|Easily expandable data processing system and method
|US11152835 Expired - Fee Related USRE40520E1 (en)
|Easily expandable data processing system and method
Family Applications After (2)
|Application Number
|Priority Date
|Filing Date
|US11152839 Expired - Lifetime USRE40063E1 (en)
|Data processing and method for maintaining cardinality in a relational database
|US11152838 Expired - Lifetime USRE40235E1 (en)
|Data processing system and method for detecting mandatory relations violation in a relational database
Country Status (1)
|US5604899A (en)
Families Citing this family (121)
|Publication number
|Priority date
|Publication date
|US5604899A (en)
|Financial Systems Technology Pty. Ltd.
|Data relationships processor with unlimited expansion capability
|FR2724471B1 (en) *
|Bull Sa
|A object-oriented interfaces for generation of relational databases and method implemented by said device
|JPH08235033A (en) *
|Nec Corp
|Joint arithmetic system for object-oriented data base management system
|US6078925A (en) *
|International Business Machines Corporation
|Computer program product for database relational extenders
|US5701471A (en) *
|Sun Microsystems, Inc.
|System and method for testing multiple database management systems
|US5918224A (en) *
|Borland International, Inc.
|Client/server database system with methods for providing clients with server-based bi-directional scrolling at the server
|JP2988394B2 (en) *
|Device and method for processing data base for variable length object and storage medium for storing data base processing program
|US5875334A (en) *
|International Business Machines Corporation
|System, method, and program for extending a SQL compiler for handling control statements packaged with SQL query statements
|US5974455A (en) *
|Digital Equipment Corporation
|System for adding new entry to web page table upon receiving web page including link to another web page not having corresponding entry in web page table
|US5860011A (en) *
|Parasoft Corporation
|Method and system for automatically checking computer source code quality based on rules
|US5802512A (en) *
|Oracle Corporation
|Storage, replay and error detection of user-defined queries
|US5899997A (en) *
|Transparency Systems, Inc.
|Object-oriented query mechanism
|US5752028A (en) *
|Ellacott; Bruce Arthur
|Object-oriented query mechanism
|US5826268A (en) *
|Ontos, Inc.
|Secure multilevel object oriented database management system
|US5870747A (en) *
|Informix Software, Inc.
|Generalized key indexes
|US5745889A (en) *
|Digital Equipment Corporation
|Method for parsing information of databases records using word-location pairs and metaword-location pairs
|US5832500A (en) *
|Digital Equipment Corporation
|Method for searching an index
|US5864863A (en) *
|Digital Equipment Corporation
|Method for parsing, indexing and searching world-wide-web pages
|US5809502A (en) *
|Digital Equipment Corporation
|Object-oriented interface for an index
|US6745194B2 (en)
|Alta Vista Company
|Technique for deleting duplicate records referenced in an index of a database
|US5745890A (en) *
|Digital Equipment Corporation
|Sequential searching of a database index using constraints on word-location pairs
|US6167393A (en) *
|Novell, Inc.
|Heterogeneous record search apparatus and method
|US6185559B1 (en)
|Hitachi America, Ltd.
|Method and apparatus for dynamically counting large itemsets
|JP3779431B2 (en) *
|Relational database management apparatus, the intermediate link table automatic creation processing method, and program storage medium
|US6052672A (en) *
|Financial Systems Technology Pty Ltd.
|Data processing system for complex pricing and transactional analysis
|US7127420B1 (en)
|Financial Systems Technology (Intellectual Property) Pty. Ltd.
|Data processing system for complex pricing and transactional analysis
|US6163781A (en) *
|Physician Weblink Technology Services, Inc.
|Object-to-relational data converter mapping attributes to object instance into relational tables
|US6026382A (en) *
|Ncr Corporation
|Computer-implemented system for relationship management for financial institutions
|US6243703B1 (en) *
|International Business Machines Corporation
|Method of accessing and displaying subsystem parameters including graphical plan table data
|US6061690A (en) *
|Oracle Corporation
|Apparatus and method for storage of object collections in a database system
|US6035306A (en) *
|Terascape Software Inc.
|Method for improving performance of large databases
|US6421462B1 (en)
|Compaq Computer Corporation
|Technique for differencing an image
|US6240197B1 (en)
|Compaq Computer Corporation
|Technique for disambiguating proximate objects within an image
|US6400830B1 (en)
|Compaq Computer Corporation
|Technique for tracking objects through a series of images
|US6141434A (en) *
|Christian; Andrew Dean
|Technique for processing images
|US6556708B1 (en)
|Compaq Computer Corporation
|Technique for classifying objects within an image
|US6052132A (en) *
|Digital Equipment Corporation
|Technique for providing a computer generated face having coordinated eye and head movement
|US6184858B1 (en)
|Compaq Computer Corporation
|Technique for updating a background image
|US6434271B1 (en)
|Compaq Computer Corporation
|Technique for locating objects within an image
|US6043827A (en) *
|Digital Equipment Corporation
|Technique for acknowledging multiple objects using a computer generated face
|US6105035A (en) *
|Lucent Technologies, Inc.
|Method by which notions and constructs of an object oriented programming language can be implemented using a structured query language (SQL)
|GB2334601B (en) *
|Database data model extension
|US6138100A (en) *
|At&T Corp.
|Interface for a voice-activated connection system
|US6185560B1 (en)
|Sungard Eprocess Intelligance Inc.
|System for automatically organizing data in accordance with pattern hierarchies therein
|US6249292B1 (en)
|Compaq Computer Corporation
|Technique for controlling a presentation of a computer generated object having a plurality of movable components
|US6163822A (en) *
|Compaq Computer Corporation
|Technique for controlling and processing a section of an interactive presentation simultaneously with detecting stimulus event in manner that overrides process
|US6014614A (en) *
|Oracle Corporation
|Method and mechanism for performing spatial joins
|US6304876B1 (en)
|Computer Associates Think, Inc.
|Method for enforcing integrity constraints in a database table using an index
|US6112209A (en)
|Gusack; Mark David
|Associative database model for electronic-based informational assemblies
|US6327606B1 (en) *
|Oracle Corp.
|Memory management of complex objects returned from procedure calls
|US7076507B1 (en)
|Required Technologies, Inc.
|Value-instance-connectivity computer-implemented database
|US6513041B2 (en) *
|Required Technologies, Inc.
|Value-instance-connectivity computer-implemented database
|US6009432A (en)
|Required Technologies, Inc.
|Value-instance-connectivity computer-implemented database
|GB2343763B (en) *
|Shell Services Internat Ltd
|Data processing system
|GB9819394D0 (en) *
|Balaena Limited
|US6487551B2 (en)
|International Business Machines Corporation
|Externalizing very large objects in a relational database client/server environment
|US6473896B1 (en) *
|Parasoft, Corp.
|Method and system for graphically generating user-defined rules for checking language quality
|US6735593B1 (en) *
|Simon Guy Williams
|Systems and methods for storing data
|US6339766B1 (en) *
|Electronic payment system employing limited-use account number
|US6438549B1 (en) *
|International Business Machines Corporation
|Method for storing sparse hierarchical data in a relational database
|US6735591B2 (en) *
|Joseph M. Khan
|Universal information warehouse system and method
|US7389305B1 (en) *
|Fair Isaac Corporation
|System and method for managing a database
|US7103806B1 (en) *
|Microsoft Corporation
|System for performing context-sensitive decisions about ideal communication modalities considering information about channel reliability
|US6421663B1 (en)
|International Business Machines Corporation
|Optimization of joined table expressions by extended access path selection
|US6502088B1 (en)
|International Business Machines Corporation
|Method and system for improved access to non-relational databases
|US6542904B2 (en) *
|International Business Machines Corporation
|Method and system for efficiently providing maintenance activity on a relational database that is utilized within a processing system
|WO2001015013A1 (en) *
|The Bismin Trust
|Data processing system
|US9076448B2 (en) *
|Nuance Communications, Inc.
|Distributed real time speech recognition system
|US7050977B1 (en)
|Phoenix Solutions, Inc.
|Speech-enabled server for internet website and method
|US7725307B2 (en)
|Phoenix Solutions, Inc.
|Query engine for processing voice based queries including semantic decoding
|US7392185B2 (en)
|Phoenix Solutions, Inc.
|Speech based learning/training system using semantic decoding
|US6633879B1 (en) *
|International Business Machines Corporation
|Method and system for optimizing direct tables and trees
|US6636858B1 (en) *
|Michael T. Coffey
|Method for formatting, associating organizing, and retrieving data of and from a database stored in a computer system
|US6915298B1 (en) *
|International Business Machines Corporation
|User-defined relationships for diagramming user-defined database relations
|US7162713B2 (en) *
|Arc International
|Difference engine method and apparatus
|WO2001072011A9 (en) *
|Us Postal Service
|Methods and systems for proofing identities using a certificate authority
|US6622144B1 (en)
|Ncr Corporation
|Methods and database for extending columns in a record
|US20020065815A1 (en) *
|Xcelerix, Inc.
|Systems and methods for searching a database
|GB2368929B (en) *
|Andrew Mather
|An improved system for storing and retrieving data
|US6915303B2 (en)
|International Business Machines Corporation
|Code generator system for digital libraries
|WO2002063502A1 (en) *
|Regt Marcelinus Wilhelmus De
|Organic dictionary method for storage and unlocking data
|US7606744B1 (en)
|Financial Systems Technology (Intellectual Property) Pty. Ltd.
|System and method for real-time pricing with volume discounting
|US7330895B1 (en)
|Microsoft Corporation
|Representation, decision models, and user interface for encoding managing preferences, and performing automated decision making about the timing and modalities of interpersonal communications
|US7389351B2 (en) *
|Microsoft Corporation
|System and method for identifying and establishing preferred modalities or channels for communications based on participants' preferences and contexts
|GB2379289B (en) *
|Gordon Ross
|An interactive multi-dimensional visual user interface
|CA2353026A1 (en) *
|Raj Vadavia
|Adaptive data architecture
|US7693845B2 (en)
|NetTraffic, Inc.
|Database systems, methods and computer program products using type based selective foreign key association to represent multiple but exclusive relationships in relational databases
|US20030220879A1 (en) *
|Gaughan Breen P.
|System and method for electronic document processing
|US7644144B1 (en)
|Microsoft Corporation
|Methods, tools, and interfaces for the dynamic assignment of people to groups to enable enhanced communication and collaboration
|US20030196574A1 (en) *
|Keter Plastic Ltd
|Collapsible table formed of injection-molded half sections
|US7870240B1 (en)
|Microsoft Corporation
|Metadata schema for interpersonal communications management systems
|US7627585B2 (en) *
|Sap Ag
|Data structure mapping and packaging
|US20120158633A1 (en) *
|Jeffrey Scott Eder
|Knowledge graph based search system
|WO2004079588A1 (en) *
|Sap Aktiengesellschaft
|A method and a computer system for data assignment
|EP1622042A4 (en) *
|Hewlett Packard Development Co
|Database device, database search device, and method thereof
|US20060179067A1 (en) *
|Bechtel Michael E
|Knowledge discovery tool navigation
|US7882121B2 (en) *
|Microsoft Corporation
|Generating queries using cardinality constraints
|US7945559B2 (en) *
|Microsoft Corporation
|Completion of partially specified paths
|WO2008041242A4 (en) *
|Brainwave Applic Ltd
|A novel database
|CN101236549B (en)
|Method and system for obtaining attribute information content
|US20080222080A1 (en) *
|Nitrosecurity, Inc.
|Inferred index of circular tables in a database
|US7711716B2 (en) *
|Microsoft Corporation
|Optimizations for a background database consistency check
|US7814084B2 (en) *
|Schmap Inc.
|Contact information capture and link redirection
|US9501474B2 (en) *
|Oracle International Corporation
|Enhanced use of tags when storing relationship information of enterprise objects
|US8219581B2 (en) *
|Teradata Us, Inc.
|Method and system for analyzing ordered data using pattern matching in a relational database
|KR20110003947A (en) *
|Data processing apparatus and method
|CN102063434B (en)
|Candidate key capture device and candidate key capture method
|US8793288B2 (en) *
|Sap Ag
|Online access to database snapshots
|US20110153603A1 (en) *
|Yahoo! Inc.
|Time series storage for large-scale monitoring system
|EP2519897B1 (en) *
|Telecom Italia S.p.A.
|Method and system for carrying out searches in a database
|CN102117293B (en)
|Dynamic file positioning and query method
|JP5398007B2 (en) *
|Relationship information expansion device, relationship information expansion method, and program
|US9342314B2 (en)
|Oracle International Corporation
|Efficient hardware instructions for single instruction multiple data processors
|US9697174B2 (en)
|Oracle International Corporation
|Efficient hardware instructions for processing bit vectors for single instruction multiple data processors
|WO2013086384A1 (en)
|Oracle International Corporation
|Techniques for maintaining column vectors of relational data within volatile memory
|US9792117B2 (en)
|Oracle International Corporation
|Loading values from a value vector into subregisters of a single instruction multiple data register
|US9292569B2 (en)
|Oracle International Corporation
|Semi-join acceleration
|EP3182304A1 (en) *
|Pilab S.A.
|Computer-implemented method for storing unlimited amount of data as a mind map in relational database systems
|EP2843568A1 (en)
|Pilab S.A.
|Computer implemented method for creating database structures without knowledge on functioning of relational database system
|US9606921B2 (en)
|Oracle International Corporation
|Granular creation and refresh of columnar data
|US9773040B2 (en)
|Alan Weisman
|Search token mnemonic replacement
Citations (50)
|Publication number
|Priority date
|Publication date
|US3618027A (en)
|Research Corp
|Associative memory system with reduced redundancy of stored information
|US3670310A (en)
|Infodata Systems Inc
|Method for information storage and retrieval
|US4068300A (en)
|Honeywell Information Systems, Inc.
|Data processing system utilizing data field descriptors for processing data files
|US4128891A (en)
|International Business Machines Corporation
|Magnetic bubble domain relational data base system
|US4497039A (en)
|Fujitsu Limited
|Join operation processing system in relational model
|US4498145A (en)
|International Business Machines Corporation
|Method for assuring atomicity of multi-row update operations in a database system
|US4506326A (en)
|International Business Machines Corporation
|Apparatus and method for synthesizing a query for accessing a relational data base
|US4575798A (en)
|International Business Machines Corporation
|External sorting using key value distribution and range formation
|US4631664A (en)
|Bachman Information Systems, Inc.
|Partnership data base management system and method
|US4670848A (en)
|Standard Systems Corporation
|Artificial intelligence system
|US4774661A (en)
|American Telephone And Telegraph Company, At&T Information Systems
|Database management system with active data dictionary
|US4791561A (en)
|Wang Laboratories, Inc.
|Interactive construction of means for database maintenance
|US4807122A (en)
|Mitsubishi Denki Kabushiki Kaisha
|Information storage system
|US4829427A (en)
|Data General Corporation
|Database query code generation and optimization based on the cost of alternate access methods
|US4855908A (en)
|Fujitsu Limited
|POS system
|US4893232A (en)
|Kabushiki Kaisha Toshiba
|Data management system for efficiently searching data elements and having a flexible registration order of data elements
|US4901229A (en)
|Tsutomu Tashiro
|Parallelized rules processing system using associative memory for pipelined execution of plural join operations and concurrent condition comparing
|US4918593A (en)
|Wang Laboratories, Inc.
|Relational database system
|US4930072A (en)
|At&T Bell Laboratories
|Method for computing transitive closure
|US4930071A (en)
|Intellicorp, Inc.
|Method for integrating a knowledge-based system with an arbitrary database system
|US4933848A (en) *
|International Business Machines Corporation
|Method for enforcing referential constraints in a database management system
|US4947320A (en) *
|International Business Machines Corporation
|Method for referential constraint enforcement in a database management system
|US4967341A (en)
|Hitachi, Ltd.
|Method and apparatus for processing data base
|US5133068A (en)
|International Business Machines Corporation
|Complied objective referential constraints in a relational database having dual chain relationship descriptors linked in data record tables
|US5168565A (en)
|Ricoh Company, Ltd.
|Document retrieval system
|US5193183A (en)
|Bachman Information Systems, Inc.
|System for accessing design data of modeler subsystems by reference to partnership set and for dynamically correlating design data of modeler subsystems
|US5197005A (en)
|Intelligent Business Systems
|Database retrieval system having a natural language interface
|US5226158A (en) *
|International Business Machines Corporation
|Method and apparatus for maintaining referential integrity within a relational database
|US5239663A (en)
|Centre National De La Recherche Scientifique
|Self-adapting and multifunctional process and structure for the automated evaluation of logical or arithmetic expressions, particularly for extended database consultation
|US5247575A (en)
|Sprague Peter J
|Information distribution system
|US5262942A (en)
|Bankers Trust Company
|Financial transaction network
|US5297279A (en)
|Texas Instruments Incorporated
|System and method for database management supporting object-oriented programming
|US5369761A (en)
|Conley; John D.
|Automatic and transparent denormalization support, wherein denormalization is achieved through appending of fields to base relations of a normalized database
|US5379419A (en)
|Digital Equipment Corporation
|Methods and apparatus for accesssing non-relational data files using relational queries
|US5386559A (en) *
|International Business Machines Corporation
|Variant domains and variant maps in a versioned database management system
|US5386557A (en) *
|International Business Machines Corporation
|Enforcement of referential constraints in a database system
|US5408657A (en) *
|Unisys Corporation
|Method of imposing multi-object constraints on data files in a data processing system
|US5459860A (en)
|International Business Machines Corporation
|Computerized system and process for managing a distributed database system
|US5488722A (en) *
|International Business Machines Corporation
|System and method for automating implementation and execution of constraint most likely to be violated in a database
|US5504885A (en)
|Texas Instruments Incorporated
|O-R gateway: a system for connecting object-oriented application programs and relational databases
|US5539870A (en)
|International Business Machines Corporation
|Computerized system and process for interactively managing a distributed database system
|US5542073A (en)
|International Business Machines Corporation
|Computer program product for choosing largest selectivities among eligible predicates of join equivalence classes for query optimization
|US5548749A (en)
|Wall Data Incorporated
|Semantic orbject modeling system for creating relational database schemas
|US5581785A (en)
|Fuji Electric Co., Ltd.
|Starting system of disk storage device and data reading/writing system of the same
|US5664177A (en)
|Digital Equipment Corporation
|Data processing system having a data structure with a single, simple primitive
|US5826259A (en)
|Financial Systems Technology Pty. Ltd.
|Easily expandable data processing system and method
|US5893108A (en)
|International Business Machines Corporation
|System, method, and computer program product for efficiently translating relational tuples to object-oriented objects
|WO2000007354A1 (en)
|American Management Systems, Incorporated
|Decision network based event pricing system in a component based, object oriented convergent customer care and billing system
|US6105035A (en)
|Lucent Technologies, Inc.
|Method by which notions and constructs of an object oriented programming language can be implemented using a structured query language (SQL)
|WO2001015811A1 (en)
|Toshiba Carrier Corporation
|Air cleaner
Family Cites Families (1)
|Publication number
|Priority date
|Publication date
|US4918583A (en) *
|Nikon Corporation
|Illuminating optical device
Patent Citations (50)
|Publication number
|Priority date
|Publication date
|US3618027A (en)
|Research Corp
|Associative memory system with reduced redundancy of stored information
|US3670310A (en)
|Infodata Systems Inc
|Method for information storage and retrieval
|US4068300A (en)
|Honeywell Information Systems, Inc.
|Data processing system utilizing data field descriptors for processing data files
|US4128891A (en)
|International Business Machines Corporation
|Magnetic bubble domain relational data base system
|US4497039A (en)
|Fujitsu Limited
|Join operation processing system in relational model
|US4498145A (en)
|International Business Machines Corporation
|Method for assuring atomicity of multi-row update operations in a database system
|US4506326A (en)
|International Business Machines Corporation
|Apparatus and method for synthesizing a query for accessing a relational data base
|US4575798A (en)
|International Business Machines Corporation
|External sorting using key value distribution and range formation
|US4631664A (en)
|Bachman Information Systems, Inc.
|Partnership data base management system and method
|US4829427A (en)
|Data General Corporation
|Database query code generation and optimization based on the cost of alternate access methods
|US4855908A (en)
|Fujitsu Limited
|POS system
|US4901229A (en)
|Tsutomu Tashiro
|Parallelized rules processing system using associative memory for pipelined execution of plural join operations and concurrent condition comparing
|US4670848A (en)
|Standard Systems Corporation
|Artificial intelligence system
|US4807122A (en)
|Mitsubishi Denki Kabushiki Kaisha
|Information storage system
|US4774661A (en)
|American Telephone And Telegraph Company, At&T Information Systems
|Database management system with active data dictionary
|US4893232A (en)
|Kabushiki Kaisha Toshiba
|Data management system for efficiently searching data elements and having a flexible registration order of data elements
|US4967341A (en)
|Hitachi, Ltd.
|Method and apparatus for processing data base
|US4918593A (en)
|Wang Laboratories, Inc.
|Relational database system
|US4791561A (en)
|Wang Laboratories, Inc.
|Interactive construction of means for database maintenance
|US5239663A (en)
|Centre National De La Recherche Scientifique
|Self-adapting and multifunctional process and structure for the automated evaluation of logical or arithmetic expressions, particularly for extended database consultation
|US4930071A (en)
|Intellicorp, Inc.
|Method for integrating a knowledge-based system with an arbitrary database system
|US4930072A (en)
|At&T Bell Laboratories
|Method for computing transitive closure
|US5168565A (en)
|Ricoh Company, Ltd.
|Document retrieval system
|US5664177A (en)
|Digital Equipment Corporation
|Data processing system having a data structure with a single, simple primitive
|US4947320A (en) *
|International Business Machines Corporation
|Method for referential constraint enforcement in a database management system
|US4933848A (en) *
|International Business Machines Corporation
|Method for enforcing referential constraints in a database management system
|US5247575A (en)
|Sprague Peter J
|Information distribution system
|US5133068A (en)
|International Business Machines Corporation
|Complied objective referential constraints in a relational database having dual chain relationship descriptors linked in data record tables
|US5197005A (en)
|Intelligent Business Systems
|Database retrieval system having a natural language interface
|US5226158A (en) *
|International Business Machines Corporation
|Method and apparatus for maintaining referential integrity within a relational database
|US5386557A (en) *
|International Business Machines Corporation
|Enforcement of referential constraints in a database system
|US5369761A (en)
|Conley; John D.
|Automatic and transparent denormalization support, wherein denormalization is achieved through appending of fields to base relations of a normalized database
|US5193183A (en)
|Bachman Information Systems, Inc.
|System for accessing design data of modeler subsystems by reference to partnership set and for dynamically correlating design data of modeler subsystems
|US5826259A (en)
|Financial Systems Technology Pty. Ltd.
|Easily expandable data processing system and method
|US5297279A (en)
|Texas Instruments Incorporated
|System and method for database management supporting object-oriented programming
|US5262942A (en)
|Bankers Trust Company
|Financial transaction network
|US5379419A (en)
|Digital Equipment Corporation
|Methods and apparatus for accesssing non-relational data files using relational queries
|US5408657A (en) *
|Unisys Corporation
|Method of imposing multi-object constraints on data files in a data processing system
|US5386559A (en) *
|International Business Machines Corporation
|Variant domains and variant maps in a versioned database management system
|US5459860A (en)
|International Business Machines Corporation
|Computerized system and process for managing a distributed database system
|US5539870A (en)
|International Business Machines Corporation
|Computerized system and process for interactively managing a distributed database system
|US5542073A (en)
|International Business Machines Corporation
|Computer program product for choosing largest selectivities among eligible predicates of join equivalence classes for query optimization
|US5488722A (en) *
|International Business Machines Corporation
|System and method for automating implementation and execution of constraint most likely to be violated in a database
|US5504885A (en)
|Texas Instruments Incorporated
|O-R gateway: a system for connecting object-oriented application programs and relational databases
|US5581785A (en)
|Fuji Electric Co., Ltd.
|Starting system of disk storage device and data reading/writing system of the same
|US5548749A (en)
|Wall Data Incorporated
|Semantic orbject modeling system for creating relational database schemas
|US5893108A (en)
|International Business Machines Corporation
|System, method, and computer program product for efficiently translating relational tuples to object-oriented objects
|US6105035A (en)
|Lucent Technologies, Inc.
|Method by which notions and constructs of an object oriented programming language can be implemented using a structured query language (SQL)
|WO2000007354A1 (en)
|American Management Systems, Incorporated
|Decision network based event pricing system in a component based, object oriented convergent customer care and billing system
|WO2001015811A1 (en)
|Toshiba Carrier Corporation
|Air cleaner
Non-Patent Citations (77)
|"Extended Disjunctive Normal Form for Efficient Processing of Recursive Logic Queries", IBM Technical Disclosure Bulletin, vol. 30, No. 1, Jun. 1987 pp. 360-366.
|"The Smart Card's Chief Advocate", Credit Card Management, vol. 10, No. 1, p. 26+, ISBN: 0896-9329, 1992.
|Adiba et al., "Database Snapshots", Proceedings of the 1980 International Conference on Very Large Data Bases, IEEE 1980, pp. 86-91.
|Annevelink et al., "Object SQL-A Language for the Design and Implementation of Object Databases", Jan. 3, 1994, pp. 1-21.
|Ashok Malhotra, Yakov Tsalalikhin, Donald P. Pazel, Luanne M. Burns and Harry M. Markowitz, Implementing an Entity-Relationship Language on a Relational Data Base, IBM Research Report RC 12134 (#54499) (Aug. 27, 1986) ("Malhotra").
|Banerjee et al., "Data Model Issues for Object-Oriented Applications", ACM Transactions on Office Information Systems, vol. 5, No. 1, Jan. 1987, pp. 3-26.
|Bharadwaj et al., Determinants of success in service industries: a PIMS-based empirical investigation, Journal of Service Marketing, v7n4, pp. 19-40, 1993, 23 pages from Dialog file 15, acc. # 00813287.
|Blaha et al., "Relational Database Design using an Object-Oriented Methodology", Communications of the ACM, Apr. 1988, vol. 31, No. 4, pp. 414-427.
|Blakeley et al., "Experiences Building the Open OODB Query Optimizer", 1993, pp. 287-296.
|Blakeley et al., "Join Index, Materialized View, and Hybrid-Hash Join: A Performance Analysis", Technical Report No. 280, Indiana University Computer Science Department, IEEE 1990, pp. 256-263.
|Blakely et al., "Experience Buildig the Open OODB Query Optimizer", 1993, pp. 287-296.
|Cattell, R. and Rogers, T., "Combining Object-Oriented and Relational Models of Data", 1986 International Workshop on Sep. 26, 1986, pp. 212-213.
|Chen, P., "Entity-Relationship Approach to Information Modeling and Analysis", International Conference in Washington, D.C., Oct. 12-14. 1981, pp. 49-72.
|Chen, Peter, "Entity-Relationship Approach to Systems Analysis and Design", Proceedings of the International Conference in Los Angeles, Dec. 10-12, 1979, pp. 237-257.
|Codd, E., "Extending the Database Relational Model to Capture More Meaning", ACM Transactions on Database Systems, vol. 4, No. 4, Dec. 1979, pp. 397-434.
|Curran, T. "EE221-Database Systems & Software Analysis and Design", course notes, Dublin City University, School of Electronic Engineering, downloaded from www.eeng.dcu.ie/-ee221/EE221-DB-2.pdf, 2007. *
|Daniel R. Dolk, et. al., A Relational Information Resource Dictionary System, Computing Practices, Communications of the ADM (Jan. 1987).
|Dewan et al. "Engineering the Object-Relation Database Model in O-Raid", Lecture Notes in Computer Science, 3<SUP>rd </SUP>International Conference-Paris, Jun. 21-23, 1989, pp. 389-403.
|Elmasri et al., "Fundamentals Of Database Systems", 1989.
|El-Sharkawi et al, "The Architecture and Implementation of Enli: An Example-Based Natural Language Assisted Interface", Parbase 90 Intl. Conf. on Databases, Parallel Architectures & Their Applications, Mar. 7-9 1990.
|Finkelstein et al., "Physical Database Design for Relational Databases", ACM Transactions on Database Systems, vol. 13, No. 1, Mar. 1988, pp. 91-128.
|Fishman et al., "Overview of the Iris DBMS", Association for Computing Machinery, Inc., pp. 219-250.
|Gamache et al., "Addressing Techniques Used in Database Object managers O<SUB>2 </SUB>and Orion", SIGMOD Record, vol. 24, No. 3, Sep. 1995, pp. 50-55.
|Gio Wiederhold, "Database Design Second Edition", Discloses Definition Tables, Sections 7-3-1, 7-3-7, 7-4-4, 7-4-5, and 9-7-6 and Figs. 8-5, 8-7, 8-9 (1995).
|Hainaut, J. L., "Theoretical And Practical Tools For Data Base Design", Proceedings of the Seventh International Conference on Very Large Data Bases, IEEE 1981, pp. 215-224.
|Halper et al., "An OODB "Part" Relationship Model", 10 pages.
|Hanks, D.R., "The Payoff of Modest Price Adjustments," (Abstract only), Bank Marketing, vol. 12, No. 9, p. 13,, Sep. 1980.
|Hendler, James A. Expert Systems: The User Interface. Albex Publishing Corporation. Norwood, NJ. 1988. pp. 31, 46-47, 109-110, 113 and 132-134.
|Howcroft, "Contemporary issues in UK bank delivery systems", Inter. Jour. of Service Industry Management, vol. 3, No. 1, pp. 39-56, ISBN 096-4223, 1992.
|Hudson et al., "Cactis: A Self-Adaptive, Concurrent Implementation of an Object-Oriented Database Management System", ACM Transactions on Database Systems, vol. 14, No. 3, Sep. 1989, pp. 291-321.
|Hull et al., "Semantic Database Modeling: Survey, Applications, and Research Issues", ACM Computing Survey, vol. 19, No. 3, Sep. 1987, pp. 201-260.
|Introduction to NonStop SQL, Tandem Computers, May 1988, pp. I-3-19.
|Khoshaflan, S. and Copeland, G., "Object Identity", Microelectronics and Computer Technology Corporation, pp. 37-46.
|Kifer et al, "Sygraf: Implementing Logic Programs in a Database Style" IEEE Transactions on Software Engnrn. v:14, N7, Jul. 1988 pp. 92-935.
|Kim et al., "Architecture of the Orion Next-Generation Database System", IEEE, 1990, pp. 109-124.
|Kim et al., "Composite Object Support in an Object-Oriented Database System", OOPSLA '87 Proceedings, Oct. 4-8, 1987, pp. 118-125.
|Kim et al., "Evaluation of the Object-relational DBMS Postgres .I. Administrative Data", Computing Science, Oct. 1994, pp. 1-52.
|Kim et al., "Features of the ORION Object-Oriented Database System", pp. 251-282.
|Kim et al., "Semantics and Implementation of Schema Evolution in Object-Oriented Databases", 1987, pp. 311-322.
|Klimbie et al., "Data Base Management", North-Holland Publishing Company, 1974, pp. 1-59.
|Korth and Silberschatz, Database System Concepts, McGraw-Hill Book Company (New York, 1986), pp. 45-105; pp. 301-323.
|M.M. Zloof, Query-by-Example: A Data Base Language, IBM Systems Journal, No. 4 (1977).
|Mark et al., "Metadata Management", Computer Database Architecture, Dec. 1986, pp. 26-36.
|Mark L. Gillenson, Database Step-by-step 141-42, 2d Ed. (1990).
|Markowitz et al., "Representing Extended Entity-Relationship Structures in Relational Databases: A Modular Approach", ACM Transactions on Office Information Systems, vol. 17, No. 3, Sep. 1992, pp. 423-464.
|Microsoft "Microsoft Press Computer Dictionary, Third Edition", Redmond:Microsoft Press, pp. 403-404, 1997. ISBN 1-57231-446-X, QA76.15.M54 1997. *
|Microsoft Corporation, "Relational Database Components", tutorial, downloaded from msdn.microsoft.com/en-us/library/aa174501(SQL.80).aspx, 2007. *
|Munz, R. "Design of the Well System", in Entity-Relationship Approach to Systems Analysis and Design, Proceedings of the 1<SUP>st </SUP>International Conference on the Entity-Relationship Approach, Chen, P. ed., 1979, pp. 502-522. *
|Munz, R. "The Well System: A Multi-User Database System Based on Binary Relationships and Graph-Pattern-Matching", Information Systems, vol. 3, 1978, pp. 99-115. *
|Nixon et al., "Implementation of a Compiler for a Semantic Data Model: Experiences with Taxis", 1987, pp. 118-131.
|Osborn et al., "The Design of a relational Database System with Abstract Data Types for Domains", ACM Transactions on Database Systems, vol. 11, No. 3, Sep. 1986, pp. 357-373.
|Parsaye, Kamran & Chignell, Mark. Expert Systems For Experts. John Wiley & Sons. 1988. pp. 35-60, 177-178, 191-210 and 295-309.
|Peckham et al., "Semantic Data Models", Acm Computing Surveys, vol. 20, No. 3, Sep. 1988, pp. 153-189.
|Pin-Shan Chen, The entity-relationship model-A basis for the enterprise view of data 77 (1977).
|Rose, Peter S., et al. Financial Institution, Understanding and Managing Financial Services, 4th Edition, Richard D. Irwin, Inc., 1993. pp. 1-217; 328-356; 423-446; 654-792.
|Rowe, L. and Stonebraker, M. "The POSTGRES Data Model", Computer Science Division, EECS Department, University of California, pp. 1-21.
|Rudolph Munz, "Das WEB-Modell" (English translated pages), Chapter 10 (1976), 18 pages.
|Rudolph Munz, "Das WEB-Modell" (translated pages), pp. 155-156, Fig. 10.2.1, (1976). ("Munz 111"), with English translation. Document Provided Doesn't Match.
|Rumbaugh, J., "Relations as Semantic Constructs in an Object-Oriented Language", OOPSLA '87 Proceedings, Oct. 4-8, 1987, pp. 466-481.
|Rybinski, H. "On First-Order-Logic Databases", ACM Transactions on Database Systems (TODS), vol. 12, No. 3, Sep. 1997, pp. 325-349. *
|Stonebraker, M. and J.M. Hellerstein "What Goes Around Comes Around", in Readings in Database Systems 4<SUP>th </SUP>Edition, Caimbridge:MIT Press, Jan. 2005, ISBN 0-262-69314-3. *
|Stonebraker, M. and Moore, D., "Object-Relational DBMSs The Next Great Wave", Morgan Kaufman Publishers, Inc., 1996, pp. 56-61.
|Straube et al., "Queries and Query Processing in Object-Oriented Database Systems", ACM Transactions on Information Systems, vol. 8, No. 4, Oct. 1990, pp. 387-430.
|Stuchfield, N., et al., "Modeling of Profitability of Customer Relationships: Development and Impact of Barclays de Zoete Wedd's Beatrice," Journal of Management Information Systems, vol. 9, No. 2, p. 53, Fall 1992.
|Takahashi, J., "Hybrid Relations for Database Schema Evolution", IEEE, 1990, pp. 465-470.
|Teorey et al., "A Logical Design Methodology for Relational Databases Using the Extended Entity-Relationship Model", Computing Surveys, vol. 18, No. 2, Jun. 1986, pp. 197-222.
|The IBM Dictionary of Computing Terms (8th Ed. 1987), p. 107.
|Tsichritzis, D. "LSL: A Link and Selector Language", Proceedings of the ACM-SIGMOD International Conference on Management of Data, Jun. 2-4, 1976, pp. 123-133. *
|Tsurt et al., "An Implementation of GEM-supporting a semantic data model on a relational back-end.", 1984, pp. 286-295.
|Webster's New World Dictionary of Computer Terms (3d Ed. 1988), pp. 87-88.
|Whang et al., "Query Optimization in a Memory-Resident Domain Relational Calculus Database System", ACM Transactions on Database Systems, vol. 15, No. 1, Mar. 1990, pp. 67-95.
|Wiederhold, G., "Database Design Appendix B", McGraw-Hill, 2001, pp. 689-698.
|Wiederhold, G., "Views, Objects, and Databases" Computer Database Architecture, Dec. 1986, pp. 37-44.
|Wilkinson et al., "The Iris Architecture and Implementation", IEEE Transactions on Knowledge and Data Engineering, vol. 2, No. 1, Mar. 1990, 27 pages.
|Wilschut et al, "Pipelining in Query Execution" Parbase-90 Intl. Conf. on Databases, Parallel Architectures and Their Applications, Mar. 7-9, 1990 p. 562.
|Yu et al, "Automatic Knowledge Acquisition and Maintenance For Semantic Query Optimization", IEEE Transactions on Knowledge and Data Engrn, V:1, No. 3 Sep. 1989, pp. 362-375.
|Zand et al., "A Survey of Current Object-Oriented Databases", Data Base Advances, Feb. 1995, vol. 26, No. 1, pp. 14-29.
Also Published As
|Publication number
|Publication date
|US5826259A (en)
|USRE40520E1 (en)
|US5652882A (en)
|USRE40235E1 (en)
|USRE40063E1 (en)
|US5617567A (en)
|US5604899A (en)
|US5675779A (en)
Similar Documents
|Publication Date
|Tsichritzis et al.
|Hierarchical data-base management: A survey
|Join indices
|Wu et al.
|Research issues in data warehousing
|Subramanian et al.
|Performance challenges in object-relational DBMSs
|US5898872A (en)
|Software reconfiguration engine
|US6598038B1 (en)
|Workload reduction mechanism for index tuning
|US5761654A (en)
|Memory structure and method for tuning a database statement using a join-tree data structure representation, including selectivity factors, of a master table and detail table
|US6453314B1 (en)
|System and method for selective incremental deferred constraint processing after bulk loading data
|US6058392A (en)
|Method for the organizational indexing, storage, and retrieval of data according to data pattern signatures
|US6112209A (en)
|Associative database model for electronic-based informational assemblies
|US6598059B1 (en)
|System and method of identifying and resolving conflicts among versions of a database table
|US5913214A (en)
|Data extraction from world wide web pages
|US6658437B1 (en)
|System and method for data space allocation using optimized bit representation
|US7603345B2 (en)
|Detecting spam documents in a phrase based information retrieval system
|US7702618B1 (en)
|Information retrieval system for archiving multiple document versions
|Cui et al.
|Tracing the lineage of view data in a warehousing environment
|US5819282A (en)
|Database generator
|US5499358A (en)
|Method for storing a database in extended attributes of a file system
|US7567959B2 (en)
|Multiple index based information retrieval system
|US6035303A (en)
|Object management system for digital libraries
|Pfaltz et al.
|Partial-match retrieval using indexed descriptor files
|US5450581A (en)
|System for copying from one database management system to another by translating authorization statements
|US6339769B1 (en)
|Query optimization by transparently altering properties of relational tables using materialized views
|US6366902B1 (en)
|Using an epoch number to optimize access with rowid columns and direct row access
|US5604901A (en)
|Interrogation index file comparison
Legal Events
|Aia trial proceeding filed before the patent and appeal board: inter partes review
Free format text: TRIAL NO: IPR2013-00078
Opponent name: INTERNATIONAL BUSINESS MACHINES CORPORATION
Effective date: 20121212