Extending relational algebra for data management

Abstract

Systems and Methods are provided for improving the ability to apply modeling techniques similar to relational algebra to an expanded number of workflows. By allowing a relational algebra type modeling technique to be applied to an expanded number of workflows, an increased number of data processing workflows can be more readily improved, such as by automatic modification of the sequence of tasks in a workflow, to reduce the execution costs for a workflow. The relational algebra type modeling technique can also allow for identification of portions of data processing workflows or queries that share a common input and output.

What is claimed is: 
     
         1 . A computer-implemented method for managing a distributed database, the method comprising:
 receiving a query defining a first workflow, the first workflow corresponding to tasks for processing data from one or more data sources, the query having a corresponding first logical expression comprising a sequence of operations defined by operators from an expanded relational algebra, at least one operator in the first logical expression being an instance of a reduce operator;   modifying an ordering of the operations in the first logical expression to form a modified first logical expression, the modifying of the ordering of the operations in the first logical expression comprising a) moving one or more operators from a position prior to the instance of the reduce operator to a position after the instance of the reduce operator, b) moving one or more operators from a position after the instance of the reduce operator to a position prior to the instance of the reduce operator, or c) a combination thereof;   constructing a modified first workflow corresponding to the modified first logical expression; and   executing at least a portion of the modified first workflow, wherein the modified first workflow has a lower execution cost than an execution cost of the first workflow.   
     
     
         2 . The computer-implemented method of  claim 1 , wherein moving one or more operators from a position prior to the instance of the reduce operator to a position after the instance of the reduce operator comprises moving a foreign key join operator from a position prior to the instance of the reduce operator to a position after the instance of the reduce operator. 
     
     
         3 . The computer-implemented method of  claim 1 , wherein executing at least a portion of the modified first workflow comprises executing tasks corresponding to all operators in the modified first logical expression. 
     
     
         4 . The computer-implemented method of  claim 1 , wherein executing at least a portion of the modified first workflow comprises executing tasks corresponding to fewer than all tasks in the first workflow defined by the query. 
     
     
         5 . A computer-implemented system comprising:
 one or more sensors configured to provide sensor data from at least one user device;   one or more processors; and   one or more computer storage media storing computer-useable instructions that, when executed by the one or more processors, implement a method for managing a distributed database, the method comprising:   receiving a first workflow corresponding to tasks for processing data from one or more data sources, the first workflow having a corresponding first logical expression comprising a sequence of operations defined by operators from an expanded relational algebra, at least one operator in the first logical expression being an instance of a reduce operator;   modifying an ordering of the operations in the first logical expression to form a modified first logical expression, the modifying of the ordering of the operations in the first logical expression comprising a) moving one or more operators from a position prior to the instance of the reduce operator to a position after the instance of the reduce operator, b) moving one or more operators from a position after the instance of the reduce operator to a position prior to the instance of the reduce operator, or c) a combination thereof;   constructing a modified first workflow corresponding to the modified first logical expression; and   executing at least a portion of the modified first workflow.   
     
     
         6 . The computer-implemented system of  claim 5 , wherein the modified first workflow has a lower execution cost than an execution cost of the first workflow. 
     
     
         7 . The computer-implemented system of  claim 5 , wherein the first workflow is constructed based on a query. 
     
     
         8 . The computer-implemented system of  claim 5 , wherein the modifying includes increasing a number of operators in common with a sequence of a second logical expression of a second workflow. 
     
     
         9 . The computer-implemented system of  claim 5 , wherein moving one or more operators from a position prior to the instance of the reduce operator to a position after the instance of the reduce operator comprises moving a foreign key join operator from a position prior to the instance of the reduce operator to a position after the instance of the reduce operator. 
     
     
         10 . The computer-implemented system of  claim 5 , wherein moving one or more operators from a position after the instance of the reduce operator to a position prior to the instance of the reduce operator comprises moving a foreign key join operator from a position after the instance of the reduce operator to a position prior to the instance of the reduce operator. 
     
     
         11 . The computer-implemented system of  claim 5 , wherein the modifying includes increasing a number of operators in common with a sequence of a second logical expression of a second workflow, and the executing uses an intermediate data set formed by executing a portion of the second workflow corresponding to operators added by the increasing the number of operators. 
     
     
         12 . The computer-implemented system of  claim 5 , wherein the modifying includes increasing a number of operations in common with a sequence of a second logical expression of a second workflow, and the executing uses an intermediate data set formed by executing a portion of the second workflow corresponding to operations added by the increasing the number of operations. 
     
     
         13 . One or more computer storage devices storing computer-useable instructions that, when used by one or more computing devices, cause the one or more computing devices to perform a method for managing a distributed database, the method comprising:
 receiving a first workflow corresponding to tasks for processing data from one or more data sources, the first workflow having a corresponding first logical expression comprising a sequence of operations defined by operators from an expanded relational algebra, at least one operator in the first logical expression being an instance of a reduce operator;   modifying an ordering of the operations in the first logical expression to form a modified first logical expression, the modifying of the ordering of the operations in the first logical expression comprising a) moving one or more operators from a position prior to the instance of the reduce operator to a position after the instance of the reduce operator, b) moving one or more operators from a position after the instance of the reduce operator to a position prior to the instance of the reduce operator, or c) a combination thereof;   constructing a modified first workflow corresponding to the modified first logical expression; and   executing at least a portion of the modified first workflow.   
     
     
         14 . The one or more computer storage devices of  claim 13 , wherein the modifying includes increasing a number of operators in common with a sequence of a second logical expression of a second workflow. 
     
     
         15 . The one or more computer storage devices of  claim 13 , wherein the first workflow is constructed based on a query. 
     
     
         16 . The one or more computer storage devices of  claim 13 , wherein the modified first workflow has a lower execution cost than an execution cost of the first workflow. 
     
     
         17 . The one or more computer storage devices of  claim 13 , wherein moving one or more operators from a position prior to the instance of the reduce operator to a position after the instance of the reduce operator comprises moving a foreign key join operator from a position prior to the instance of the reduce operator to a position after the instance of the reduce operator. 
     
     
         18 . The one or more computer storage devices of  claim 13 , wherein moving one or more operators from a position after the instance of the reduce operator to a position prior to the instance of the reduce operator comprises moving a foreign key join operator from a position after the instance of the reduce operator to a position prior to the instance of the reduce operator. 
     
     
         19 . The one or more computer storage devices of  claim 13 , wherein the modifying includes increasing a number of operators in common with a sequence of a second logical expression of a second workflow, and the executing uses an intermediate data set formed by executing a portion of the second workflow corresponding to operators added by the increasing the number of operators. 
     
     
         20 . The one or more computer storage devices of  claim 13 , wherein the modifying includes increasing a number of operations in common with a sequence of a second logical expression of a second workflow, and the executing uses an intermediate data set formed by executing a portion of the second workflow corresponding to operations added by the increasing the number of operations.