Introduction

Nowadays more and more companies choose to employ e-recruiting systems to automatically assign vacant job positions. Such systems allow for electronically managing the whole recruitment process, reducing the related cost. E-recruiting systems efficiency is therefore significantly affected by the efficacy of the framework underlying the match between recruiters requests and candidates profiles stored. In available skill management systems, information about candidates employment and personal data as well as certifications and competence is usually modeled through relational databases with customized and structured templates. Nevertheless, even though a Data Base Management System (DBMS) is surely suitable for storage and retrieval, relational query languages do not allow for the flexibility needed to support a discovery process as complex as recruitment. The order by statement and the min and max aggregation operators are generally used to retrieve the best tuples but, in real scenarios, there are no candidates that are better than the others ones w.r.t. every selection criteria. Moreover, if exact matches are lacking, worse alternatives must be often accepted or the original requirements have to be negotiated for compromises.

Logic-based techniques and technologies permit to make more efficient and flexible the recruitment process. The system we present here automatically performs a matchmaking process between available candidate profiles and vacant job positions according to mandatory requirements and preferences provided by a recruiter. In order to perform it, we need a language suitable for data intensive applications with a good compromise between expressiveness and computational complexity. The system performs non-exact match through top-k retrieval techniques: it uses a match engine which performs top-k queries over a DLR-lite [1] Knowledge Base (KB) providing a ranked list of candidates.

In the remaining we proceed as follows: Section 2 motivates our proposal, also by comparing it with relevant related work; Section 3 shortly recalls language and algorithms we adopted. In Section 4 the proposed system is presented with particular reference to the evaluation of its performance. Finally, conclusions close the paper.

Currently, several solutions for talent management1 and e-recruitment are available on the market. Most of them are complete enterprise suites supporting human resource management, including solutions that, even though improving the recruitment process by means of innovative media and tools, do not bring a significant novelty charge with them. Available solutions in fact exploit databases to store candidate personal and employment information, and do not ground on a logic-based structure.

One of the few logic-based solutions to recruitment and referral process is, to the best of our knowledge, STAIRS2 , a system in use at US Navy Department allowing to retrieve referral lists of best qualified candidates w.r.t. a specific mansion, according to the number of required skills they match. The commercial software supporting STAIRS is RESUMIX 3 an automated staffing tool making use of artificial intelligence techniques and adopted only as an internal tool. The system allows also to distinguish skills in required and desired ones in the query formulation: all required skills must be matched by the retrieved candidate, differently from desired ones.

We propose here a logic-based solution to recruitment process, allowing for distinguishing in required and preferred skills and exploiting a Skills Ontology, designed in (a subset of) OWL DL, to model experiences, education, certifications and abilities of candidates. The system translates a user request into a union of conjunctive queries for retrieving the best candidate to cover a given position. Hence, in order to perform a match both the user request and candidates CVs (which we generally call profiles) are defined w.r.t. the same Skills Ontology.

In order to understand the advantages of our system w.r.t. not logic-based solutions, we provide here a tiny example: imagine you are a recruiter, with the following request:"I'm looking for an expert in Artificial Intelligence with an experience of at least two years and he/she must have a doctorate". Let us suppose that there are three candidates Sarah, Paul and Bill skilled as presented in Figure 2 and that the three of them have a doctoral degree fulfilling the strict constraint of the user request. Looking both Fig. 1. Example of candidate skills at the three profile descriptions and at the original request, we will rank the three candidates as (1) Paul; (2) Bill; (3) Sarah w.r.t. the preference expressed by the user. In fact, reasonably, the skills of Paul are very close to the requested ones even if he does not fully satisfy the requested experience (in years). On the other side, since ontology and semantic technologies relate to Artificial Intelligence Bill skills seems to be more useful than Sarah ones. It is easy to see that the only way to automatically perform such a ranking is exploiting a semantic-based approach, making use of a domain ontology modeling competence hierarchies and relations. Moreover, thanks to the information modeled in the ontology, the system is able to return all scores computed for each feature of the retrieved profiles.

