arXiv:1611.03736v1 [cs.DB] 10 Nov 2016

A Formal Definition for Configuration
Calvo Yanguas, M. C.

Elvira Donázar, C

Trillo Lado, R.

cacalvo@unizar.es

celvira@unizar.es

raqueltl@unizar.es

University of Zaragoza, Spain

Abstract
There exists a wide set of techniques to perform keyword-based
search over relational databases but all of them match the keywords
in the users’ queries to elements of the databases to be queried as first
step. The matching process is a time-consuming and complex task.
So, improving the performance of this task is a key issue to improve
the keyword based search on relational data sources.
In this work, we show how to model the matching process on
keyword-based search on relational databases by means of the symmetric group. Besides, how this approach reduces the search space is
explained in detail.
Keywords
Configuration, Permutation, Symmetric group, G-module, Relational
database, Keyword-based search, Keyword-based queries.

1

Introduction

In the last decade, the amount of large digital structured data available
on the Web is increasing due to the success of initiatives such as DBpedia,
Linked Open Data and Semantic Web [1]. Moreover, keyword-based search
has become the de-facto standard for searching information on the Web
since its adoption by the main web search engines, such as Google, at the
end of the 90’s. The reasons of its success are mainly its simplicity and
intuitiveness, as it does not require users searching information to know
either any formal language, such as SQL [6] or SPARQL [7], or how the
data and documents are stored.
This context has made to increase the interest in supporting keyword
search over structured databases, and, in particular, over relational databases
[9]. There exists a wide set of techniques and methods to perform keywordbased search over relational databases, classified under two main groups:
graph-based approaches and schema-based approaches [10]. Nevertheless,
1

all of them require matching the keywords in the users’ queries to elements
of the databases to be queried as first step, i.e., they require to explore what
in Keymantic [2] is defined as to find configurations of the users’ queries.
Thus, exploring possible configurations by using specific algorithms, such as
Hungarian algorithm, is required to optimize the search.
In this paper, we propose a formal definition for configurations to improve the performance of current techniques such as Keymantic. In particular, we define configurations as given types of elements of the symmetric
group, Sn , in order to establish equivalence relations among different configurations, and, therefore, in order to reduce the number of configurations to
evaluate.
Moreover, since there is a natural one to one correspondence between
the conjugacy classes of Sn and the partitions of n and there exists an order
in partitions of n, then, it is possible to order configurations.

2

Fundamental concepts

In the following, the bases to formalize the keyword based search over relational databases are described.

2.1

Keyword Search over Relational Databases

Definition 2.1 A database, D, [2] is a collection of relational tables ,
R(A1 , A2 , · · · , An ), where R is the name of the table and A1 , A2 , · · ·, An
its attributes.
Definition 2.2 The vocabulary of D, denoted by VD , is the set of all its
relation names, their attributes and their respective domains.
A database term is a member of this vocabulary VD .
A keyword query q is an ordered list of keywords {k1 , k2 , · · · , kN }. Each
keyword is a specification about the element of interest.
Definition 2.3 A configuration C of a keyword query q on a database D [2]
is an injective map from the keywords in q to database terms in the vocabulary of D.
It is made the natural assumption that each keyword can be mapped to
only one database term, not two keywords can be mapped into the same
database term and there are no unjustified keywords.
2

We must map the N keywords in a query to the |VD | database terms in
the vocabulary of D, so there are
|VD |!
(|VD | − N )!
possible configurations.
VD = {X|∃R(A1 , · · · , An )∈D s.t. X=R ∨ X=Ak ∨ X=Dom(Ak ), 1≤k≤n},
so
|VD | = 2 ∗

|D|
X

|Ri | + |D|,

i=1

