Aug 24, 2019 - Index-free adjacency

Graph databases are much more efficient than traditional relational databases for traversing interconnected data. The way they store data and execute queries is heavily optimized for this use case, and one property in particular is key for achieving such higher performance: index-free adjacency.

This short article first analyzes the complexity of data traversal in relational databases, then explains how graph databases take advantage of index-free adjacency for traversing data more efficiently.

Relational Databases

Consider a social application in which users can follow each other, and its simplified database schema presented below:

relational-indexing

In this illustrative schema a Users table stores application users profiles, and a Followers table stores unidirectional “follower” relationships between users. An Index is also used to speed-up queries against the Followers table (represented in yellow).

Suppose we want to know whether or not it’s possible to reach an specific “Target User” starting from “Source User” with at most “N” steps, how do we implement this in SQL?

Since SQL by itself doesn’t support control structures and recursion, we need help of a procedural programming language for implementing this traversal algorithm, and fortunately most database systems do support structured programming out of the box for writing functions and stored procedures.

Regardless of the specific database and programming language used, the traversal code should look similar to the code example provided below:

bool CanReachTarget(int[] sourceIds, int targetId, HashSet<int> visitedIds, int steps)
{
    if (steps == 0)
        return false;

    int[] followersIds = ExecuteQuery<int[]>(
        "SELECT Follower_ID FROM Followers WHERE User_ID in ({0});",
        sourceIds
    );

    if (followersIds.Contains(targetId))
    {
        return true;
    }
    else
    {
        visitedIds.AddRange(sourceIds);
        sourceIds = followersIds.Except(visitedIds).ToArray();
        return CanReachTarget(sourceIds, targetId, visitedIds, steps - 1);
    }
}

At each level of the recursion the function will fetch all followers IDs at that level, check whether or not the target ID is present, return true in case it’s present or go one level deeper in case it’s not, keeping track of aready visited elements. If the function runs out of steps during the recursion it will return false, since it failed to reach the target ID.

Let’s exercise this algorithm with data from figure 1, starting from “Willian Johnson” (ID = 2) and trying to reach “Mary Miller” (ID = 5) with at most 3 steps:

  sourceIds targetId visitedIds steps followersIds contains?
#1 [2] 5 [ ] 3 [1, 4] false
#2 [1, 4] 5 [2] 2 [1, 2, 3, 4, 5] true

Notice that “Mary Miller” was found at the second level, and the function will return true in this case.

Now, let’s analyze the time complexity of this algorithm. You may have already realized that it’s performing a Breadth First Search (BFS), offloading most of the work to the database query engine. The BFS part executes O(V + E) operations, where V is the number of users whose followers are fetched from the database and E the aggregated number of followers from this group of users. The cost to fetch followers for each user considering a B-Tree index is O(log(n)), where n is the length of the followers table. Hence, the resulting time complexity will be O(V * log(n) + E).

Without the index things would be much worse, since a full table scan would be necessary to fetch followers, yielding O(V * n + E) time complexity in the worst case.

Graph Databases

As I’ve said at the beginning of this article graph databases take advantage of index-free adjacency for traversing data more efficiently. Figure 2 presents a logical representation of how data from figure 1 would be organized in a graph database:

index-free-adjacency

Instead of relying on a global index for accessing connected nodes, each node directly references its adjacent nodes. Even though the lack of a global index for nodes relationships is what gives the index-free adjacency property its name, you can think that each node actually holds a mini-index to all nearby nodes, making traversal operations extremely cheap.

As to leverage this structure, graph databases perform traversal queries natively, being able to execute the BFS algorithm from the previous section entirely whithin the database query engine. The BFS part will still execute O(V + E) operations, however the cost to fetch a user node followers will go down to O(1), running in constant time, since all followers are directly referenced at the node level.

You may be thinking:

What about accessing the query starting node in the first place, wouldn’t that require a global index?

And you’re completely right, in order to get to the starting point of the traversal efficiently we will have to rely on an index lookup. Again, considering a B-Tree index, this will run in O(log(n)) time in addition to the traversal.

The resulting time complexity for the query will be simply O(V + E + log(n)), much better than for relational databases, specially when the number of users (n) gets larger.


A lot of factors that affect database performance were left out of the analysis for simplicity, such as file system caching, data storage sparsity, memory requirements, schema and query optimizations.

There’s no single universal database that performs greatly in all scenarios. Different kinds of problems may be better solved using different kinds of databases, if you can afford the additional operational burden. As with most decisions in software development, a reasonable approach is to lay down your requirements and analyze whether or not tools available to you meet them before jumping to a new ship.

Aug 18, 2019 - Business logic

In software architecture, the business logic layer contains classes that implement application specific business rules, typically made available in the form of high level operations, also known as use cases. The use cases encapsulate interactions between entities, which are reusable lower level logical models of the real-world business domain.

Code Examples

Use cases have an unidirectional many-to-many relationship to entities, for instance, consider the two use cases below for an illustrative banking application:

