Client/server database system with methods for providing clients with server-based bi-directional scrolling at the server

• US 5,918,224 A
• Filed: 07/26/1995
• Issued: 06/29/1999
• Est. Priority Date: 07/26/1995
• Status: Expired due to Term

• Current Assignee: CodeGear (Idera, Inc.)
• Original Assignee: Borland International, Inc. (Open Text Corporation)
• Inventors: Bredenberg, David
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Corrielus, Jean M.
• Application Number:
  US08/506,944
• Time in Patent Office: 1,434 Days
• Field of Search: 395/614, 395/602, 395/601, 395/603, 395/608, 395/495, 395/616, 395/610, 707/8, 707/2, 707/202, 707/1, 707/200, 707/10, 707/103
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

System and methods are described for integrating the navigational semantic model of PC DBMS environments into the set-oriented model of SQL database environments. More particularly, a Client/Server system of the present invention provides native navigational support on the Server side, without emulation through a multitude of SQL commands from the Client. The Database Server surfaces to the Client an API (Application Programming Interface) having calls corresponding to each verb taken from a navigational context. The Server, in turn, is modified to include knowledge of how to process each navigational verb. To support this functionality, the indexing of the Server is modified to provide bi-directional scrolling. In this manner, the system is able to provide more efficient, higher performance navigational support in an SQL database context.

Claims

1. In a client/server database system, the system including a database server storing a relational database table, the database server in communication with a plurality of clients and transmitting to those clients sets of data records meeting client-specified query conditions, a method for providing the clients with server-based bi-directional scrolling support provided at the database server such that clients can maintain a bi-directional scrollable cursor for such data records without having to emulate such a cursor with multiple query commands, the method comprising:

(a) creating at the database server a plurality of verbs for bi-directional scrolling of the database table, each verb corresponding to a command which a client issues for requesting bi-directional scrolling of the database table at the server;

(b) creating at the database server an index for accessing the database table, said index including an ordered set of leaf pages for accessing the database table according to a particular sort order;

(c) modifying said leaf pages of the index to support bi-directional scrolling by multiple concurrent clients, said modifying step supporting bi-directional traversing among said leaf pages;

(d) receiving a database query including a request from a client to open a cursor at the database table, said database query including a command for bi-directional scrolling of the database table such that the client can scroll the cursor bidirectionally at the database table; and

(e) in response to receiving said request, performing bi-directional scrolling at the database server by traversing in a bi-directional manner said modified index;

wherein step (a) includes creating at the database server a plurality of verbs by providing a handler at the database server for each of said verbs, each handler executing at the database server in response to receipt of a particular command from a client for providing the client with bi-directional scrolling of the cursor at the database server.

2. The method of claim 1, wherein said verbs include selected ones of seek, find, and skip, which are performed at the database server in a bi-directional manner.

3. The method of claim 1, wherein each said handler comprises steps executed at the database server for traversing said index in a bi-directional manner.

4. In a client/server database system, the system including a database server storing a relational database table, the database server in communication with a plurality of clients and transmitting to those clients sets of data records meeting client-specified query conditions, a method for providing the clients with server-based bi-directional scrolling support provided at the database server such that clients can maintain a bi-directional scrollable cursor for such data records without having to emulate such a cursor with multiple query commands, the method comprising:

(a) creating at the database server a plurality of verbs for bi-directional scrolling of the database table, each verb corresponding to a command which a client issues for requesting bi-directional scrolling of the database table at the server;

(b) creating at the database server an index for accessing the database table, said index including an ordered set of leaf pages for accessing the database table according to a particular sort order;

(c) modifying said leaf pages of the index to support bi-directional scrolling by multiple concurrent clients, said modifying step supporting bi-directional traversing among said leaf pages;

(d) receiving a database query including a request from a client to open a cursor at the database table, said database query including a command for bi-directional scrolling of the database table such that the client can scroll the cursor bidirectionally at the database table; and

(e) in response to receiving said request, performing bi-directional scrolling at the database server by traversing in a bi-directional manner said modified index;

wherein step (c) includes modifying each leaf page to provide forward and backward page pointers, so that a previous page and a next page can be determined for a current leaf page;