with |Ri | denoting the arity of the relation Ri and |D| the number of tables
in the database.
To give a formal definition for a configuration we start by considering
the keyword query and the vocabulary of the database as sets of numbers
{1, 2, · · · , N }, {1, 2, · · · , |VD |} respectively, where N ≤ |VD |. The definition of a configuration can be interpreted as an injective correspondence
{1, 2, · · · , N } −→ {1, 2, · · · , |VD |},
that can be extended to a one to one correspondence
{1, 2, · · · , N, N + 1, · · · , |VD |} −→ {1, 2, · · · , |VD |},
that is, we define it as an element of the symmetric group S|VD | .

2.2

The Symmetric Group

Definition 2.4 The symmetric group, Sn , [8] is the set of all bijections
{1, 2, · · · , n} −→ {1, 2, · · · , n},
also called permutations, using composition as the multiplication. We multiply permutations from right to left, thus πσ is the bijection obtained by first
applying σ, followed by π.
Definition 2.5 Given π ∈ Sn and i ∈ {1, 2, · · · , n}, the elements i, π(i),
π 2 (i), · · · cannot all be distinct. Taking the first power r that π r (i) = i, we
have the r-cycle, or cycle of length r,

i, π(i), π 2 (i), · · · , π r−1 (i) .

A 1-cycle of π is called a fixedpoint.

3

Definition 2.6 Given π ∈ Sn and mk the number of its k-cycles, the cycle
type of π, or simply the type, is the expression of the form
(1m1 , 2m2 , · · · , nmn ) .
Definition 2.7 A partition of n is a sequence
λ = (λ1 , λ2 , · · · , λl )
where the λi are weakly decreasing and
|λ| def
=

l
X

λi = n.

i=1

We use the notation λ ⊢ n.
To obtain the partition of a permutation, for each mk 6= 0 in cycle type
we put mk times the value of k, starting with the biggest k and decreasing.
That is another way to give the cycle type.
We are interested in permutations in S|VD | that have only cycles of length
≤ N + 1 and with no more than a number bigger than N in each cycle,
therefore permutations in S|VD | with mN +2 = · · · = m|VD | = 0.
Definition 2.8 Elements g, h ∈ Sn are conjugates if
g = khk −1
for some k ∈ Sn . The conjugacy class of g ∈ Sn is

Kg = h ∈ G|∃k ∈ G s.t. khk −1 = g ,

the set of all elements conjugate to g.

Conjugacy is an equivalence relation in Sn . Two permutations are in the
same conjugacy class if and only if they have the same cycle type and, using
Kλ for Kg when g has type λ (see [8] for more details):
kλ def
= |Kλ | =

1m1

m1

! 2m2

n!
.
m2 ! · · · nmn mn !

Thus there is a natural one to one correspondence between partitions of n
and conjugacy classes of Sn .
4

3

Configurations as permutations

