novies are compared, i.e., tuples from the two relations are com- pared if they have the same [ Mid, Mid2) Model T(Mid, Mid2, Score(Ext_Moviel D Ext- Movie2) Given the relation Model, the algorithm finds movies similar to those rated by the user, aggregates those items (we will sur recommend the most correlated items lice movies RecMovies: Alice Movies Score sum AliceMovies has all the movies that Alice has rated(identified by Mid )and movies similar to them(identified by Mid2). Recommended movies. i.e. RecMovies are selected from the similar movies. Figure 5 shows possible expression trees representing some of the example workflows above With FlexRecs, it is easy to define novel recommendations, since the new operators can be composed and combined with more tra- ditional operators to form recommendation workflows. To execute recommendation workflows, algebraic laws will help an optimizer to enumerate or transform plans in search of efficient ones for gen erating the desired recommendations. Figure 6: System Architecture Under the general operator semantics we assume, we cannot fined workflows(through an appropriate user interface)with differ make any assumptions for the general properties of all the oper- ent inputs and receive customized recommendations. The Work ators. For example, we cannot make any assumption w.r.t. the flow Manager hides the details of how flexible recommendation associativity or commutativity of any blend operator because its are generated, such as the details of the algorithms and structures ies depend on the semantics assumed in any given imple- used to implement the functionality of the operators that comprise on and, in particular, on the blending method used. For a recommendation workflow and the execution order of operators, xample, the bscores of tuples may depend on the order in which which can be different from the workflow definition in order to op- the input sets of tuples are presented to the operator(e.g, the timize the process ator may give more weight to the tuples of its first input relation) The Workfow Parser takes as input a workflow and constructs an Of course, in any particular realization of the framework, one may expression tree. like these shown in Figure 5, keeping the order of ive more specific or restricted semantics to some operator and be ble to define additional rules. For example, a blend operator based the operators as defined in the workflow, since no real processing on an Occurrences method will be always commutative. On the is performed at this level other hand, the extend and recommend operators are neither com The Recommendation Plan Generator takes as input an expres- mutative nor associative based on their definition There are laws sion tree and generates a recommendation execution plan. The gen- that can be derived directly from the definition of the operators. erated plan comprises a sequence of SQL statements and function For example, selection can be pushed through an extend to its first calls and specifies how and in what order operators are executed argument:a(RiE R,)=a(RiER and any results that are shared in a particular workflow and need to be materialized. This module leverages the underlying DB en- gine's query optimizer for implementing the new operators, and 4. SYSTEM ARCHITECTURE in particular, its ability to efficiently compute joins and aggrega- tions. In addition, it allows calling functions that implement various In this section, we present a prototype system that compiles and comparison functions and blending methods. When possible, these on top of an existing database system has a number of advantage functions are compiled into the SQL statements; in other cases ex- ternal functions can be called by the SQL statements. In this way, such as implementation ease, portability and faster deployment and the system can support new types of recommendations by extend. testing of the framework in our course planning tool. It also of- fers a proof of the framework's feasibility. Extending the database ing its library. In the next section, we describe in more detail the query engine with the processing capabilities required for support recommendation plan generation proces g flexible recommendations is the next step in order to try more The Recommendation Generator executes a plan and returns the sophisticated optimizations. A high level representation of the ngine, as- chitecture is shown in Figure 6. sembles any intermediate results and invokes the functions used in Our strategy for processing workflows reduces the amount of extended relations are never materialized. On the other hand,re- 4.1 Recommendation plan generati ults generated by any recommend or blend operators, which are The system builds a recommendation plan by traversing an ex later re-used in the same workflow are materialized for efficiency. pression tree from its root and going down to its leaves. To illustrate Our workflows are converted into sequences of SQL queries, whic the recommendation plan generation process and the implementa- are then executed by the database system. Thus, we can take advan tion of the new operators, we walk through the following examples tage of the underlying query opt uumizato n. The FlexRecs engine Example 3(cont'd): We return to Example 3(Sec. 3.6)and has the following parts consider its expression tree(Figure 5), which has two recommend The Workflow Manager allows a designer to define different rec- operators. We will first see the set of queries that can be generated ommendation workflows and end-users to invoke any of the de- for implementing the lower operatormovies are compared, i.e., tuples from the two relations are com￾pared if they have the same {Mid, Mid2}. Model := π{Mid,Mid2,Score}(Ext_Movie1 . Ext_Movie2) Given the relation Model, the algorithm finds movies similar to those rated by the user, aggregates those items (we will sum up the similarity scores of the movies to the user’s movies) in order to recommend the most correlated items. AliceMovies := σVid=3232Saw ./Mid Model RecMovies := AliceMovies .Score,Sum,Mid2 AliceMovies AliceMovies has all the movies that Alice has rated (identified by Mid) and movies similar to them (identified by Mid2). Recommended movies, i.e., RecMovies, are selected from the similar movies. Figure 5 shows possible expression trees representing some of the example workflows above. With FlexRecs, it is easy to define novel recommendations, since the new operators can be composed and combined with more tra￾ditional operators to form recommendation workflows. To execute recommendation workflows, algebraic laws will help an optimizer to enumerate or transform plans in search of efficient ones for gen￾erating the desired recommendations. Under the general operator semantics we assume, we cannot make any assumptions for the general properties of all the oper￾ators. For example, we cannot make any assumption w.r.t. the associativity or commutativity of any blend operator because its properties depend on the semantics assumed in any given imple￾mentation and, in particular, on the blending method used. For example, the bscores of tuples may depend on the order in which the input sets of tuples are presented to the operator (e.g., the oper￾ator may give more weight to the tuples of its first input relation.) Of course, in any particular realization of the framework, one may give more specific or restricted semantics to some operator and be able to define additional rules. For example, a blend operator based on an Occurrences method will be always commutative. On the other hand, the extend and recommend operators are neither com￾mutative nor associative based on their definition. There are laws that can be derived directly from the definition of the operators. For example, selection can be pushed through an extend to its first argument: σc(Ri ε Rj ) ≡ σc(Ri) ε Rj . 4. SYSTEM ARCHITECTURE In this section, we present a prototype system that compiles and executes FlexRecs workflows on top of a database. Implementation on top of an existing database system has a number of advantages, such as implementation ease, portability and faster deployment and testing of the framework in our course planning tool. It also of￾fers a proof of the framework’s feasibility. Extending the database query engine with the processing capabilities required for support￾ing flexible recommendations is the next step in order to try more sophisticated optimizations. A high level representation of the ar￾chitecture is shown in Figure 6. Our strategy for processing workflows reduces the amount of data saved in temporary relations during execution. For instance, extended relations are never materialized. On the other hand, re￾sults generated by any recommend or blend operators, which are later re-used in the same workflow are materialized for efficiency. Our workflows are converted into sequences of SQL queries, which are then executed by the database system. Thus, we can take advan￾tage of the underlying query optimization. The FlexRecs engine has the following parts. The Workflow Manager allows a designer to define different rec￾ommendation workflows and end-users to invoke any of the de￾Functions Data DB Engine Recommendation Generator e Methods ß Recommendation Plan Generator FlexRecs Workflow Parser Flexible recommendation engine Application Database Workflow Manager designer define workflows User Interface invoke workflow Users Figure 6: System Architecture fined workflows (through an appropriate user interface) with differ￾ent inputs and receive customized recommendations. The Work- flow Manager hides the details of how flexible recommendations are generated, such as the details of the algorithms and structures used to implement the functionality of the operators that comprise a recommendation workflow and the execution order of operators, which can be different from the workflow definition in order to op￾timize the process. The Workflow Parser takes as input a workflow and constructs an expression tree, like these shown in Figure 5, keeping the order of the operators as defined in the workflow, since no real processing is performed at this level. The Recommendation Plan Generator takes as input an expres￾sion tree and generates a recommendation execution plan. The gen￾erated plan comprises a sequence of SQL statements and function calls and specifies how and in what order operators are executed and any results that are shared in a particular workflow and need to be materialized. This module leverages the underlying DB en￾gine’s query optimizer for implementing the new operators, and in particular, its ability to efficiently compute joins and aggrega￾tions. In addition, it allows calling functions that implement various comparison functions and blending methods. When possible, these functions are compiled into the SQL statements; in other cases ex￾ternal functions can be called by the SQL statements. In this way, the system can support new types of recommendations by extend￾ing its library. In the next section, we describe in more detail the recommendation plan generation process. The Recommendation Generator executes a plan and returns the recommendations. It sends the SQL queries to the DB engine, as￾sembles any intermediate results and invokes the functions used in the plan for comparing and blending tuples. 4.1 Recommendation Plan Generation The system builds a recommendation plan by traversing an ex￾pression tree from its root and going down to its leaves. To illustrate the recommendation plan generation process and the implementa￾tion of the new operators, we walk through the following examples. Example 3 (cont0 d): We return to Example 3 (Sec. 3.6) and we consider its expression tree (Figure 5), which has two recommend operators. We will first see the set of queries that can be generated for implementing the lower operator