Platform for processing semi-structured self-describing data

• US 7,519,948 B1
• Filed: 12/22/2003
• Issued: 04/14/2009
• Est. Priority Date: 12/26/2002
• Status: Expired due to Fees

• Current Assignee: Judson Ames Cornish
• Original Assignee: Judson Ames Cornish
• Inventors: Cornish, Judson Ames
• Primary Examiner(s): Dam; Tuan Q
• Assistant Examiner(s): DAO, THUY CHAN
• Application Number:
  US10/743,953
• Time in Patent Office: 1,940 Days
• Field of Search: None
• US Class Current: 717/117
• CPC Class Codes: G06F 16/83 Querying
• CPC Class Codes: G06F 8/00 Arrangements for software engineering testing or debugging G06F11/36; administrative, planning or organisation aspects of software project management G06Q10/06
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

An Extensible Markup Language (XML) Application Server for storing, processing, communicating, and displaying dynamic semi-structured information. It comprises a declarative specification language, a transactional indexed XML data store, and an XML application server engine. An integrated architecture (a) provides for optimization, indexing, and backtracking search in a business logic layer, (b) provides for general-purpose programming idioms including recursive function definitions, iteration, and dynamic dispatch in data layer queries and updates, and (c) eliminates processing overhead and maintenance issues caused by transforming between relational, object-oriented, and semi-structured data paradigms.

Claims

1. A method of specifying, generating, and running a data processing system, comprising:

(a) providing a plurality of predicates, each referring to a set of arguments,

(b) providing a plurality of specifications, each of which defines valid argument values for said predicates, and refers to;

i. a set of variables, and

ii. a set of clauses,

(c) specifying some clauses of said specifications by referring to one of said predicates, and to variables of the specification to specify values for arguments of the predicate,

(d) providing a plurality of plans, which are able to be run to generate sets of valid argument values for said predicates,

(e) providing a planning means which is able to generate said plans from said specifications,

(f) providing an evaluation means which is able to run said plans to generate sets of valid argument values,

(g) generating multiple sets of valid variables for some component steps of some plans, and testing said sets of valid variables for combinations which generate said valid argument values as results,

(h) providing an input means which is able to provide input data values for a set of the arguments of one of said predicates,

(i) providing an output means which is able to output data,

(j) inputting argument values from said input means, evaluating input argument values to generate output argument values using said evaluation means, and outputting argument values using said output means,

(k) wherein some of said plans refer to an ordering of the clauses of one of said specifications,

(l) wherein said evaluation means further;

i. runs said plans by evaluating each clause in the order specified, using variable values generated by earlier clauses as input to later clauses, and by recursively selecting and running plans for clauses which are specified by predicates,

ii. generates valid variables by backtracking and re-evaluating an antecedent clause to generate alternate sets of variable values when a subsequent clause fails to evaluate successfully using the original set of variable values;

(m) wherein said planning means comprises;

i. selecting which clauses of said specification will generate which variable values, by first selecting clauses which generate the minimum number of different values, whereby other clauses will be less frequently re-evaluated during execution.

2. The method of claim 1, wherein:

(a) said planning means further comprises;

i. ordering the clauses for sequential processing, by first scheduling clauses that combine higher processing cost and lower number of different generated values, whereby more computationally expensive clauses will be evaluated less often.

3. The method of claim 2, wherein:

(a) the data values for some of said arguments and said variables are comprised of semi-structured data, wherein said values are tagged with a label,

(b) said evaluation means further recursively selects said plans by considering the said label of some input argument values while running, and by using said label to look up said specification plans.

4. The method of claim 2, further comprising:

(a) providing a data store which is able to store and retrieve data, and

(b) specifying some of said clauses by referring to locations in said data store;

(c) further comprising specifying some of said clauses by specifying an alteration to said data store, and

(d) wherein said evaluation means further comprises;

i. altering said data store in accordance with only the clauses that refer to an alteration in said data store and that are also included in a successfully evaluated plan for said input, and in accordance only with the variable values that were tested successfully.

5. The method of claim 4, further comprising:

(a) providing a plurality of caches which are able to store sets of variable values,

(b) storing precomputed valid values of some variables of said specifications in said caches,

(c) providing a plurality of indexes, each of which is able to accept values for a predetermined subset of the variables in one of said caches, and to return all matching sets of the remaining values,

(d) providing an indexing means which is able to create one of said indexes given one of said caches and a predetermined subset of input variables,

(e) wherein said evaluation means further comprises;

i. generating some variable values by inputting other variable values into said indexes, and

(f) providing an updating means which uses data changes in said data store as input arguments to said specifications associated with said cache, and evaluates a modified version of said plans associated with said specifications, in order to determine which portions of said cache must be updated.

6. The method of claim 5, wherein:

(a) the data values for some of said arguments and said variables are comprised of semi-structured data, wherein said values are tagged with a label,

(b) said evaluation means further recursively selects said plans by considering the said label of some input argument values while running, and by using said label to look up specification plans,

whereby a single declarative language can be used to specify the presentation, business logic, and data layers of a multi-tier application, and

whereby the same semi-structured, self-describing data model can be used throughout the presentation, business logic, and data layers, and

whereby the business logic layer specification can be used to drive the automatic creation of the best set of indexes for efficient data retrieval, and

whereby the business logic layer can benefit from the backtracking and search power of rule-based engines, and

whereby the business logic layer can benefit from the optimization efficiency of planning engines normally used only on the data layer, and

whereby the business logic layer can benefit from caching and indexing performance improvements normally reserved for the data layer, and

whereby data layer declarative queries can include user-defined functions, arbitrary iterative algorithms, and object-oriented dynamic-dispatch as part of their specifications, and

whereby applications do not require garbage-collection or any memory management by the programmer, and

whereby application source code can be specified without the run-time side-effects of function arguments passed by reference, of variable assignment and reassignment, or of long-term data store changes, and is thus amenable to automated correctness checking and automated re-writing.