Tag: Math

Monotonic functions, SQL and MySQL

MySQL

In mathematics, a monotonic function (or monotone function) is a function which preserves the given order. [Wikipedia]

To be more precise, a function f is monotonic increasing, if for every x ≤ y it holds that f(x) ≤ f(y). f is said to be strictly monotonic increasing is for every x < y it holds that f(x) < f(y).

So, if we follow values in some order, we say that f is monotonic increasing if f‘s value never decreases (it either increases or stays the same), and we say that f is strictly increasing if f‘s value is always changes “upwards”.

Monotonic functions play an important role in SQL. To discuss monotonic functions in SQL we must first determine what the order is, and then, what the function is.

Well, they both change according to our point of view. Let’s look at some examples. Take a look at the following table: Continue reading » “Monotonic functions, SQL and MySQL”

Checking for string permutation

MySQL

A permutation is a change of places. Thus, ‘lolhe’ is a permuted ‘hello’ (commonly referred to as ‘scrambled text’).

I wish to present an SQL solution for checking if two strings are permutations of the same text.

About permutations

So, if ‘lolhe’ is a permutation of ‘hello’, then ‘hello’ is a permutation of ‘lolhe’, as well; and both are permutations of ‘elloh’. The REVERSE() of a text is an example of permutation. Mathematically, string permutation is an equivalence relation, and divides all strings to equivalence classes.

Use cases

  • We may be interested in permutations when a user chooses a password. We may disallow a password which is identical to the login name; but we may also disallow upper-lower-case-only transformations of the text. We may still disallow a permutation of the text.
  • On a slightly different scale, the two queries: SELECT * FROM City WHERE id IN (5, 21, 13) and SELECT * FROM City WHERE id IN (13, 5, 21) are identical. Here, the permutation is not with string characters, but with string tokens. While the solution discussed is targeted at string characters, it can be easily converted to work with string tokens.

Checking for permutation

The solution I’m suggesting checks for permutation between 2 strings by permuting both to a third, normal form. The two string are permutations of each other if both have the same normal form.

Continue reading » “Checking for string permutation”