A relevant aspect of our work is the exploitation of classical relational database systems (RDBMS) and languages i.e., SQL, for storing the reference ontology and candidate CVs and to perform reasoning tasks. Using the system, both recruiters and candidates refers to the same model of the domain knowledge. Several approaches ( [2], [3], [4], [5]) have been presented in which databases allow users and applications to access both ontologies and other structured data in a seamless way. A possible optimization consists in caching the classification hierarchy in the database and to provide tables maintaining all the subsumption relationships between primitive concepts. Such an approach is taken in Instance Store (iS) [6], a system for reasoning over OWL KBs specifically adopted in bio and medical-informatics domains. iS is also able -by means of a hybrid reasoner/database approach-to reply to instance retrieval queries w.r.t. an ontology, given a set of axioms asserting class-instance relationships. Nevertheless, iS reduces instance retrieval to pure TBox reasoning and is able to return only exact matches (i.e., instance retrieval) whilst we use an enriched relational schema storing only the Abox (i.e., facts) in order to provide a logic-based ranked list of results and the not classified ontology. Other systems using RDBMS in order to deal with large amounts of data are QuOnto4 and Owlgres5 . They are DL-Lite reasoners providing consistency checking and conjunctive query services. Neither QuOnto nor OWLgres return a ranked list of results. SHER ( [7], [8]) is a high-scalability OWL reasoner performing both membership and conjunctive query answering by querying large relational datasets using ontologies modeled in a subset of OWL-DL which excludes nominals. It relies on an indexing technique summarizing the instances data in the database into a compact representation used for reasoning and works by selectively uncompressing portions of the summarized representation relevant for the query, in a process called refinement. Internally, SHER uses Pellet to reason over the summarized data and obtain justifications for data inconsistency. SHER allows for getting fast incomplete answers to queries, but does not provide a ranked list of results.

As hinted before, our system also allows for formulating queries by distinguishing between preferred and required skills by exploiting top-k retrieval techniques. Top-k queries [9] ensure an efficient ranking support in RDBMSs letting the system to provide only a subset of query results, according to a user-specified ordering function (which generally aggregates multiple ranking criteria).The general problem of preference handling in RDBMS in information retrieval systems [10] has been faced from two competing perspectives : quantitative-models, coping with preferences by means of utility functions [9,11] and qualitative-models, using logical formulas [12,10,13]. Various approaches using numerical ranking in combination with either the top-k model [14][15][16], the Preference SQL [17] or the Preference XPath [12] have been also devised. 3 System background: Top-k Retrieval for DLR-Lite

For computational reasons the particular logic we adopt is based on an extension of the DLR-Lite [1] Description Logic (DL) [18] without negation. DLR-Lite is different from usual DLs as it supports n-ary relations (n 1), whereas DLs support usual unary relations (called concepts) and binary relations (called roles). The DL will be used in order to define the relevant abstract concepts and relations of the application, while data is stored into a database. On the other hand, conjunctive queries will be used to describe the information needs of a user and to rank the answers according to a scoring function. The logic extends DLR-Lite by enriching it with build-in predicates. Conjunctive queries are enriched with scoring functions that allow to rank and retrieve the top-k answers, that is, we support Top-k Query Answering [19][20][21][22][23], (find top-k scored tuples satisfying query), e.g., "find candidates with excellent knowledge in DLR-Lite", where EXCELLENT is a function of the years of experience.

The query and representation language

A knowledge base K = F, O consists of a facts component F and an Ontology component (also called, DL component) O, which are defined below.

Facts Component. F is a finite set of expressions of the form R(c 1 , . . . , c n ) , where R is an n-ary relation, every c i is a constant. For each R, we represent the facts R(c 1 , . . . , c n ) in F by means of a relational n-ary table T R , containing the records c 1 , . . . , c n . Fig. 2 shows an example of facts about Curricula Vitae stored into the Profile relation.