Let C be a configuration of a keyword query q = {k1 , k2 , · · · , kN } on a
database D with a vocabulary VD given by
k1 → bj1 , k2 → bj2 , · · · , kN → bjN ,
we identify it with π ∈ S|VD | given by:
• π(i) = ji for all i ≤ N ,
• for each z ≤ N with N < π(z) ≤ |VD |, we call i = π(z) and define
π(i) in order to obtain the smallest cycle containing z. For each N <
i ≤ |VD | not obtainned previously, we define π(i) = i.
Equivalently:
– For each j ≤ N such that there is no i ≤ N with π(i) = j, if
π(j), π 2 (j), · · ·, π m−1 (j) are all ≤ N but N < π m (j) ≤ |VD |, we
call i = π m (j) and define π(i) = π m+1 (j) = j obtainning a cycle
of length ≤ N + 1 in which only one value is bigger than N .
– For each N < i ≤ |VD | such that there is no j ≤ N with π(j) = i,
we define π(i) = i obtaining a fixedpoint. All this points will be
fixedpoints so, if |VD | is bigger enough (|VD | ≥ 2 ∗ N ), we will
have at least |VD | − 2 ∗ N fixedpoints.
Definition 3.1 A configuration C of a keyword query q with N keywords
on a database D with vocabulary VD is a permutation π ∈ S|VD | such that
each cycle of π contains no more than an element of value bigger than N
(1 ≤ i ≤ r).
Example 3.2 Let be a keyword query q = {k1 , k2 , k3 , k4 , k5 } and a database
D with vocabulary VD = {b1 , b2 , b3 , b4 , b5 , b6 , b7 , b8 }, then N = 5 and
8!
= 6720 configurations.
|VD | = 8 and there are (8−5)!
The configuration k1 → b4 , k2 → b7 , k3 → b6 , k4 → b1 , k5 → b3 can be
extended to the following permutation π ∈ S8 :
• π(1) = 4, π(2) = 7, π(3) = 6, π(4) = 1, π(5) = 3
• Since 2 ≤ 5 such that there is no i ≤ 5 with π(i) = 2, π(2) = 7 and
7 > 5, then π(7) = π 2 (2) = 2.
• Since 5 ≤ 5 such that there is no i ≤ 5 with π(i) = 5, π(5) = 3 with
3 ≤ 5 and π 2 (5) = π(3) = 6 with 6 > 5, then π(6) = π 3 (5) = 5.
5

• Since 8 > 5 such that there is no i ≤ 5 with π(i) = 8, then π(8) = 8.
We have a 3-cycle (3, 6, 5), two 2-cycles (1, 4), (2, 7) and a fixedpoint (8),
so the cycle notation is π = (3, 6, 5)(1, 4)(2, 7)(8).
The type is (11 , 22 , 31 , 40 , 50 , 60 , 70 , 80 ), corresponding to the partition of
8: λ = (3, 2, 2, 1).
8!
kλ = 22 ·2!·3
= 1680, so the conjugacy class of π, Kπ = Kλ , contains 1680
elements.

Note 3.3 If π ∈ S|VD | is a configuration of a keyword query q with N
keywords on a database D with vocabulary VD , the type cycle of π is
λ = (λ1 , · · · , λm , 1, · · · , 1) ⊢ |VD |,
with λi > 1 (1 ≤ i ≤ m) and
m
X

λi ≤ m + N.

i=1

Proof 3.4 Indeed, if π = c1 c2 · · · cr in cycle notation and it has k fixedpoints, the type cycle of π is λ = (λ1 , · · · , λm , 1, · · · , 1), where λi > 1
(1 ≤ i ≤ m) and r = m + k.
Since each cycle of π, ci , contains no more than an element of value bigger than N and we have |VD | − N elements bigger than N , π has at least
|VD | − N cycles. Thus r ≥ |VD | − N .
m
m
X
X
λi ≤ m + N .
λi + k, we have
Consecuently, since |VD | =
i=1

i=1

We have an equivalence relation between configurations through the conjugacy in S|VD | . In addition, this definition of configuration permits to order configurations through some orders that we can consider on partitions.
These are two important reasons why explaining configurations as elements
of the symmetric group opens up a way to explain top-k algorithms as combinatorial algorithms.

4

Matrix Representations of a Group

To stablish the orders needed to explain top-k algorithms as combinatorial
algorithms, we need some previous results about group representations that
are explained in this Section.
6

4.1

Matrix Representations and G-Modules

