Fewer and narrower covering indexes for report tables

I recently looked at how to index a report table of six dimensions (plus the time one) with the fewer number of the narrower indexes possible. I was interested in drill-down queries, so the condition (apart from the time condition) will be formed by a conjunction of dimension key equalities.  A quick research did not come up with anything. Any prefix of an index can be used to cover a query, so I was sure that indexes with one to 6 columns would be needed. The closest I came using straightforward combinatorics was 58 permutations of six columns to cover any possible query. Not bad, compared to the total number of 720 distinct permutations. And, to be truthful, I did not derive the number by math but by eliminating unneeded permutations using a program. However, 58 indexes is still a lot, and I was still bothered by the presence of extra columns in most of those permutations. We only need one index having all six columns and we only need one index having all five columns for any subset of five columns, and so on.

It has been said that any heavy calculation that you do because you don’t grok enough math to avoid it, saves you some face if you do it in F# (ok, it is I who said it). Follows a program to calculate indexes of length 1 to N to cover any possible query with N columns. Columns are represented by numbers 1 to N+1, just to make the whole thing seem more abstract than it is. And how many are those for N=6? Not 42, unfortunately but close: [1; 2; 3; 4; 5; 6], [1; 2; 3; 4; 6], [1; 2; 3; 5; 6], [1; 2; 3; 6], [1; 2; 4; 5; 6], [1; 2; 4; 6], [1; 2; 5; 6], [1; 2; 6], [1; 3; 4; 5; 6], [1; 3; 4; 6], [1; 3; 5; 6], [1; 3; 6], [1; 4; 5; 6], [1; 4; 6], [1; 5; 6], [1; 6], [2; 3; 4; 5; 6], [2; 3; 4; 6], [2; 3; 5; 6], [2; 3; 6], [2; 4; 5; 6], [2; 4; 6], [2; 5; 6], [2; 6], [3; 4; 5; 6], [3; 4; 6], [3; 5; 6], [3; 6], [4; 5; 6], [4; 6], [5; 6], [6]

// Helpers from: http://fssnip.net/4u

let rec insertions x = function
    | []             -> [[x]]
    | (y :: ys) as l -> (x::l)::(List.map (fun x -> y::x) (insertions x ys))
let rec permutations = function
    | []      -> seq [ [] ]
    | x :: xs -> Seq.concat (Seq.map (insertions x) (permutations xs))

// The program itself

type covering = {
    covering: Set list;
}

let covers (N:int) (x:int list) =
    {
        covering= List.init N (fun i -> if x.Length>=i+1 then Set.ofSeq (Seq.take (i+1) x) else Set.ofList []);
    }

type allcovers = {
    p: Set;
    covering: Set<Set> list;
}

let emptyallcovers (N:int) =
    { 
        p= Set.ofList [];
        covering= List.init N (fun i -> Set.ofList []);
    }

let subsumes (a:int list) (b:int list) =
    if a.Length >= b.Length then
        Seq.fold (&&) true (Seq.map2 (fun i j -> i = j) a b)
    else 
        false

let add_subsuming (x:int list) (s:Set) =
    let s2 = Set.filter (fun y -> subsumes x y) s
    Set.add x (s - s2)

let combine_coverings (c:allcovers) (x:int list) (cx:covering) =
    {
        p = add_subsuming x c.p;
        covering = c.covering |> List.mapi (fun i c -> Set.add (cx.covering.Item i) c);
    }

let addifnotcovered (N:int) (c:allcovers) (x:int list) =
    let cx = covers N x
    let rec add1 (c:allcovers) (cx:covering) (x:int list) =
        let Li = x.Length - 1
        if not (Set.contains (cx.covering.Item Li) (c.covering.Item Li)) then
            combine_coverings c x cx
        elif Li = 0 then
            c
        else
            add1 c cx  (List.ofSeq (Seq.take Li x))
    add1 c cx x

let Main() =
    let N = 6
    let vec = [1 .. N]
    let p =  permutations vec
    let cp = Seq.fold (addifnotcovered N) (emptyallcovers N) p
    Seq.iter (printf "%A\n") cp.p

    printf "End"

Main()
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s