Optimization Problems with Items and Categories in Oracle – Intro

Posted on by
Reply

I recently posted a series of eight articles on my GitHub Pages blog.

[Here is the general introduction to the articles…]

The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

  • Knapsack problem

    • The knapsack problem and many other problems in combinatorial optimization require the selection of a subset of items to maximize an objective function subject to constraints. A common approach to solving these problems algorithmically involves recursively generating sequences of items of increasing length in a search for the best subset that meets the constraints.

    I applied this kind of approach using SQL for a number of problems, starting in January 2013 with A Simple SQL Solution for the Knapsack Problem (SKP-1), and I wrote a summary article, Knapsacks and Networks in SQL
    , in December 2017 when I put the code onto GitHub, sql_demos – Brendan’s repo for interesting SQL.

    Here is a series of eight articles that aim to provide a more formal treatment of algorithms for item sequence generation and optimization, together with practical implementations, examples and verification techniques in SQL and PL/SQL.

    List of Articles

    GitHub

  • Optimization Problems with Items and Categories in Oracle

    • Twitter

  • Thread with Short Recordings

    • [Here is the conclusion to the articles…]

    We can list here some of the features and concepts considered in the whole series.

    Sequence Generation

    • 4 types of sequence defined
    • sequence generation explained via recursion…
    • …implemented by recursion and by iteration

    Optimization Problems

    • sequence truncation using simple maths
    • value filtering techniques with approximation and bounding
    • two-level iterative refinement methods

    SQL

    • recursive SQL
      • materializing subqueries via hints or use of temporary tables
      • cycles and some anomalies
    • storing sequences of items in SQL by concatenation, nested tables, and linking tables
    • index organised tables
    • partitioned outer joins
    • splitting concatenated lists into items via row-generation
    • combining lists of items into concatenated strings by aggregation
    • passing bind variables into views via system contexts
    • automated generation of execution plans

    PL/SQL

    • PL/SQL with embedded SQL as alternative solution methods to recursive SQL…
    • …with sequence generation by both recursion and iteration, with performance comparisons
    • use of arrays and temporary tables for intermediate storage, with performance comparisons
    • methods for compact storage of sequences of items
    • use of PL/SQL functions in SQL and performance effects of context switching
    • automated code timing

    Verification Techniques

    Automation

    • installation
    • running the solution methods
    • code instrumentation
    • unit testing
    • blog internal links hierarchy






    Oracle User Group Ireland Presentations

    Posted on by
    Reply

    I have presented at the annual conference of the Oracle User Group Ireland four times, in the Gresham hotel on O’Connell Street in Dublin. Here are my slides:






    The Math Function Unit Testing Design Pattern – Introduction

    Posted on by
    Reply

    I have just posted The Math Function Unit Testing Design Pattern on my GitHub blog.

    Here is the introduction…

    This article provides an overview of a new design pattern for unit testing in any programming language, ‘The Math Function Unit Testing Design Pattern’. The data-driven design pattern involves repeatable, automated testing, and minimises unit test code (see example) by delegating to library modules the unit test driver, reading/writing of test data and assertion and formatting of results.

    After a section on the background, the article describes the design pattern in two parts: the first deals with the concepts of transactions and APIs and why we should base our unit testing around APIs, while the second describes the design pattern at high level.

    There are modules in Oracle PL/SQL, JavaScript, Powershell and Python implementing utilities to support the design pattern, and demonstrating its use. A final section provides links to their GitHub projects and some related articles.

    Infographic: The Bauhaus, Where Form Follows Function

    Wrapper Function – Purely_Wrap_All_Nets

    Go to source location
    Here is the complete function:

    FUNCTION Purely_Wrap_All_Nets(
            p_inp_3lis                     L3_chr_arr)   -- input list of lists (group, record, field)
            RETURN                         L2_chr_arr IS -- output list of lists (group, record)
  l_act_2lis        L2_chr_arr := L2_chr_arr();
  l_csr             SYS_REFCURSOR;
BEGIN
  FOR i IN 1..p_inp_3lis(1).COUNT LOOP
    INSERT INTO network_links VALUES (p_inp_3lis(1)(i)(1), p_inp_3lis(1)(i)(2), p_inp_3lis(1)(i)(3));
  END LOOP;
  l_act_2lis.EXTEND;
  OPEN l_csr FOR SELECT * FROM TABLE(Net_Pipe.All_Nets);
  l_act_2lis(1) := Utils.Cursor_To_List(x_csr    => l_csr);
  ROLLBACK;
  RETURN l_act_2lis;
END Purely_Wrap_All_Nets;

    This is a good example of how little code may be necessary when following The Math Function Unit Testing Design Pattern: The complexity of the code reflects only the complexity of the external interface. Here, there are single input and output groups, and so the code is equally simple, despite the unit under test having a larger degree of internal complexity.