Ontology Component. The ontology component is used to define the relevant abstract concepts and relations of the application domain by means of axioms. But, before we address the syntax of axioms, let us introduce the notion of concrete domains. In fact, Top-k DLR-Lite supports concrete domains with specific predicates on it. The allowed concrete predicates are relational predicates such as ([i] 1500) (e.g., the value of the i-th column is less or equal than 1500) and ([i] = "M ayer ) (e.g., the value of the i-th column is equal to the string "Mayer"). Formally, a concrete domain in is a pair where m 1, all Rl i and Rr have the same arity and where each Rl i is a so-called lefthand relation and Rr is a right-hand relation. As illustrative purpose, a simple ontology axiom may be of the form AjaxProgrammer WebProgrammer with informal reading "any AJAX programmer is also a Web programmer". In such an axiom, AjaxProgrammer and WebProgrammer are unary relations with signature AjaxProgrammer(id) and WebProgrammer(id), respectively. But we may also involve n-ary realtions in ontology axioms. For instance, suppose that from the profiles records, we would like to extract just the profile ID and the last name, and call this new relation HasLastName with signature HasLastName(profID, LastName). In database terminology this amounts in a projection of the Profile relation on the first and third column. In our language, the projection of an n-ary relation R on the columns i 1 , . . . , i k (1 i 1 , i 2 , . . . , i k n, 1 i n), will be indicated with ∃[i 1 , . . . , i k ]R. Hence, e.g., ∃[1, 3]Profileis the binary relation that is the projection on the first and third column of the Profile relation. So, for instance, the axiom

∆ D , Φ D ,∃[1, 3]Profile ∃[1, 2]HasLastName

states that the relation HasLastName contains the projection of the Profile relation on the first and third column. In case of a projection, we may further restrict it according to some conditions, using concrete predicates. For instance, ∃[1, 5]Profile.(([5] 1979)) corresponds to the set of tuples profID, BirthDate such that the fifth column of the relation Profile, i.e., the person's birth date, is equal or greater than 1979. The exact syntax of the relations appearing on the letf-hand and right-hand side of ontology axioms is specified below (where h 1):

Rr −→ A | ∃[i1, . . . , i k ]R Rl −→ A | ∃[i 1 , . . . , i k ]R | ∃[i1, . . . , i k ]R.(Cond1 . . . Cond h ) Cond −→ ([i] v) | ([i] < v) | ([i] v) | ([i] > v) | ([i] = v) | ([i] = v)

where A is an atomic concept, R is an n-ary relation with 1 i 1 , i 2 , . . . , i k n, 1 i n and v is a value of the concrete interpretation domain of the appropriate type.

Here ∃[i 1 , . . . , i k ]R is the projection of the relation R on the columns i 1 , . . . , i k (the order of the indexes matters). Hence, ∃[i 1 , . . . , i k ]R has arity k.

On the other hand, ∃[i 1 , . . . , i k ]R.(Cond 1 . . . Cond l ) further restricts the projection ∃[i 1 , . . . , i k ]R according to the conditions specified in Cond i . For instance, ([i] v) specifies that the values of the i-th column have to be less or equal than the value v.

Query language. Concerning queries, a query consists of a "conjunctive query", with a scoring function to rank the answers. A query is of the form

q(x)[s] ← ∃y R 1 (z 1 ), . . . , R l (z l ), OrderBy(s = f (p 1 (z 1 ), . . . , p h (z h ))(1)

where 1. q is an n-ary relation, every R i is an n i -ary relation,

2.

x are the n distinguished variables; 3. y are so-called non-distinguished variables and are distinct from the variables in x; 4. z i , z j are tuples of constants or variables in x or y. Any variable in x occurs in some z i . Any variable in z j occurs in some z i .; 5. p j is an n j -ary fuzzy predicate assigning to each n j -ary tuple c j a score p j (c j ) ∈ [0, 1] m . Such predicates are called expensive predicates in [24] as the score is not pre-computed off-line, but is computed on query execution. We require that an n-ary fuzzy predicate p is safe, that is, there is not an m-ary fuzzy predicate p such that m < n and p = p . Informally, all parameters are needed in the definition of p;

6. f is a scoring function f : ([0, 1] m ) h → [0, 1] m ,

which combines the scores of the h fuzzy predicates p j (c j ) into an overall score to be assigned to the rule head q(c).

We assume that f is monotone, that is, for each

v, v ∈ ([0, 1] m ) h such that v v , it holds f (v) f (v ), where (v 1 , . . . , v h ) (v 1 , . . . , v h ) iff v i v i for all i. 7.

We also assume that the computational cost of f and all fuzzy predicates p i is bounded by a constant.

Finally, a disjunctive query q is, as usual, a finite set of conjunctive queries in which all the rules have the same head. We omit to write ∃y when y is clear from the context. R i (z i ) may also be a concrete unary predicate of the form

(z v), (z < v), (z v), (z > v), (z = v), (z = v),

where z is a variable, v is a value of the appropriate concrete domain. We call q(x)[s] its head, ∃y.R 1 (z 1 ), . . . , R l (z l ), OrderBy(. . .) its body and OrderBy(. . .) the scoring atom.

Top-k Retrieval. Given a knowledge base K, and a disjunctive query q, retrieve k tuples c, s that instantiate the query relation q with maximal score (if k such tuples exist), and rank them in decreasing order relative to the score s, denoted

ans k (K, q) = Top k ans(K, q) .

From a query answering point of view, it extends the DL-Lite/DLR-Lite reasoning method [1] to the fuzzy case. The algorithm is an extension of the one described in [1, 20,22]). Roughly, given a query q(x)[s]← ∃yφ(x, y), 1. by considering O, the user query q is reformulated into a set of conjunctive queries r(q, O). Informally, the basic idea is that the reformulation procedure closely resembles a top-down resolution procedure for logic programming, where each axiom is seen as a logic programming rule. 2. from the set of reformulated queries r(q, O) we remove redundant queries; 3. the reformulated queries q ∈ r(q, O) are translated to ranked SQL queries and evaluated. The query evaluation of each ranked SQL query returns the top-k answer set for that query. Specifically, we use the RankSQL [14] system for this purpose; 4. all the n = |r(q, O)| top-k answer sets have to be merged into the unique top-k answer set ans k (K, q). As k • n may be large, we apply a Disjunctive Threshold Algorithm (DTA, see e.g., [22]) to merge all the answer sets.

The detailed description of the algorithm embedded in our system to solve top-k retrieval problem is beyond the scope of this work. The algorithm is an extension of the one described in [1, 20,22]) and has been implemented as part of the SoftFacts system6 .