public class GetAccountBalanceUseCase : UseCase
{
    public GetAccountBalanceUseCase(
        BankAccountIdentityProvider indentityProvider,
        BankAccountIndex accounts)
    {
        this.indentityProvider = indentityProvider;
        this.accounts = accounts;
    }

    public GetAccountBalanceOutput Execute(GetAccountBalanceInput input)
    {
        indentityProvider.Authenticate(
            input.AuthenticationToken,
            input.AccountNumber
        );

        BankAccount account = accounts.Get(input.AccountNumber);

        return new GetAccountBalanceOutput
        {
            Balance = account.GetBalance();
        };
    }

    private BankAccountIdentityProvider indentityProvider;

    private BankAccountIndex accounts;
}
public class TransferFundsUseCase : UseCase
{
    public TransferFundsUseCase(
        TransactionScopeProvider transactionScope,
        BankAccountIdentityProvider indentityProvider,
        BankAccountIndex accounts,
        Ledger ledger)
    {
        this.transactionScope = transactionScope;
        this.indentityProvider = indentityProvider;
        this.accounts = accounts;
        this.ledger = ledger;
    }

    public TransferFundsOutput Execute(TransferFundsInput input)
    {
        indentityProvider.Authenticate(
            input.AuthenticationToken,
            input.SendingAccountNumber
        );

        using (transactionScope.Begin())
        {
            BankAccount sender = accounts.Get(input.SendingAccountNumber);
            BankAccount receiver = accounts.Get(input.ReceivingAccountNumber);

            sender.Withdraw(input.Amount);
            receiver.Deposit(input.Amount);

            ledger.Insert(from: sender, to: receiver, amount: input.Amount);

            return TransferFundsOutput
            {
                SenderBalance = sender.GetBalance();
                ReceiverBalance = receiver.GetBalance();
            };
        }
    }

    private TransactionScopeProvider transactionScope;

    private BankAccountIdentityProvider indentityProvider;

    private BankAccountIndex accounts;

    private Ledger ledger;
}

Both of them depend on up to four business entities for implementing workflows for querying an account’s balance and transferring funds from one account to another:

  • BankAccountIdentityProvider: Responsible for ensuring that the agent executing the operation has adequate permissions for managing the bank account

  • BankAccountIndex: Responsible for fetching bank account entities according to their account number

  • BankAccount: Responsible for providing functionalities on the level of an individual bank account

  • Ledger: Responsible for recording economic transactions

Notice that a TransactionScopeProvider class is also present in the TransferFundsUseCase implementation, however it’s not a business entity, it’s an infrastructure component instead, determining the behavior of underlying data retrieval and persistence operations, and its specific implementation is irrelevant in this scope.

Layered Architecture

The business logic layer has no knowledge of infrastructure and operational details, such as which specific web server, message broker or database system are chosen for deploying the application. For greater flexibility and cohesion, all of these decisions are made at the outermost layer of the application, and required functionality is injected into the business logic layer with the assistance of a dependency injection strategy.

clean-architecture

The figure borrows from Uncle Bob’s clean architecture and demonstrates how business logic should be isolated from external dependencies to prevent leaking infrastructure logic to the business layer, achieving a clear separation of concerns that greatly benefits software development quality and productivity in the long-term.

The conversion logic layer is where Models, Views, Controllers, Presenters and integrations lie. It is responsible for converting data to the most convenient format inwards and outwards.

Finally, the infrastructure layer is where the application is hosted, specific UI and web frameworks are employed, and database and messaging systems are configured and interfaced.


In this short article I provide code examples for implementing use cases with the sole purpose of illustrating business logic concepts. I employ one of many different use case formats, a format which I have successfully applied in professional projects.

Aug 11, 2019 - Complexity classes of problems

In computational complexity theory problems are classified into classes according to the algorithmic complexity for solving them. Confusion often arises due to the fact that naming of these classes are not intuitive, and even misleading. For instance, many consider that the complexity class “NP” stands for “non-polynomial time” when it actually stands for “non-deterministic polynomial time”. Another common misconception is that problems that are elements of the “NP-hard” class are also elements of “NP”, which is not necessarily true.

The following table summarizes the most important complexity classes and their properties according to the current understanding in the field:

  P NP NP-complete NP-hard
Solvable in polynomial time      
Solution verifiable in polynomial time  
Reduces any NP problem in polynomial time    

Each column lays down the pre-requisites a problem ought to fulfil for being considered a member of that complexity class. Notice that, trivially, all elements of “P” are also elements of “NP”, however the inverse cannot be alleged (at least while the P versus NP problem remains a major unsolved problem in computer science).

The next sections provide more details on these properties.

Solvable in polynomial time

Defines decision problems that can be solved by a deterministic Turing machine (DTM) using a polynomial amount of computation time, i.e., its running time is upper bounded by a polynomial expression in the size of the input for the algorithm. Using Big-O notation this time complexity is defined as O(n ^ k), where n is the size of the input and k a constant coefficient.

To put it briefly, a DTM executes algorithms the same way our modern computers do. It follows a set of pre-defined instructions (program), executing one instruction at a time, changing state and resolving the next instruction. We can imagine that at any given point in time there will be a history of executed operations and a set of predictable operations to follow based solely on the machine’s current state:

