Optimization Problems with Items and Categories in Oracle – Intro

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

    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:






    A Note on Updates to Unit Testing Projects

    This is a brief article to summarise some recent developments relating to my ‘Math Function Unit Testing design pattern’.

    Further to an article I posted in October 2021, Unit Testing, Scenarios and Categories: The SCAN Method, I have updated two unit testing utility packages to integrate the category set concept explored there.

    The Powershell utility, Write-UT_Template, has also been extended to generate a template scenario for each scenario listed in a new CSV input file. In addition, the Powershell package has new functions for automation of the unit testing steps both for scripting languages and for Oracle PL/SQL.

    Experience with the SCAN method has led to two extensions that simplify its application:

    1. Introduction of a new visualisation, the Category Structure Diagram, for example:
    2. (Mostly) 1-1 mapping between categories and scenarios

    The project README files have also been reworked, in particular with updating of the Usage sections to centre around the three main steps in the design pattern.

    These changes can be seen in the two projects above, and have also been applied in the Oracle projects:

    Here is the background section from the first of the latter two projects:

    Background

    I explained the concepts for the unit testing design pattern in relation specifically to database testing in a presentation at the Oracle User Group Ireland Conference in March 2018:

    The Database API Viewed As A Mathematical Function: Insights into Testing

    I later named the approach ‘The Math Function Unit Testing design pattern’ when I applied it in Javascript and wrote a JavaScript program to format results both in plain text and as HTML pages:
    Trapit – JavaScript Unit Tester/Formatter

    The module also allowed for the formatting of results obtained from testing in languages other than JavaScript by means of an intermediate output JSON file. In 2021 I developed a powershell module that included a utility to generate a template for the JSON input scenarios file required by the design pattern:
    Powershell Trapit Unit Testing Utilities Module

    Also in 2021 I developed a systematic approach to the selection of unit test scenarios:
    Unit Testing, Scenarios and Categories: The SCAN Method

    In early 2023 I extended both the the JavaScript results formatter, and the powershell utility to incorporate Category Set as a scenario attribute. Both utilities support use of the design pattern in any language, while the unit testing driver utility is language-specific and is currently available in Powershell, JavaScript, Python and Oracle PL/SQL versions.

    This module is a prerequisite for the unit testing parts of these other Oracle GitHub modules:
    Utils – Oracle PL/SQL General Utilities Module
    Log_Set – Oracle PL/SQL Logging Module
    Timer_Set – Oracle PL/SQL Code Timing Module
    Net_Pipe – Oracle PL/SQL Network Analysis Module

    Examples of its use in testing four demo PL/SQL APIs can be seen here:
    Oracle PL/SQL API Demos – demonstrating instrumentation and logging, code timing and unit testing of Oracle PL/SQL APIs