A matrix representation can be thought of as a way to model an abstract
group with a concrete group of matrices.
Definition 4.1 A matrix representation of a group G [8] is a group homomorphism
X : G −→ GLd ,
where d is the degree, or dimension, of the representation, denoted by degX,
GLd denotes the complex general linear group of degree d of all matrices
X = (xi,j )d×d ∈ M atd that are invertible with respect to multiplication and
M atd denotes the set of all d×d matrices with entries in the complex numbers
C.
Let G be a group and V be a vector space over the complex numbers of
finite dimension. Let GL(V ) stand for the set of all invertible linear transformations of V to itself, called the general linear group of V . If dimV = d,
then GL(V ) and GLd are isomorphic as groups.
Definition 4.2 Let V be a vector space and G be a group, then V is a
G-module if there is a group homomorphism
ρ : G −→ GL(V ).
Let G be a group of finite order n. We denote by C[G] the algebra of G
over C; this algebra has a basis indexed by elements of G and most of the
time we identify this bases with G. Each element in C[G] can be uniquely
written in the form
c1 g1 + · · · + cn gn , ci ∈ C
and multiplication in C[G] extends that in G.
Let V be a C-vectorial space and let ρ : G −→ GL(V ) be a linear
representation of G in V . For g ∈ G and v ∈ V set
g · v ≡ ρg (v).
By linearity this defines f · v for f ∈ C[G] and v ∈ V . Thus, V is endowed
with the structure of a left G-module. Conversely such structure defines a
linear representation of G in V .
An idea pervading all of science is that large structures can be understood
by breaking them up into their smallest pieces. The same thing is true in
representation theory. Some representations are built out of smaller ones,
whereas others are indivisible. This is the distinction between reducible and
irreducible representations.
7

Definition 4.3 Let V be a G-module. A submodule of V , or G-invariant
subspace, is a subspace W that is closed under the action of G, i.e.,
w ∈ W ⇒ gw ∈ W ∀g ∈ G.
Definition 4.4 A nonzero G-module V is reducible if it contains a non
trivial submodule W ; otherwise, V is said to be irreducible.
Theorem 4.5 (Maschke’s Theorem) Let G be a finite group and let V be a
nonzero G-module, then
V = W (1) ⊕ W (2) ⊕ · · · ⊕ W (k) ,
where each W (i) is an irreducible G-submodule of V .

4.2

Tableaux and Tabloids

We need something about irreducible representations of the symmetric group.
We know that the number of such representatios is equal to the number of
conjugacy classes, that is the number of partitions of n.
It may not be obvious how to associate an irreducible with each partition
λ = (λ1 , λ2 , ..., λl ) but it is easy to find a corresponding soubgroup Sλ that
is an isomorphic copy of
Sλ1 × Sλ2 × · · · × Sλl
inside Sn . So, we can produce the right number of representations by including the trivial representation on each Sλ up to Sn .
If M λ is a module for the last representation, it is not irreducible. However, we will be able to find an ordering λ(1) , λ(2) , · · · of all partitions of n
with nice properties.
To build the modules M λ first we need:
Definition 4.6 The Ferrers diagram, or shape, of λ = (λ1 , λ2 , ..., λl ) ⊢ n
is an array of n dots having l left-justified rows with row i containing λi dots
for 1 ≤ i ≤ l. The dot in row i and column j has coordinates (i, j), as in a
matrix.
Definition 4.7 A Young tableau of shape λ ⊢ n, or λ-tableau, [5] is an
array t obtained by replacing the dots of the Ferrers diagram of λ with the
numbers 1, 2, · · ·, n bijectively. Alternatively, we write sh t = λ.

8

There are n! Young tableaux for any shape λ ⊢ n.
Definition 4.8 Two λ-tableaux t1 and t2 are row equivalent,
t1 ∼ t2 ,
if corresponding rows of the two tableaux contain the same elements.
Definition 4.9 A tabloid of shape λ, or λ-tabloid, is
{t} = {t1 |t1 ∼ t},
where sh t = λ.
If λ = (λ1 , λ2 , · · · , λl ) ⊢ n, then the number of tableaux in any given
equivalence class is
λ! def
= λ1 !λ2 ! · · · λl !.
Thus the number of λ-tabloids is just
n!
.
λ!
.
Let ti,j stand for the entry of a λ-tableau t in position (i, j). Now π ∈ Sn
acts on a tableau t = (ti,j ) of shape λ ⊢ n as follows:
πt = (π(ti,j )).
This induces an action on tabloids by letting
π{t} = {πt}.
Definition 4.10 Suppose λ ⊢ n. Let
M λ = C{{t1 }, · · · , {tk }},
the permutation module corresponding to λ, where {t1 }, · · · , {tk } is a complete list of λ-tabloids.
Definition 4.11 Any G-module M is cyclic if there is a v ∈ M such that
M = CGv,
where Gv = {gv | g ∈ G}. In this case we say that M is generated by v.
9