The proposed system has been implemented by plugging the Top-K DLR-Lite retrieval approach into I.M.P.A.K.T. [25], a system for skills and knowledge management developed by Data Over Ontological Models s.r.l. 7 as a commercial solution implementing to some extent the skill matching framework designed in [26]. The efficiency and scalability of the approach has been tested using the skill ontology underlying I.M.P.A.K.T.. Both requests and candidate profiles have been modeled w.r.t. to this ontology containing 2594 relations, both unary (classes) and n-ary ones, and 5119 axioms. The main structure of the ontology is depicted in Figure 3. Level represents profile education such as certifications, masters, doctorate, etc.; Knowledge represents technical skill and specific competences of the candidate; Com-plementarySkill represents abilities and hobbies of the candidate; JobTitle represents work experiences of the candidate; Industry representing sectors (institutes, research laboratories, companies, etc.) in which candidate works/worked; Language represents the knowledge of foreign languages. Data properties, have been used to represent years of experience, degree final mark and knowledge level of foreign languages.

The system exploits the user interface of I.M.P.A.K.T., shown in Figure 4. Panels (a), (b) and (d) allow the recruiter to compose her semantic-based request. In fact, in menu (a) all the entry points are listed whilst panel (b) allows to search for ontology concepts according to their meaning and section (d) enables the user to explore both taxonomy and properties of a selected concept. Entry points in menu (a) represent, to some extent, the main classes and relations represented in Figure 3. Once an item is selected in panel (d), the corresponding panel, representing the item itself, is dynamically filled Fig. 4. Query composition GUI and added to panel (e). This latter enumerates all the requested features in the query. For each of them, the GUI of I.M.P.A.K.T. allows: (1) to define if the feature is strict (crisp) or negotiable (fuzzy); (2) to delete the whole feature; (3) to complete the description showing all the elements (concepts, object properties and data properties) that could be added to the selected feature; (4) to edit each feature piece as well as existing data properties. Finally, panel (c) enables searches like "I'm searching a candidate like John Doe" i.e., it is useful to model all those situations where you are looking for a candidate whose skills and knowledge are similar to the ones of John Doe. In this case, the job-seeker fills first and/or last name field of the known candidate and the system consider her/his profile as starting request. The user can view the query -automatically generated-and eventually she can edit it before starting a new search.

In the experiments we carried out, we considered 100.000 automatically generated CVs and stored them into a database having 17 relational tables. In Figure 4 we show the ontology axioms mapping the relational tables involved in the proposed queries, in order to provide the reader with the alphabet of the query language. Each axiom renames with the role name given as first parameter the table defined as second parameter with all its fields. We build several queries, with/without scoring atom and submitted them to the system, with different values for k in case of top-k retrieval (k ∈ {1, 10}). We run the experiments using the top-k retrieval SoftFacts system as back-end. No indexes have been used for the facts in the relational database. The concept and role hierarchy -overall, the response time is quite good (almost fraction of second) taking into account the non negligible size of the ontology, the number of CVs and that we did not consider any index for the relational tables; -if the answer set is large, e.g., query 1, then there is a significant drop in response time, for the top-k case; -for each query, the response time is increasing while we increase the number of retrieved records.

CONCLUSION AND FUTURE WORK

We presented an innovative and scalable logic-based system for efficiently managing skills and experiences of candidates in the e-recruitment field. The system grounds on a Skill Ontology in order to return a ranked list of profiles and on scoring functions in order to weight each feature of the retrieved profiles. Differently from existing recruitment systems, our approach allows to express a user request as the composition of both mandatory requirements and preferences, by means of top-k retrieval techniques. The implemented retrieval framework was embedded into an existing system for skill management and experiments conduced on a preliminary profiles dataset show a satisfiable behavior. Future work aims at evaluating system performance on several datasets and at providing user-friendly explanation facilities to better clarify scores of obtained results.