Method and apparatus for routing data in an automatic identification system

Abstract

A system for routing data in an automatic identification system includes an event management system (EMS), a real-time in-memory data structure (RIED) coupled to the EMS, the RIED for storing event information gathered by the EMS and a task management system (TMS) for ensuring that the RIED is updated by one transaction at a time. With this particular arrangement, a system for managing a large number of real-time events is provided. In one embodiment, the control system can be provided in a distributed hierarchical arrangement. The EMS of each control system can include filters which limit the amount of information provided to the next level in the hierarchy. In this manner the hierarchical control system network acts as a high volume data collector and processor. In some embodiments a level of the hierarchy can be removed spatially and/or temporally from an adjacent level in the hierarchy. This approach results in an intelligent network and also lends itself to scalability. By including optional filters and queues in the EMS, the EMS can be configured as desired.

1 . A method of processing and storing data in a distributed control system comprising the steps of: 
 a. Maintaining a first persistent datum;    b. Forwarding data received from a data reader to an edge control system;    c. Processing the data at the edge control system;    d. Forwarding the data from the edge control system to at least one second-level control system;    e. Forwarding data from a second edge control system to at least one second-level control system; and    f. Processing data at the at least one second-level control system that was received from at least two edge control systems.    
   
   
       2 . The method of  claim 1 , further comprising the step wherein event data readers communicate with the edge control system through an adapter.  
   
   
       3 . The method of  claim 2  wherein said adapter sends information to the edge control system through a filter.  
   
   
       4 . The method of  claim 3 , further comprising storing information in an event logger.  
   
   
       5 . The method of  claim 4 , further comprising a step of providing a queuing system that records events read by at least one reader adapter, and posting the recorded events to all of the event loggers registered with the system.  
   
   
       6 . The method of  claim 1 , further comprising the step of saving a snapshot of a database.  
   
   
       7 . A method of processing and storing real time data in a control system comprising the steps of: 
 a. Maintaining a versioned database;    b. Saving snapshots of a database;    c. Maintaining a current sequence number and corresponding data item;    d. Maintaining a sequence manager that stores sequence numbers associated with each snapshot in a sequence manager table; and    e. Maintaining said first persistent datum so that said datum comprises a first row containing sequence numbers and a second row containing data.    
   
   
       8 . The method of  claim 7 , further comprising the step of storing a first hash table having a first column containing a primary key and a second column containing data that corresponds to said key.  
   
   
       9 . The method of  claim 8 , wherein the primary key corresponds to an electronic product code (EPC) tag number, and the data corresponds to Object Name Service (ONS) data relevant for the given EPC tag number.  
   
   
       10 . The method of  claim 8 , wherein the primary key corresponds to an EPC tag number, and the data corresponds to Physical Markup Language (PML) data for that EPC number.  
   
   
       11 . The method of  claim 8 , further comprising storing a second hash table containing a first column having data and a second column containing at least one key that corresponds to said data.  
   
   
       12 . The method of  claim 11 , wherein the said data corresponds to Object Name Service (ONS) data relevant to a particular EPC tag number, and the primary key corresponds to said EPC tag number.  
   
   
       13 . The method of  claim 11 , wherein the said data corresponds to Physical Markup Language (PML) data relevant to a particular EPC tag number, and the primary key correspond to said EPC tag number.  
   
   
       14 . The method of  claim 7 , further comprising the step of adding a new sequence number and corresponding data item to the persistent datum.  
   
   
       15 . The method of  claim 7 , further comprising the step of deleting an existent sequence number and corresponding data item in the persistent datum.  
   
   
       16 . The method of  claim 7 , further comprising the step of assigning a snapshot name to a snapshot.  
   
   
       17 . The method of  claim 16 , wherein the sequence manager maintains the snapshot name and the sequence number in a table.  
   
   
       18 . The method of  claim 16 , further comprising the step of updating the sequence by appending a new snapshot name and sequence number to the table.  
   
   
       19 . The method of  claim 7 , further comprising the step of synchronizing a snapshot, wherein the sequence manager updates the latest snapshot entry with the current sequence number.  
   
   
       20 . The method of  claim 7 , further comprising an update operation; said update operation comprises the following steps: 
 a. Determining the value of a n th  lowest sequence number;    b. Storing the value of the n th  lowest sequence number from the sequence manager table; where n initially equals 1;    c. Reading the sequence numbers stored in the first persistent datum at the sequence number read from the sequence manager;    d. Locating and moving the n th  lowest sequence number and data item pair to an updated persistent datum, if a sequence number exists in the persistent datum that equals the persistent datum in the sequence manager;    e. Storing the n th +1 lowest sequence number from the sequence manager in memory and determining whether there is a corresponding sequence number in the first persistent datum; 
 i. Moving the sequence number and data item pair to the updated persistent datum, if a sequence number in the first persistent datum is equal to the n th +1 lowest sequence number in the sequence manager;  
 ii. Locating a lower sequence number that exists in the first persistent datum that has not already been moved to the updated persistent datum and moving the sequence number and data item pair to the updated persistent datum, if no sequence number in the first persistent datum is equal to the n th +1 lowest sequence number in the sequence manager; and  
 iii. Deleting any sequence number and data item pairs that are less than the n th +1 lowest sequence number in the sequence manager but greater than the n th  lowest sequence number.  
   
   
   
       21 . The method of  claim 20 , wherein the update operation further comprises: 
 e. Setting n=n+1 and repeating step e.    
   
   
       22 . The method of  claim 20 , wherein step e is repeated until n>x, wherein x equals the number of snapshots in the sequence manager.  
   
   
       23 . The method of  claim 20 , further comprising the step of storing the current sequence number and corresponding data item in the updated persistent datum.  
   
   
       24 . The method of  claim 21 , wherein the update operation constructs an updated persistent datum that stores the sequences in descending order.  
   
   
       25 . A method of querying real time data in a control system comprising the steps of: 
 a. Maintaining a first persistent datum;    b. Saving at least one snapshot of data;    c. Maintaining at least one snapshot name for each said snapshot;    d. Maintaining a current sequence number;    e. Maintaining a sequence manager that stores sequence numbers associated with each snapshot in a sequence manager table; and    f. Maintaining said first persistent datum so that said first persistent datum comprises a first row maintaining sequence numbers and a second row maintaining data items.    
   
   
       26 . The method of  claim 25 , further comprising the step of adding a data item to said first persistent datum.  
   
   
       27 . The method of  claim 25 , further comprising the step of subtracting a data item from said first persistent datum.  
   
   
       28 . The method of  claim 25 , further comprising the step of processing a query; said step of processing the query comprises the following steps: 
 a. Reading the snapshot names and sequence number from the m th  row of the table, where m is initially set to 1;    b. Scanning the first persistent datum for the n th  highest sequence number from the persistent datum that is less than or equal to the sequence number from the sequence manager table, where n is initially set to 1; 
 i. Adding the data item associated with the n th  highest sequence number to a memory, if the data item specifies an addition operation;  
 ii. Subtracting the data item associated with the n th  highest sequence number from the memory, if the data item specifies a subtraction operation;  
   c. Setting n=n+1;    d. Repeating steps b and c until all the sequence numbers from the persistent datum that are less than or equal to the sequence number from the sequence manager have been scanned and the appropriate addition or subtraction operation has been performed to memory;    e. After step d is completed, restoring n=1 and setting m=m+1; and    f. Performing steps a-e, until m>than the number of rows stored in the sequence manager.    
   
   
       29 . The method of  claim 28 , further comprising the step of creating a table comprising a row of snapshots and the data stored in memory that corresponds to each snapshot.  
   
   
       30 . The method of  claim 29 , wherein the table additionally comprises the sequence number.  
   
   
       31 . The method of  claim 25 , wherein the sequence numbers in the first persistent datum are stored in descending or ascending order.  
   
   
       32 . The method of  claim 26 , further comprising the step of deleting invalid data items comprising the following steps: 
 a. Scanning the first persistent datum for a set of two adjacent operations that specify the addition and subtraction of the same value; and    b. Deleting the sequence numbers and corresponding data items, if the sequence manager does not contain a snapshot name specifying a sequence number that is equal to the higher of the two adjacent sequence numbers.