Proposition 4.12 If λ ⊢ n, then [8] M λ is cyclic, generated by any given
λ-tabloid. In addition,
n!
dim M λ = ,
λ!
the number of λ-tabloids.
Example 4.13 Let λ = (3, 2) ⊢ 5. The Ferrers diagram, or shape, of λ is
• • •
• •
Some Young tableaux of shape λ, or a λ-tableaux, are
t=

1 3 2
,
5 4

t1 =

1 2 3
,
4 5

t2 =

1 2 4
3 5

t ∼ t1 but t1 6∼ t2 . We have 3! 2! = 12 λ-tableaux row equivalent to t1 .
A tabloid of shape λ, or λ-tabloid, is

1 2 3
1 2 3
1 3 2
1 3 2
2 1 3
{t1 } =
,
,
,
,
,
4 5
5 4
4 5
5 4
4 5
2 1 3
,
5 4
3 1 2
,
4 5
There are

5!
3! · 2!

2 3 1
2 3 1
,
,
4 5
5 4

1 2 3
3 1 2
=
5 4
4 5

3 1 2
,
4 5

3 1 2
,
5 4

= 10 λ-tabloids.

The permutation module corresponding to λ is M λ = C{{t1 }, · · · , {t10 }},
{t1 } =

1 2 3
1 2 4
1 2 5
1 3 4
, {t2 } =
, {t3 } =
, {t4 } =
,
4 5
3 5
3 4
2 5

{t5 } =

1 3 5
1 4 5
2 3 4
, {t6 } =
, {t7 } =
,
2 4
2 3
1 5

{t9 } =

2 4 5
3 4 5
, {t10 } =
1 3
1 2

{t8 } =

The action of (1, 3, 5)(2)(4) ∈ S5 on t1 is:
(1, 3, 5)(2)(4) t1 = (1, 3, 5)(2)(4)
10

1 2 3
3 2 5
=
4 5
4 1

2 3 5
1 4

and the action of (1, 3, 5)(2)(4) ∈ S5 on {t1 }:
(1, 3, 5)(2)(4) {t1 } = (1, 3, 5)(2)(4)

4.3

1 2 3
3 2 5
=
= {t8 }
4 5
4 1

Dominance and Lexicographic ordering

We consider two important orderings [8] on partitions of n.
Definition 4.14 Suppose λ = (λ1 , λ2 , · · · , λl ) and µ = (µ1 , µ2 , · · · , µm )
are partitions of n:
• λ dominates µ, written λ D µ, if
λ1 + λ2 + · · · + λi ≥ µ1 + µ2 + · · · + µi
for all i ≥ 1. If i > l (respectively, i > m), then we take λi (respectively,
µi ) to be zero.
• λ < µ in lexicographic order if, for some index i, λj = µj for j < i and
λi < µi .
The dominance order is partial and the lexicographic is total.
The lexicographic order is a refinement of the dominance order in this
sense:
Proposition 4.15 If λ, µ ⊢ n with λ D µ, then λ ≥ µ.
Intuitively, λ is greater than µ in the dominance order if the Ferrers diagram
of λ is short and fat but the one for µ is long and skinny.
Example 4.16 If we have a configuration C of q = {k1 , k2 , k3 } on a
database D with |VD | = 8, we will have λ = (λ1 , λ2 , · · · , λm , 1, · · · , 1) ⊢ 8
with 1 < λi ≤ 8 for all 1 ≤ i ≤ m and
m
X