deterministic-machine

As long as there’s no external stimulus (randomness) involved, systems of this kind are deterministic, always producing the same output from a given initial state.

Solution verifiable in polynomial time

Defines decision problems for which a given solution can be verified by a DTM using a polynomial amount of computation time, even though obtaining the correct solution may require higher amounts of time.

There’s a straightforward brute force search approach for solving this kind of problems:

  1. Generate a solution Si from the space of every feasible solution (in constant time)
  2. Verify the correctness of the solution Si (in polynomial time)
  3. If solution Si correctly solves the problem, end execution
  4. Otherwise move to the next unvisited position i and repeat

It’s easy to see that this algorithm has time complexity O(k ^ n) * O(w), where w is the size of every feasible solution, since it iterates over the solution space and, for each possible solution, performs a verification that takes polynomial time. Typically solution spaces are not polynomial in size, yielding exponential (O(k ^ n)) or factorial (O(n!)) time complexity for this naive approach.

Here we introduce the non-deterministic Turing machine (NTM), a theoretical computer that can take this naive algorithm and run it in a polynomial amount of time:

non-deterministic-machine

As figure 2 exemplifies, the NTM, by design, can be thought as capable of resolving multiple instructions simultaneously, branching into several execution flows, each one of them verifying a different solution to the decision problem, until one of them finds the correct one, halting the NTM.

NTMs only exist in theory, and it’s easy to understand why: Their capability for branching indefinitely into simultaneous execution flows would require an indefinitely large amount of physical resources.

Reduces any NP problem in polynomial time

Defines decision problems whose algorithms for solving them can be used to solve any NP problem after a polynomial time translation step. For instance, if we have a solver for a NP-hard problem, we can then build a solver for a NP problem as follows:

np-solver

Hence, we are effectively reducing the NP-problem into the NP-hard problem for solving it. Intuitively problems that allow this are at least as hard as the hardest NP problem, otherwise they couldn’t be used to solve any NP problem.

As a consequence, if we were to find a polynomial time algorithm for solving a NP-hard problem (which is unlikely), then we could use it to solve any NP problem in polynomial time as well, implying that P = NP and solving the P versus NP problem.

Demonstration

For this demonstration we will use two well-known NP-complete problems:

  • Knapsack problem: 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.
  • Partition problem: Given a multiset S of positive integers, determine if it can be partitioned into two subsets S1 and S2 such that the sum of the numbers in S1 equals the sum of the numbers in S2.

First, consider the following solver for the knapsack problem in its decision form:

public class KnapsackProblemSolver
{
    public bool Solve(Item[] items, int capacity, int value)
    {
      /* ... */
    }
}

This solver will answer whether or not it’s possible to achieve a value combining the available items without exceeding the knapsack weight capacity, returning true in case it’s possible, false otherwise.

The Item data structure is presented below:

public class Item
{
    public int Value { get; set; }

    public int Weight { get; set; }

    public int Limit { get; set; }
}

Now, we want to implement a solver for the partition problem that answers whether or not a given multiset can be partitioned:

public class PartitionProblemSolver
{
    public bool Solve(int[] multiset)
    {
      /* ... */
    }
}

In order to do that we evaluate both problems objectives, translate the partition problem input accordingly, and feed it into the knapsack problem solver:

public class PartitionProblemSolver
{
    public bool Solve(int[] multiset)
    {
        var sum = multiset.Sum(n => n);
        if (sum % 2 == 1) // Odd sum base case for integer multiset
          return false;
        
        /* translate partition input into knapsack input */
        var items = multiset.Select(n => new Item { Value = n,  Weight = n, Limit = 1 }).ToArray();
        var capacity = sum / 2;
        var value = capacity;

        /* feed translated input into knapsack solver */
        return new KnapsackProblemSolver().Solve(items, capacity, value);
    }
} 

Let’s analyze the translation step:

  1. It creates a set of items with a single item for each multiset element, assigning the item’s value and weight from the element’s own value.
  2. It defines the knapsack capacity as the expected sum for each partition. Hence, we know that if the capacity is completely filled, the combined weight of items inside and outside of the knapsack will be same.
  3. It defines the knapsack target value also as the expected sum for each partition. Since the defined capacity prevents a value higher than this from being achieved, the solver will return true if, and only if, the exact expected sum for each partition can be achieved, thus solving the partition problem.

If you found that fun, I suggest you try to reduce another NP problem to the knapsack problem. You’ll find out that each problem needs a slightly different approach, sometimes recurring to heuristics to make it work.


In the demonstration at the end of the article you may have noticed that I didn’t provide an actual implementation for solving the knapsack problem, however you can find one at the linked Wikipedia page, or in one of my GitHub repositories: https://github.com/TCGV/Knapsack

This is my take on the topic of complexity classes of problems, which I find of major importance for becoming a more effective, skillful software developer, giving us the tools for better analyzing and solving technical challenges. I hope you enjoyed it!