{"id":90408,"date":"2021-03-26T14:40:20","date_gmt":"2021-03-26T14:40:20","guid":{"rendered":"https:\/\/www.red-gate.com\/simple-talk\/?p=90408"},"modified":"2021-06-03T16:48:14","modified_gmt":"2021-06-03T16:48:14","slug":"a-data-transformation-problem-in-sql-and-scala-dovetailing-declarative-solutions-part-ii","status":"publish","type":"post","link":"https:\/\/www.red-gate.com\/simple-talk\/databases\/sql-server\/t-sql-programming-sql-server\/a-data-transformation-problem-in-sql-and-scala-dovetailing-declarative-solutions-part-ii\/","title":{"rendered":"A data transformation problem in SQL and Scala: Dovetailing declarative solutions Part II"},"content":{"rendered":"

Part II : Equivalent Solutions in Functional Programming \u2013 Scala <\/span><\/h2>\n

Part I<\/a> of this two-part series presented the series problem then solved it in SQL Server. However, this was a simulation meant to provide the following: result sets against which the actual software can verify; and a query execution plan that can serve as a pattern for the actual software design. In this second of the series, components from the former guide the software development, which will be done in functional programming \u2013 specifically, Scala.<\/p>\n

Scala is not a CLR language, so I don\u2019t expect you to know it. Therefore, the article starts with just enough background in functional programming and Scala to follow the discussion. You do, though, need some experience in any imperative or functional language so that structures such as lists, sets, and maps are familiar.<\/p>\n

Declarative programming is a major theme in this series. You already know the style from work done in (T-)SQL DML. If you are unfamiliar with functional programming, then consider this article a voyage into a foreign paradigm in which concise and elegant logic describes transformations over immutable data. Keep in mind that there is much more to functional programming than is presented here \u2013 emphasis, again, is its declarative nature.<\/p>\n

The Scala file and its executable (not included), runnable in PowerShell, plus all project files are available in the download<\/a>.<\/p>\n

Functional programming: Basics in Scala<\/h2>\n

This cursory look into functional programming (FP) starts with relevant terms and concepts, and I\u2019ll add more later as the discussion progresses. The second subtopic examines the anonymous function, and the third, map functions. Return to this section as needed or skip it if you know Scala.<\/p>\n

Terminology and concepts<\/h3>\n

At the highest level, functional programming is about composing operations over immutable data. Operations are functions written declaratively \u2013 i.e., in concise logic that describe transformations. Functions do not alter object or program state; they only compute results. Contrast this with the imperative programming style, such as object-oriented programming (OOP), in which lower-level steps delineated in order in sequences and loops and branches can change program state.<\/p>\n

In FP, functions are pure,<\/em> meaning that they have no side effects such as reading from or writing to data sources or mutating data in place. As a result, given the same input values, a pure function always returns the same output value. Furthermore, they always return a usable<\/em> value, never a void<\/code> (Unit in Scala), which signifies that the method is invoked to produce a side effect(s). In the solution\u2019s sections, I\u2019ll isolate all pure functions in one place.<\/p>\n

(C# and perhaps all languages allow writing pure functions. FP takes it much further.)<\/p>\n

Here are some Scala-specific keywords you will see in explanations and code:<\/p>\n

    \n
  • trait<\/em><\/strong>.<\/em> Roughly analogous to an interface in OOP.<\/li>\n
  • def<\/em><\/strong>.<\/em> A named method.<\/li>\n
  • val<\/em><\/strong>.<\/em> A variable that can\u2019t be reassigned to a different value.<\/li>\n
  • type<\/em><\/strong>.<\/em> A user-defined alias, possibly parameterized, for a data structure or function<\/li>\n
  • object<\/em><\/strong>. <\/em>A one-instance class whose members are (therefore) all static (one copy only). Can be standalone or companion <\/em>to a trait or class when they share the same name. The latter type is used in the code.<\/li>\n<\/ul>\n

    Finally, and critically, FP functions are first-class values, <\/em>meaning they can appear anywhere a type-referencing variable can.<\/p>\n

    Next is an important kind of function.<\/p>\n

    The Anonymous Function<\/h3>\n

    An anonymous function<\/em> is any that is not a named, reusable method \u2013 i.e, not introduced with the keyword def<\/code> in Scala. It is also known as a function literal, and more universally, as a lambda expression. I\u2019ll use anonymous function<\/em> and lambda<\/em> interchangeably. The arrow symbol =><\/code> separates the bound parameters, if any, from the computation. Bound variable names are arbitrary.<\/p>\n

    <\/p>\n

    Figure 1. A Scala anonymous function with two bound parameters<\/strong><\/p>\n

    This basic example next shows a variable bound to an anonymous function and its invocation. Variable timesThree<\/code> represents an unnamed function of type Int<\/code> (integer) to Int \u2013 left of =<\/code> \u2013 that is defined as taking an Int argument x<\/code> and returning a transformed Int<\/code> value.<\/p>\n

    \"Text\n\nDescription<\/p>\n

    Figure 2. One of several ways to define and use an anonymous function<\/strong><\/p>\n

    Colons indicate variable types and return type.<\/p>\n

    A higher-order function<\/em> takes a function(s) as a parameter(s) and\/or returns a function. Thus, an anonymous function, a variable such as timesThree<\/code>, or a named method could all be arguments.<\/p>\n

    \"Text\n\nDescription<\/p>\n

    Figure 3. A well-known kind of higher-order function<\/strong><\/p>\n

    Higher-order method composeInt<\/code> takes two function parameters and does a common operation. Without providing the x<\/code> value (3) argument, the return is a lambda as was echoed to screen (Int => Int<\/code>).<\/p>\n

    NOTE: These examples were done in PowerShell. To try this on Windows, you must set up the Java JDK and Scala. Some websites, though, let you enter and run Scala code in a browser \u2013 just learn the println()<\/code> command.<\/p>\n

    Two important higher-order functions are next.<\/p>\n

    Map functions<\/h3>\n

    A polymorphic function <\/em>is one parameterized by type(s), allowing methods to be written generically, independent of instantiating type. A type can be the return type or type held by the returned containing object, and\/or type of a parameter(s).<\/p>\n

    Known by varying names in possibly all FP languages are Scala\u2019s polymorphic functions map()<\/em> and flatMap()<\/em>.<\/p>\n

    <\/p>\n

    Figure 4. A higher-order polymorphic function for sequence collections<\/strong><\/p>\n

    Type parameters in Scala are in square brackets. The Seq<\/code> trait is a supertype for sequence collections such as list and vector.<\/p>\n

    Part I showed that declarative T-SQL code could be translated into a loop implementation by the query optimizer. In a similar vein, map()<\/code> abstracts looping over all collection elements, applying the polymorphic function \u2018f\u2019 parameter to each element. This is the result:<\/p>\n

    The original collection is unchanged; a new collection of the same class \u2013 in this example, a Seq subclass \u2013 holding the transformed elements of type B is returned.<\/em><\/p>\n

    Type B may or not be the same as type A, held in the original collection.<\/p>\n

    The map()<\/code> can be chained with other map()<\/code> calls and other operations but is not suited to nest another map()<\/code> to simulate a nested loops pattern. This requires a more powerful form of map function.<\/p>\n

    <\/p>\n

    Figure 5. The flatMap function signature<\/strong><\/p>\n

    The IterableOnce<\/code> trait is a more general base for all traversable data structures, as it covers the sequences in examples here as well as Sets<\/code> and Maps<\/code> and some non-collection types as well.<\/p>\n

    The background ends here. You will see maps and other higher-order functions in the solutions.<\/p>\n

    Solution space: IceCream trait<\/h2>\n

    Having the download file IceCream_client.scala<\/em> open aids the discussion. The commented code file also has many features and tests I won\u2019t cover in this article. Make sure you have the latest version of the file, as it has changed since the release of the first article.<\/p>\n

    Recall the T-SQL query plan from Part I:<\/p>\n

    \"A<\/p>\n

    Figure 6. Query plan from Section \u2018Query Rewrite II\u2019<\/strong><\/p>\n

    The subtopic covers translating the plan into methods and index simulators in Scala.<\/p>\n

    Mirroring the T-SQL Query Plan<\/h3>\n

    The following table shows the mapping from query plan items \u2013 the T-SQL blueprint above \u2013 to Scala pure functions and index simulators. Both will be covered in detail in subsequent topics.<\/p>\n

    \"Table\n\nDescription<\/p>\n

    Figure 7. Query plan to Scala mapping<\/strong><\/p>\n

    Notice that there isn\u2019t a precise correspondence from T-SQL to Scala objects. In rows two and three, the clustered index seeks, which use the primary key, reflect to different Scala methods and index simulators. In rows one and three, two different index seek types and index usage map to the same Scala method and index simulator.<\/p>\n

    \"Text\n\nDescription<\/p>\n

    Figure 8. Trait as client interface<\/strong><\/p>\n

    The IceCream trait in the figure above serves as the Scala client interface of available methods.. Two are defined in the trait, and the rest are abstract. Additional methods, some of which to be discussed, are documented in the download Scala file.<\/p>\n

    Since most relational tables have primary keys, they are sets, whether well-normalized (redundancy-free) or not. The query plan operators in the rewrite produce and work with denormalized sets of rows. In parallel, almost all trait functions return RowSets and have Set or RowSet parameters. This is by design. RowSet \u2013 meant to be intuitively named \u2013 is defined anon.<\/p>\n

    Client software now needs a way to create the object that implements the IceCream contract.<\/p>\n

    Solution space: IceCream companion object<\/h2>\n

    Some data types in the trait are user-defined aliases from the companion object.<\/p>\n

    \"Graphical<\/p>\n

    Figure 9. Type aliases and factory method<\/strong><\/p>\n

    A Row<\/code> is a three-tuple of strings representing (Maker, Flavor, Base Flavor). Types RowSeq<\/code> and RowSet<\/code>, then, are sequence and set parameterized data types holding the tuples. Tuple components are referenced with _x<\/code> position notation, where x<\/code> is 1,2,3\u2026<\/p>\n

    The apply()<\/code> function in companion objects has special meaning: it is a factory method clients use for creating the implementing object. In the IceCream<\/em> project, the companion creates its own private class, passing it the RowSeq<\/code> data, and returns the trait interface. This hidden implementation\/separation of concerns style is a common design paradigm.<\/p>\n

    The object\u2019s private class IceCreamImpl<\/code> extends <\/em>\u2013 roughly, inherits \u2013 the trait and encapsulates the resources for doing all data transformations.<\/p>\n

    Solution Space: IceCream Implementation<\/h2>\n

    I\u2019ll now broaden the meaning of \u2018blueprint\u2019 to include the query plan (Figure 6), its mapping to Scala equivalents (Figure 7), and the IceCream<\/code> trait interface (Figure 8). Hidden class IceCreamImpl<\/code> now has its pattern.<\/p>\n

    <\/p>\n

    Figure 10. Implementation class\u2019 initial data and trait extension <\/strong><\/p>\n

    The rows<\/code> in the parameter list is the OS file data, and keyword extends<\/code> is analogous to OOP inheritance but follows different rules (not covered).<\/p>\n

    The two subtopics cover building the index simulators and realizing the interface. All code is within class IceCreamImpl<\/code>.<\/p>\n

    Class construction: Index creation<\/h3>\n

    T-SQL indexes (roughly) translate to key-value (k-v) pairs, which equate to the Map<\/code> data structure. I\u2019ve set up keys and values using a trait and case classes. A trait can be used solely for grouping related items, and a case class,<\/em> for purposes here, is a class created without keyword \u2018new\u2019 and whose constructor parameters are default public.<\/p>\n

    \"A<\/p>\n

    Figure 11. Structures used by index simulators<\/strong><\/p>\n

    From the blueprint, primary key index PK_MakerFlavor<\/code> has a compound key (Maker<\/code>, Flavor<\/code>) to which MF<\/code> corresponds. In figure next, the Map<\/code> is built from the initial data using several map functions:<\/p>\n

    \"Text\n\nDescription<\/p>\n

    Figure 12. The primary key equivalent<\/strong><\/p>\n

    In the first code line (rows.groupMap\u2026<\/code>), in its first argument list (currying \u2013 not covered), the Map key is set to the composite key equivalent MF for every element in list rows. Put more explicitly: function groupMap<\/code> iterates over every three-tuple (Maker, Flavor, Base Flavor) in the rows<\/code> sequence of initial data, binding local variable row<\/code> to each tuple at each pass. The entire argument \u2013 ((row: Row) => \u2026)<\/code> \u2013 is a lambda.<\/p>\n

    The second argument list sets the k-v value to the Base Flavor (shorthand tuple access _._3<\/code>, also a lambda). The result is a Seq[String]<\/code>, where String<\/code> is base flavor. This, though, is misleading. Per the business rules (Part I), a single value, not an ordered sequence of values, is correct and clearer. This is done in the next two lines.<\/p>\n

    On the newly generated Map<\/code>, its flatMap()<\/code> \u2013 essentially, the outer loop \u2013 iterates over every k-v pair. The nested map()<\/code> \u2013 inner loop \u2013 translates and returns each one-row sequence (kv._2<\/code>) of base flavors into the k-v value. A k-v pair in Map<\/code> is represented as (k -> v<\/code>).<\/p>\n

    If you\u2019ve never worked with functional programming, I hope you are reading for the gist of it and appreciate its compactness and elegance (among other benefits).<\/p>\n

    The IX_MakerFlavor_Flavor<\/code> covering index simulator can be built from this primary key simulator:<\/p>\n

    <\/p>\n

    Figure 13. The covering index equivalent<\/strong><\/p>\n

    This time, again by the business rules, a sequence (list) of case class BM<\/code> is correct, as sample output from both Map<\/code> structures shows:<\/p>\n

    \"Graphical<\/p>\n

    Figure 14. Sample equivalent rows from primary key and covering index simulators<\/strong><\/p>\n

    The covering index simulator flavor_bm_map<\/code> restructures the data in the primary key simulator makerFlavor_baseF_map<\/code> exactly as it happened in the database.<\/p>\n

    Serving the interface<\/h3>\n

    For brevity, I won\u2019t cover the entire trait interface \u2013 just enough to explore using the indexes and deriving solutions. Refer to T-SQL to Scala mapping Figure 7.<\/p>\n

    \"Text\n\nDescription<\/p>\n

    Figure 15. Simulating index seeks<\/strong><\/p>\n

    Method getFlavorSet<\/code> is invoked to emulate two different T-SQL query plan operators using index seeks over the IX_MakerFlavor_Flavor<\/code> and PK_MakerFlavor<\/code> indexes (rows 1 and 3). The former restricts on Mint, Coffee, Vanilla and the latter, Vanilla solely, as given in the flavors<\/code> parameter.<\/p>\n

    Method withFilter<\/code> is a non-strict filter, meaning \u2013 in usage here \u2013 that it doesn\u2019t produce an intermediate set that must be garbage collected but rather restricts the flatMap<\/code> domain during its traversal of elements. Its lambda argument simply eliminates any flavor not recognized as a key in flavor_bm_map<\/code> rather than throwing or handling an exception.<\/p>\n

    The flatMap<\/code> iterates over every recognized flavor. The flavor_bm_map(flavor)<\/code> operation returns the list of BM<\/code> (base flavor, maker) case classes \u2013 the value in the k-v \u2013 and the map function takes each to form an individual Row<\/code>.<\/p>\n

    \"Text\n\nDescription<\/p>\n

    Figure 16. Query result over three flavors<\/strong><\/p>\n

    Method getMakerLikeSet<\/code> corresponds to the upper Clustered Index Seek branch in the lower input to Nested Loops (row 2). The seek is done on the primary key index but is inefficient as its Predicate must tease apart the maker name. The method equivalent is worse.<\/p>\n

    \"Text\n\nDescription<\/p>\n

    Figure 17. The method finds all \u2018Creamery\u2019 makers (suboptimal)<\/strong><\/p>\n

    The like<\/code> argument trivially is \u2018Creamery\u2019. For every k-v key in the primary index simulator, the algorithm filters out all makers who aren\u2019t \u2018Creamery\u2019 using a non-interface named method (not shown) rather than a lambda. (Without elaboration, a more optimal version is possible but involved.)<\/p>\n

    Deprecated function getBaseFlavorSet<\/code> uses a third covering index simulator having base flavor as key. The first article proved why this index is not desired; here, as in the T-SQL, usage produces four rows to be culled later instead of the desired two. This was also proved in the Scala test run.<\/p>\n

    All needed methods and resources are now in place for IceCreamImpl<\/code> to solve the series problem. Here is the first of two solutions:<\/p>\n

    \"Text\n\nDescription<\/p>\n

    Figure 18. Equivalent to T-SQL query rewrite II (final form)<\/strong><\/p>\n

    The first parameter outerFlavors<\/code> contains the three flavors as discussed; the second, Creamery; and the third, Vanilla. The first invocation of getFlavorSet<\/code> mimics the query plan outer input to Nested Loops. This set of three-tuple rows intersects (\u2018&\u2019) with the rows simulating the inner input, thereby paralleling the Nested Loops\u2019 Inner Join logical operation. The call to getMakerLikeSet<\/code> retrieves the Creamery rows and does a union (\u2018|\u2019) with the second invocation of the getFlavorSet<\/code>. The union mirrors the Stream Aggregate \u2190 Concatenation operators.<\/p>\n

    The second, equivalent solution, is more function composition style.<\/p>\n

    \"Text\n\nDescription<\/p>\n

    Figure 19. Solution in function composition<\/strong><\/p>\n

    The blueprint has been realized in software. All that is left is to verify the result:<\/p>\n

    \"Table\n\nDescription<\/p>\n

    Figure 20. Software and T-SQL yield the same result set<\/strong><\/p>\n

    The Client<\/h2>\n

    Programming side effects include I\/O, and these are limited exclusively to the client, which consumes the IceCream<\/code> trait and companion object. The client reads the data from the OS file, packages it for consumption by the factory method in the companion, and invokes the pure functions in the trait, printing results to screen. For brevity, here is a snippet from the call to apply()<\/code>:<\/p>\n

    <\/p>\n

    Figure 21. Transforming the OS file data for IceCream factory method apply()<\/strong><\/p>\n

    Variable v<\/code> holds the data from the .csv<\/em> file as a sequence of strings, and the tail<\/code> function skips past the (Maker, Flavor, BaseFlavor) header. The first map()<\/code> transforms each line in the sequence (Seq[String]<\/code>) to an array size three of strings (Array[String]). A second map()<\/code> chains to the first to turn each array into a three-tuple.<\/p>\n

    In Conclusion<\/h2>\n

    This second and last article in the series gave a condensed background in functional programming and Scala. This included higher-order, pure, and map functions and lambda arguments. All data transformations were done using these constructs, plus a non-strict filter method. In good functional programming style, all coding was declarative: no low-level control flow statements were written.<\/p>\n

    The notion of blueprint was widened, first by a translation grid that mapped T-SQL query plan operators and indexes to pure functions and Map types as index simulators. This led to the development of the IceCream<\/code> trait client interface.<\/p>\n

    The trait was paired with a companion object whose major purpose was to expose a factory method (apply()<\/code>) for creating the implementation object from a hidden (private) class and returning the IceCream<\/code> interface to the client. The client\u2019s responsibility was to supply the factory method with the OS file data. (Or data from any source.)<\/p>\n

    Last Word<\/strong><\/h2>\n

    In sum, the series presented my own methodology for solving a class of problems. I doubt you would disagree with adding SQL Server to the development environment as a means of verifying computations.<\/p>\n

    As for doing a deeper relational analysis to devise a query plan that can serve as model for software design, consider that data, regardless of source, can always be modeled relationally. By tinkering with database design, indexing, query patterns and plans, you might uncover insights you may not have discovered otherwise.<\/p>\n","protected":false},"excerpt":{"rendered":"

    In this article, Shel Burkow uses the SQL execution plan from the previous article to write a program in Scala.…<\/p>\n","protected":false},"author":230507,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[53,143531],"tags":[5134],"coauthors":[20272],"class_list":["post-90408","post","type-post","status-publish","format-standard","hentry","category-featured","category-t-sql-programming-sql-server","tag-sql-prompt"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/90408","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/users\/230507"}],"replies":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/comments?post=90408"}],"version-history":[{"count":2,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/90408\/revisions"}],"predecessor-version":[{"id":90431,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/90408\/revisions\/90431"}],"wp:attachment":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/media?parent=90408"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/categories?post=90408"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/tags?post=90408"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/coauthors?post=90408"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}