λi ≤ 3 + m.

i=1

So, we are only interested in the partitions of 8:
(4, 1, 1, 1, 1) > (3, 2, 1, 1, 1) > (3, 1, 1, 1, 1, 1) > (2, 2, 2, 1, 1) >
> (2, 2, 1, 1, 1, 1) > (2, 1, 1, 1, 1, 1, 1) > (1, 1, 1, 1, 1, 1, 1, 1).
In dominance order:
• (4, 1, 1, 1, 1) D (3, 2, 1, 1, 1) D (3, 1, 1, 1, 1, 1).
• (2, 2, 2, 1, 1) D (2, 2, 1, 1, 1, 1) D (2, 1, 1, 1, 1, 1, 1) D (1, 1, 1, 1, 1, 1, 1, 1).
• (3, 1, 1, 1, 1, 1) and (2, 2, 2, 1, 1) are incomparables but
(3, 2, 1, 1, 1) D (2, 2, 2, 1, 1) and (3, 1, 1, 1, 1, 1) D (2, 2, 1, 1, 1, 1).
11

5

Conclusions

We have provided a formal characterization for the configurations in terms
of some elements in the symmetric group Sn . We have shown that such a
characterization allows us to reduce the number of configurations to check.
In addition, using the symmetric group it is possible to give an order
between configurations. That is an important fact because in keyword based
search we can obtain more than one configuration for the same keyword
query.
Many results about representations of the symmetric group can be used
in a purely combinatorial manner.
Some top-k works [4] uses a combinatorial algorithms, such as the Hungarian algorithm (also called Munkres assignment algorithm [3]), to give
the best answer for a for a keyword query in the context of information
search. So, since the representations of the symmetric group can be used
to obtain combinatorial algorithms, explaining configurations as a kind of
elements of the symmetric group is a first step to formalize Keymantic as a
combinatorial algorithm.

References
[1] R. Amaro, J. G. Breslin, J. Cardoso, F. Guerra, R. Trillo-Lado, and
Y. Velegrakis. Collecting and generating new ideas. Whitepaper, Keystone COST Action IC 1302, 2014.
[2] S. Bergamaschi, E. Domnori, F. Guerra, R. Trillo, and Y. Velegrakis.
Keyword search over relational databases: A metadata approach. In
Proceedings of the 2011 ACM SIGMOD International Conference on
Management of data, pages 565–576, 2011.
[3] F. Bourgeois and J. Lassalle. An extension of the munkres algorithm
for the assignment problem to rectangular matrices. Communications
of ACM, 14(12):802–804, 1971.
[4] E. Domnori and B. Hitaj. Top-k results using the hungarian algorithm.
Unpublished Manuscript. Epoka University, Tirane (Albania).
[5] W. Fulton. Young tableaux: with applications to representation theory and geometry, volume 35 of London Mathematical Society Students
Texts. Cambridge University Press, 1997. ISBN 0-521-56724-6.

12

[6] A. Leon and M. Leon. SQL: A Complete Reference. McGraw-Hill
Education (India), 1999. ISBN 9780074637081.
[7] E. Prud’hommeaux and A. Seaborne. SPARQL query language for
RDF. Recommentation, W3C, January 2008.
[8] B. E. Sagan. The Symmetric Group. Representations, Combinatorial
Algorithms, and Symmetric Funtions. Number 203 in Graduate Texts
in Mathematics. Springer Science & Business Media, 2001. ISBN 9761-4419-2869-6.
[9] J. X. Yu, L. Chang, and L. Qin. Keyword Search in Databases. Synthesis
lectures on data management. Morgan & Claypool Publishers, 2010.
ISBN 9781608451951.
[10] J. X. Yu, L. Qin, and L. Chang. Keyword search in relational databases:
A survey. IEEE Data Eng. Bull., 33(1):67–78, 2010.

13

