/*
* Copyright (C) 2018 Centro de Computacao Cientifica e Software Livre
* Departamento de Informatica - Universidade Federal do Parana
*
* This file is part of blendb.
*
* blendb is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* blendb is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with blendb. If not, see <http://www.gnu.org/licenses/>.
*/
import { Opcode } from "../common/expression";
import { View } from "../core/view";
import { Clause } from "../core/clause";
import { Query } from "../common/query";
import { Dimension } from "../core/dimension";
import { Metric } from "../core/metric";
/**
* Dictionary with relevancy for each dimension.
* Indexed by dimention name and returns the score.
*/
interface Score {
[key: string]: number;
}
/** Result of a join/reduction view operation. */
interface ViewsAndClauses {
/** Set of views returned after operation. */
views: View[];
/** Set of clauses not applied yet. */
clauses: Clause[];
}
/**
* View's handler. Perform several operations with
* views and used to manipulate and create new views
* in a safe way.
*/
export class ViewHandler {
/**
* Perform the JOIN operation to create a new View
* @param q - Query with the parameters of the view
* to be created.
* @param views - Set of views required to create
* this view with the JOIN operation.
*/
public static queryJoin(q: Query, views: View[]): View {
if (views.length > 1) {
return new View({
metrics: q.metrics,
dimensions: q.dimensions,
origin: false,
clauses: (q.clauses) ? q.clauses : [],
sort: (q.sort) ? q.sort : [],
operation: {
opcode: Opcode.JOIN,
values: views.map((i) => i)
}
});
}
else {
return views[0];
}
}
/**
* Perform the REDUCE operation to create a new View
* @param q - Query with the parameters of the view
* to be created.
* @param view - View which the REDUCE was applied.
*/
public static queryReduce(q: Query, view: View): View {
const v = new View({
metrics: q.metrics,
dimensions: q.dimensions,
origin: false,
clauses: (q.clauses) ? q.clauses : [],
sort: (q.sort) ? q.sort : [],
operation: {
opcode: Opcode.REDUCE,
values: [view]
}
});
return (v.id !== view.id) ? v : view;
}
/**
* Constructs one view which represents a query.
* Given a set of views that cover the query
* combines its elements using JOIN and REDUCE
* operations to create a unique view.
* @param q - Query which represents the view to be created
* @param views - Views which cover the query.
*/
public static growView(q: Query, views: View[]): View {
let clausesToCover = q.clauses.map((i) => i);
let metView: View = null;
let partialJoin: View[] = null;
let reduced: ViewsAndClauses = null;
let partialQuery: Query = {
metrics: q.metrics,
dimensions: q.dimensions,
clauses: q.clauses,
sort: q.sort
};
partialJoin = views.map((i) => (i));
if (q.metrics.length === 0) { // ignore metView if there are 0 metrics
while (partialJoin.length > 1) {
partialQuery.clauses = clausesToCover;
reduced = ViewHandler.applyReduce(partialJoin, partialQuery);
clausesToCover = reduced.clauses;
partialJoin = ViewHandler.applyJoin(reduced.views);
}
return ViewHandler.applyReduce(partialJoin, partialQuery).views[0];
}
else {
const metViewId = partialJoin.findIndex((i) => i.metrics.some((j) => {
return j.name === q.metrics[0].name;
}));
metView = partialJoin[metViewId];
partialJoin.splice(metViewId, 1);
while (partialJoin.length > 1) {
partialJoin.push(metView); // MetView is now the last view
partialQuery.clauses = clausesToCover;
reduced = ViewHandler.applyReduce(partialJoin, partialQuery);
clausesToCover = reduced.clauses;
metView = reduced.views.pop();
partialJoin = ViewHandler.applyJoin(reduced.views);
}
if (partialJoin.length === 0) {
return ViewHandler.applyReduce([metView], partialQuery).views[0];
}
else {
partialJoin.push(metView);
// In this case, there are exactly 2 views
reduced = ViewHandler.applyReduce(partialJoin, partialQuery);
partialJoin = ViewHandler.applyJoin(reduced.views);
partialQuery.clauses = reduced.clauses;
return ViewHandler.applyReduce(partialJoin, partialQuery).views[0];
}
}
}
/**
* Calculate the score of a set of dimensions.
* @param views - Views which contain the dimensions to be scored.
* @param clauses - Clauses which contain the dimensions to be scored.
* @param dimensions - Dimensions in a query. These receives a extra score.
*/
private static dimensionsScore(views: View[], clauses: Clause[], dimensions: Dimension[]): Score {
let map: { [key: string]: number } = {};
for (let i = 0; i < views.length; ++i) {
const dims = views[i].dimensions;
for (let k = 0; k < dims.length; ++k) {
if (map[dims[k].name]) {
++map[dims[k].name];
}
else {
map[dims[k].name] = 1;
}
}
}
for (let i = 0; i < dimensions.length; ++i) {
let dim = dimensions[i];
if (map[dim.name]) {
++map[dim.name];
}
else { // Necessary for sub dimensions
map[dim.name] = 1;
}
}
/*
Also mark scores for dimensions inside clauses
*/
for (let i = 0; i < clauses.length; ++i) {
for (let j = 0; j < clauses[i].targets.length; ++j) {
if (map[clauses[i].targets[j].name]) {
++map[clauses[i].targets[j].name];
}
}
}
return map;
}
/**
* Apply the reduce operation in a set of views.
* Returns the reduced views and the set of clauses which could
* not be applied.
* @param v - Set of views to be reduced.
* @param q - Target query. Used to know which dimentions ca be removed
* and which clauses must be applied.
*/
private static applyReduce(v: View[], q: Query): ViewsAndClauses {
let changed = true;
const views = v.map((i) => i);
let clausesToCover = q.clauses.map((i) => i);
while (changed) {
changed = false;
let map = ViewHandler.dimensionsScore(views, clausesToCover, q.dimensions);
const unfilledSubDims = q.dimensions.filter((item) => {
return map[item.name] < 2;
});
let ancestors: { [key: string]: Dimension[] } = {};
for (let i = 0; i < unfilledSubDims.length; ++i) {
let dim = unfilledSubDims[i];
ancestors[dim.name] = [dim];
dim = dim.parent;
while (dim !== null) {
ancestors[unfilledSubDims[i].name].push(dim);
dim = dim.parent;
}
}
for (let i = 0; i < views.length; ++i) {
const dims = views[i].dimensions.filter((item) => {
return map[item.name] > 1;
});
/*
At this point the dimensions with less than score 2
are removed, if this happens the view is agreggated
again, with less dimensions, removing this dimension
from the view.
*/
for (let key of Object.keys(ancestors)) {
const intersection = (ancestors[key].some((anc) => {
return views[i].dimensions.some((dim) => {
return dim.name === anc.name;
});
}));
if (intersection) {
// The first item is always the sub dimension
dims.push(ancestors[key][0]);
}
}
let coveredClauses: Clause[] = [];
let notCoveredClauses: Clause[] = [];
/*
If all dimensions in a clause are a sub set of the
dimensions of a view, this clause is apllied now,
propagating the clause to this point.
Then this clause is removed from the set of clauses
*/
for (let j = 0; j < clausesToCover.length; ++j) {
if (clausesToCover[j].isCovered(views[i].dimensions)) {
coveredClauses.push(clausesToCover[j]);
}
else {
notCoveredClauses.push(clausesToCover[j]);
}
}
clausesToCover = notCoveredClauses.filter((clause) => {
return !views[i].clauses.some((c) => c.id === clause.id);
});
// Intersection between query metrics and view metrics
const mets = q.metrics.filter((met) => {
return views[i].metrics.some((m) => m.name === met.name);
});
if (dims.length < views[i].dimensions.length || coveredClauses.length > 0) {
const partial = ViewHandler.queryReduce({
metrics: mets,
dimensions: dims,
clauses: coveredClauses.concat(views[i].clauses),
sort: q.sort
}, views[i]);
views[i] = partial;
changed = true;
}
}
}
return {
views: views,
clauses: clausesToCover
};
}
/**
* Finds the pair of views most realted in a set of views and
* applies the JOIN operation in this set.
* Returns a set with the joined view and without the most
* related view.
* @param v - Set of candidated views to be joined.
*/
private static applyJoin(v: View[]): View[] {
/*
At this point 2 views will be joined, first the
similarity with each pair of views is calculated,
the pair with the biggedt similarity will be joined.
Similarity is calculated with the number of common
dimensions in the keys.
*/
const views = v.map((i) => i);
let similarity = 0;
let idx0 = 0;
let idx1 = 1;
for (let i = 0; i < views.length; ++i) {
for (let j = i + 1 ; j < views.length; ++j) {
const pi = views[i].dimensions;
const pj = views[j].dimensions;
let score = this.similarDimensions (pi, pj);
if (similarity < score) {
similarity = score;
idx0 = i;
idx1 = j;
}
}
}
const partial0 = views[idx0];
const partial1 = views[idx1];
views.splice(idx1, 1);
views.splice(idx0, 1);
let dims = partial0.dimensions.concat(partial1.dimensions);
dims = ViewHandler.removeDuplicatedDimensions(dims);
let mets = partial0.metrics.concat(partial1.metrics);
mets = ViewHandler.removeDuplicatedMetrics(mets);
let clauses = partial0.clauses.concat(partial1.clauses);
clauses = ViewHandler.removeDuplicatedClauses(clauses);
const partialQuery: Query = {
metrics: mets,
dimensions: dims,
clauses: clauses
};
const partial = ViewHandler.queryJoin(partialQuery, [partial0, partial1]);
views.push(partial);
return views;
}
/**
* Calculates the similarity of two sets of dimensions. In other
* other how many dimensions are in both sets.
* @param a - A set of dimensions.
* @param b - Another set of dimensions.
*/
private static similarDimensions(a: Dimension[], b: Dimension[]): number {
let count = 0;
for (let i = 0; i < a.length; ++i) {
if (b.some((itemB) => a[i].name === itemB.name)) {
count++;
}
}
return count;
}
/**
* Removes repeated dimensions in a list of dimensions.
* @param candiateDims - A list of dimensions.
*/
private static removeDuplicatedDimensions(candidateDims: Dimension[]): Dimension[] {
let filterDims: { [key: string]: boolean } = {};
const dims = [];
for (let i = 0; i < candidateDims.length; ++i) {
if (!filterDims[candidateDims[i].name]) {
dims.push(candidateDims[i]);
filterDims[candidateDims[i].name] = true;
}
}
return dims;
}
/**
* Removes repeated dimensions in a list of metrics.
* @param candiateMets - A list of metrics.
*/
private static removeDuplicatedMetrics(candidateMets: Metric[]): Metric[] {
let filterMets: { [key: string]: boolean } = {};
const mets = [];
for (let i = 0; i < candidateMets.length; ++i) {
if (!filterMets[candidateMets[i].name]) {
mets.push(candidateMets[i]);
filterMets[candidateMets[i].name] = true;
}
}
return mets;
}
/**
* Removes repeated dimensions in a list of clauses.
* @param candiateClauses - A list of clauses.
*/
private static removeDuplicatedClauses(candidateClauses: Clause[]): Clause[] {
let filterClauses: { [key: string]: boolean } = {};
const clauses = [];
for (let i = 0; i < candidateClauses.length; ++i) {
if (!filterClauses[candidateClauses[i].id]) {
clauses.push(candidateClauses[i]);
filterClauses[candidateClauses[i].id] = true;
}
}
return clauses;
}
}