wherein said bi-directional traversing of the modified index includes when traversing in a backward direction, releasing the current leaf page before locking the previous page; and

wherein said bi-directional traversing of the modified index further includes;

comparing the previous page with a previous page pointer stored by said current page; and

if said previous page does not match said previous page pointer, traversing in a forward direction until a page is found which stores a next page pointer which matches said current leaf page.

5. The method of claim 4, wherein step (c) includes:

modifying each leaf page to provide forward and backward page pointers, so that a previous page and a next page can be determined for a current leaf page.

6. The method of claim 5, wherein said bi-directional traversing of the modified index includes:

when traversing in a forward direction, locking the next page before releasing the current leaf page.

7. The method of claim 5, wherein said bi-directional traversing of the modified index includes:

when traversing in a backward direction, releasing the current leaf page before locking the previous page.

8. The method of claim 4, further comprising:

updating the previous page pointer of said current leaf page to point to the page found which stores a next page pointer matching said current leaf page.

9. The method of claim 4, wherein said request of step (d) includes a request to scroll backward in the database table, and wherein said bi-directional traversing of the index in step (e) includes traversing said index in a backward direction.

10. An improved client/server database system, said system including a database server connected to a plurality of clients, said database server storing a database table having an index, the improvement comprising:

means, operably coupled to the database server, for processing commands from the client for bidirectional navigation of the database table; and

means, operably coupled to said means for processing commands, for bi-directional traversing said index at the database server, said means including means for bi-directional traversing of leaf pages of said index, such that when traversing the index in a forward direction the database server locks the next page before releasing a current leaf page and when traversing the index in a backward direction, the database server releases the current leaf page before locking the previous page;

wherein said means for processing commands includes handler means for processing selected ones of a seek command, a find command, and a skip command, for seeking, finding, and skipping records in a bi-directional manner, respectively; and

wherein said database server is connected to said clients through a computer network, and wherein said handler means operates at the database server.

11. The system of claim 10, further comprising:

concurrency means for providing shared access to the index during bi-directional traversing of the index.

12. The system of claim 11, wherein said index comprises a plurality of index pages and wherein said concurrency means includes:

means for locking a next page of the index before releasing a current page, when traversing the index in a forward direction.

13. The system of claim 11, wherein said index comprises a plurality of index pages and wherein said concurrency means includes:

means for releasing a current page before locking a previous of the index, when traversing the index in a backward direction.

14. The system of claim 13, wherein each page stores a forward pointer pointing to a next page and a backward pointer pointing to a previous page and wherein said concurrency means includes:

means for traversing said index in a backward direction based on the previous pointer stored by the current index page followed by traversing said index in a forward direction until a page is found which stores a forward page pointer matching the current page.

15. In a SQL-based database server system, a method for bi-directional traversing of leaf pages for an index which comprises a B-tree having a plurality of such leaf pages, the method comprising:

(a) for each leaf page, storing a forward pointer pointing to a next page and a backward pointer pointing to a previous page;

(b) when traversing in a forward direction from a current page of the index, locking the next page from the current page and thereafter releasing the current page; and

(c) when traversing in a backward direction from the current page of the index, releasing the current page and thereafter locking the previous page, wherein the previous page is located by;

(i) referencing the backward pointer of the current page;

(ii) comparing the forward pointer for the page pointed to by the backward pointer of the current page with an identifier for the current page; and

(iii) if the forward pointer for the page pointed to by the backward pointer of the current page does not match the identifier for the current page, traversing the index in a forward direction until a page is found having a forward pointer matching the identifier for the current page.

16. The method of claim 15, wherein step (b) further comprises:

locating the next page by referencing the forward pointer stored by the current page.

17. The method of claim 15, wherein each leaf page stores a plurality of index nodes, each node storing a key value for a particular data record together with a pointer to that particular data record.

18. The method of claim 17, wherein each key value is stored in a prefix-compressed format.

19. The method of claim 18, further comprising traversing in a backward direction within a particular leaf page by:

(i) expanding said particular leaf page into an expanded leaf page storing uncompressed key values for each node;

(ii) storing at each node a length for the key value stored thereat; and

(iii) traversing to a previous node by navigating to a location within the expanded index page, said location being determined from the length of the key value stored at a current node.