Kristína Machová
email: kristina.machova@tuke.sk

Lukáš Marhefka
email: lukas.marhefka@student.tuke.sk

Opinion Mining in Conversational Content within Web Discussions and Commentaries

Keywords: Opinion mining, conversational content, opinion classification, dynamic coefficient, n-grams

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The social web or web with various forms of conversational content increases interactions between users. These interactions are provided in the form of "point-topoint" or "multicast" on-line web services, as chats, discussion forums, IRC (Internet Relay Chat), blog and micro-blog platforms and so on. These services create a big amount of text and therefore they offer interesting possibilities for research in the field of opinion classification.

Where are some interactions, there people influence each other. This influence concerns decision making about various life situations, for example decisions about purchase or production and selling some products, decisions about voting political representatives and so on. This decision making can be supported by information mining from web discussions, reviews, conversations about matter of our interest. Thus, our decision processes can be encouraged by web conversational content. The mentioned conversational content can provide us also with cultural information about films, books and cultural events. On the other hand, it can be a source of some information connected with safety issues, for example suspicious activities or characters, connected with racism, pedophilia or terrorism.

But sometimes these web discussions can be too long and some parts of these discussions can be less informative. That is why there is a need of some tools for automatic analysis of web discussions from the point of positivity or negativity. Our implementation of various methods of opinion analysis provides one such tool.

An opinion represents some positive or negative attitude, view, approach, or emotion of some person -an opinion owner. Opinions are related to a given entity or some of its parts. The entity is some product, person, event, organization, etc. It is the object, we are talking about. It is composed from components. The entity can be some product, for example a mobile. It has some parts -attributes, for example display, design and size, functionalities and so on.

There can be identified a set of different tasks within the field of the opinion analysis:

emotion detection (Does the conversation obtain some emotion?) opinion spam detection (Is the content of some discussion contribution informative?) subjectivity analysis (Does the conversation obtain subjective opinion?) opinion polarity classification (Is the conversation about given subject positive or negative?) theme modeling (What is the theme/object of this conversation? Is this theme a suspicious one?) authorship identification (Who is the opinion author? What kind of person is the author of a given contribution?)

Our approach, presented within this paper, is focused on the problem of opinion polarity classification, shortly on opinion classification.

Related Works

There are some approaches similar to our approach to opinion classification [START_REF] Choi | Learning with Compositional Semantics as Structural Inference for Subsentential Sentiment Analysis[END_REF], [START_REF] Taboada | Lexicon-Based Methods for Sentiment Analysis[END_REF], and [START_REF] Thelwall | Sentiment Strength Detection in Short Informal Text[END_REF]. New technical contribution of our approach in comparison with existing works will be discussed within this section. The most similar to our approach is Taboada at al: "Lexicon-Based Methods for Sentiment Analysis" in [START_REF] Taboada | Lexicon-Based Methods for Sentiment Analysis[END_REF]. It uses a dictionary of words annotated with their orientation (polarity). This approach splits the dictionary into more sub-dictionaries according to word classes (adjectives, nouns, verbs and adverbs). We use only one dictionary (for dynamic coefficient) or two dictionaries (for n-grams). The novelty of our approach is, that the dictionary is generated directly from web discussions, which increases the precision of opinion analysis of the given discussions. In [START_REF] Taboada | Lexicon-Based Methods for Sentiment Analysis[END_REF], intensification is provided by increasing (respectively decreasing) the semantic intensity of neighboring lexical items using a special dictionary of intensifiers. Our approach is more flexible because an intensifier and the related word need not to be neighbors. They can take any position within one lexical unit, while their distance is limited by the given dynamic coefficient. The intensifier can be located before or after the related word. Within our approach, not only intensification, but also negation processing is different, based on processing various combinations of words (lexical units) defined with the aid of dynamic coefficient. All lexical units are sequentially classified into six categories (3, 2, 1, -1, -2, -3). Three of them represents positive polarity and the other three categories negative polarity (with meaning: strong + intensifier, strong or gentle).

Another approach presented in Thelwall at al: "Sentiment strength detection in short informal text" [START_REF] Thelwall | Sentiment Strength Detection in Short Informal Text[END_REF] is focused on the SentiStrength detection algorithm, which solves some problems connected with sentiment analysis (generation of the sentiment strength list, optimization of the sentiment word strengths, allocation of the miss words, spelling correction, creation of the booster word list, the negating word list and emoticon list, repeated letters processing and ignoring negative emotion in questions). They devote more effort to correction of non-standard spelling in informal texts. Our approach is not aiming at correct spelling of contributions since the dictionary can easily accommodate some misspelled words as well. Within our approach, the dictionary is generated directly from the analysed discussion and therefore words with sentiment are accepted in spite of common mistakes (for example very common typo using "y" instead of "i" and vice versa in the Slovak language). The algorithm described in [START_REF] Thelwall | Sentiment Strength Detection in Short Informal Text[END_REF] was tested on data from MySpace and on wide variety of themes. We have provided our tests on data from narrow domains and therefore our results were a little bit better.

Paper "Learning with compositional semantics as structural inference for substantial sentiment analysis" [START_REF] Choi | Learning with Compositional Semantics as Structural Inference for Subsentential Sentiment Analysis[END_REF] written by Choi and Cardie is focused on sentiment analysis similarly to our approach. It presents a novel learning based approach that incorporates inference rules inspired by compositional semantics into the learning procedure. Our approach differs from this work because our method is dictionary based (we use simple bag-of-word approach) and it is not machine learning oriented. Our method incorporates surrounding of processed word up to distance K (maximally K neighboring words from the given word). Design of the method in [START_REF] Choi | Learning with Compositional Semantics as Structural Inference for Subsentential Sentiment Analysis[END_REF] represents meaning of a composed expression as a function of the meanings of its parts within the compositional semantics. In our approach, these parts are lexical units, lengths and number of which are defined by the dynamic coefficient. The approach presented in [START_REF] Choi | Learning with Compositional Semantics as Structural Inference for Subsentential Sentiment Analysis[END_REF] processes negations and intensification separately. This processing is made over the whole text with the aid of "voting-based inference". In our approach, the negation and intensifications are processed by the same mechanism of using dynamic coefficient. This processing is made separately in each lexical unit, not as the majority vote. Our approach does not use natural language processing. It is based on some statistical principles and so it better processes longer texts, which contain more than one sentence and very short texts (one sentence) can be analyzed with lower precision.

The machine learning approaches (Naïve Bayes classifier, Support Vector Machines (SVM) and Maximal Entropy) were used in [START_REF] Go | Twitter Sentiment Classification using Distant Supervision[END_REF], which is focused on the automatic classification of opinions from the micro-blog service Twitter. Within [START_REF] Go | Twitter Sentiment Classification using Distant Supervision[END_REF] the input data for SVM are represented by vectors with dimension m. Each item of this vector represents an attribute in the tweet. They used unigram extractor and so each attribute is one word. If this word is presented in the tweet, then its value in the vector is 1. Otherwise its value is 0. This substitution of the frequency of the given word occurrence by simple presence function leads to speedup of a tweet processing.

Sometimes, the introduced opinion analysis is denoted as opinion mining, because it focuses on the extraction of positive or negative attitude of a participant to the commented objects with the aid of mining techniques applied to text documents.

Opinion mining can be extended from the level of whole texts perception to the level of extraction of properties of those objects which match users' interests [START_REF] Ding | Holistic Lexicon-Based Approach to Opinion Mining[END_REF]. Parallel approach to opinion mining is sentiment analysis [START_REF] Pang | Opinion Mining and Sentiment Analysis[END_REF]. Deeper view on sentiment analysis, which is presented in [START_REF] Koncz | An Approach to Feature Selection for Sentiment Analysis[END_REF], focuses on feature selection. Different approach to web discussion processing is represented by the estimation of authority degree of some information sources, for example of actors contributing to discussion forums or social networkss. An important technique for authoritative actors searching is visualization approach, which is introduced in [START_REF] Heer | Vizster: Visualizing Online Social Networks[END_REF]. Some effort was spent on semantically enriching algorithms for analysis of web discussion contributions by authors of [START_REF] Lukáč | Semantically-enhanced Extension of the Discussion Analysis Algorithm in SAKE[END_REF]. Also dedicated information can be used as an interface to newsgroup discussions [START_REF] Mach | A Dedicated Information Collection as an Interface to Newsgroup Discussions[END_REF].

Nowadays, opinion analysis has become an important part of social networks analysis. Existing opinion analysis systems use large vocabularies for opinion classification into positive or negative answer categories. Such approach was used in [START_REF] Catena | Opinion Analysis of Publications on Economics with a Limited Vocabulary of Sentiments[END_REF]. Authors studied accuracy of the opinion analysis of Spanish documents originated in the field of economic. This approach uses a regression model for classification into negative or positive opinions. Authors studied how quality depends on the granularity of opinions and rules, which were used in the regression model. Another study [START_REF] Kaurova | The Study of Sentiment Word Granularity for Opinion Analysis (a Comparison with Maite Taboada Works)[END_REF] was focused on the possibility of using lesser granularity without any significant precision decrease. The results of this study show no substantial difference between one and two parameter regression models as well as no statistically significant difference between models with different granularity. Thus, for example, simpler models can be used with the sentiment scale reduced to five degrees only. The approach, presented in this paper, uses a scale with five degrees for opinion classification as well, but it differs from the previous approaches in vocabulary cardinality. Our work focuses on creating vocabularies with strong orientation on the discussion domain, not so large but created directly from live discussions. We do not use regression models.

Opinion Mining

The process of the opinion classification consists of minimally two subtasks:

1. input text preprocessing or transformation of discussion texts into lexical units which can be easily processed, 2. opinion classification, which represents determination (calculation) of the polarity (positive or negative) of a subjective opinion.

Input Text Preprocessing

There are several approaches how to parse an analyzed input text into smaller lexical units. The most used approaches are n-grams and part-of-speech tagging. N-gram can be defined as a series of items from some sequence. From the semantic point of view, it can be a sequence of phones, characters or words. In practice, n-gram as a sequence of words is the most common. The sequence of two (three) words is called bigram (trigram). For the case, when more than three words (exactly n) are in the same sequence, such sequence is called n-gram. N-grams are used in the wide scale of fields, as theoretical mathematics, biology, cartography, even in the field of music.

In the field of natural language processing, n-grams can be used for words prediction. The words prediction uses so called "n-grams model". This n-gram model calculates the probability of occurrence of the last word in an n-gram from the previous n-grams. Another way of using n-grams is plagiarism discovery by text dividing into smaller fragments. These fragments are represented by n-grams. These n-grams can be easily compared and consequently, the measure of similarity of comparing documents can be calculated. N-grams are often used for text categorization and also for effective searching for correct candidates of misspelled words. Our approach, presented within this contribution uses n-grams for splitting the web discussion contributions into lexical units.

The part-of-speech (POS) tagging represents the recognition of word class within the text on the basis of the given language attributes and relationships between word classes. The POS tagger is a program, which is able to read text and to assign word class to each word from the given text. Such word class assigning can be based on the word definition or the word position within the sentence. There are three types of POS taggers: rule taggers, stochastic taggers and transformation taggers. The rule tagging algorithms are based on sets of rules, which are used for tagging of the processed text. This tagged text can be used as a training set for stochastic approach. The stochastic taggers are based on probability of the given tag occurrence within the given text. The stochastic approach requires an input training set. The last one, transformation taggers represent combination of two previous approaches.

Opinion Classification

There are two basic approaches to opinion classification [START_REF] Taboada | Lexicon-Based Methods for Sentiment Analysis[END_REF]: machine learning approach (classification based approach), which uses the statistical and machine learning methods lexicon based approach, which can be based on the dictionary (dictionary based approach) or corpus.

Machine Learning Approach. This approach is based on using some of well-known methods of machine learning, for example Naïve Bayes classifier, Support Vector Machines (SVM) and Maximal Entropy and so on.

Naïve Bayes is a simple classifier based on Bayes formula of conditional probability with the big degree of freedom. A problem is defined as a classification of a given tweet d to a class c. This class c represents positive or negative polarity of some contribution. The original Bayes theorem in the formula (1) [START_REF] Catena | Opinion Analysis of Publications on Economics with a Limited Vocabulary of Sentiments[END_REF] was modified taking into account the following fact: the probability of a tweet occurrence is 100% and so probability p(d|c) was replaced by probability of feature f i in the class c. The final Bayes formula for conversational content is following (2) .

(2)

Maximal Entropy. Within the information theory, the entropy represents a measure of indeterminism. The principle of maximal entropy is an axiom of the Bayes probability theory. It states that the probability distribution, which can represent current state of knowledge in the best way, is the distribution with the highest information entropy. This model is described by the following formula (3) .

(3) Within this formula: c is positive (negative) class, d is a tweet and is a weighting vector. The weighting vector represents an importance of the given feature F for the given class assignment (usually the word with strong positive meaning). The weighting vector is set on the base of numerical optimization of its components by the maximization of conditional probabilities. The classification was provided by Standford classifier [13].

Support Vector Machines (SVM) is the groups of machine learning classification methods. The difference between the SVM and Perceptron is that SVM can be also used for nonlinear classification.

Dictionary Based Approach. This approach looks on the input text as a set of words. It does not take into account relationships between words within sentences or grammatical rules. Not every word has the same importance in the opinion classification. It is important to find within the processed text mainly words, which can express opinion in the best way. Such words are stored in the classification dictionary. The dictionary has to obtain some words with sentiment before starting the process of opinion classification. On the base of known polarity of such characteristic words, polarity of whole texts from conversation and finally polarity of the whole web discussion can be determined.

The classification dictionary is a database of words. These words are descriptors with marked influence on polarity determination, mainly adjectives, adverbs, nouns and verbs. The simplest dictionaries are the dictionaries which enable binary classification. More suitable are fuzzy dictionaries, which are able to determine not only polarity but also the strength of the polarity. Such dictionary can be created for only a given application or some known lexicons can be used, for example Word Net, WordNet-Affect, SenticNet, SentiWordNet and so on.

Each dictionary should contain words, which are common within web conversation forums, blogs, commentaries and so on including slang words, words without diacritics and words with more common grammatical mistakes. Our approach, presented within this contribution is the dictionary based approach.

Negation and Intensification

Besides basic problems of opinion analysis as word subjectivity identification, word polarity (orientation) determination and determination of intensity of the polarity, each application of opinion classification has to solve the processing of negation and intensification. The basic problems can be simply solved with the aid of classification dictionaries. These dictionaries focus on those words, which are able to express subjectivity very well -mainly adjectives (e.g. 'extraordinary') and adverbs (e.g. 'awfully') are considered. On the other hand, other word classes must be considered as well in order to achieve satisfactory precision, for example nouns (e.g. 'crash') or verbs (e.g. 'damage'). The words with subjectivity are important for opinion classification. Therefore, they are identified and inserted into one vocabulary or into a set of vocabularies -one vocabulary for each word class (adjectives dictionary, adverbs dictionary, nouns dictionary and verbs dictionary). Words with subjectivity are inserted into the corresponding vocabulary together with their degree of polarity. The majority of opinion classification applications work with 5 to 10 degrees of polarity.

Negation Processing

There are many approaches to negation processing: Switch negation, Shift negation, Dynamic coefficient usage.

The switch negation is simply reversion of the polarity of the lexical item. The reversion represents changing the number sign of the polarity degree (from minus to plus and vice versa). There are many various words related to negation that need to be taken into account: not, none, never, nothing, which usually are situated next to a related word -item. But also other negations should be taken into account as without, don't, lack and so on, which can be situated in significant distance from the lexical item. These negations can be hardly processed by switch negation. What is more, switch negation can be insufficiently precise, because negation of a strong positive word rarely is a strong negative word and vice versa. More often the negation of a strong positive word is a slightly negative word and vice versa.

The shift negation focuses on the case, when negation of a strong positive (negative) word is not strong negative (positive). Instead of changing the sign, "shift negation" shifts polarity degree toward the opposite polarity by a fixed value. For example, if the shift value is "6", then negation can be calculated in the following way: "It is not completely dysfunctional (-5 + 6 = +1) but also not very useful (+5 -6 = -1)."

The dynamic coefficient usage does not need to suppose that all negation words are situated next to related words -items. In this method, the text of conversation is divided into lexical units of the length given by dynamic coefficient. It does not matter how far the negation is from the related word within the same lexical unit. One sentence can be transformed into one or more lexical units.

Intensification

There are two different approaches to intensification:

Dictionary based intensification, Intensification based on dynamic coefficient.

The dictionary based intensification supposes the dictionary of intensificationswords, which are able to increase (or decrease) the intensity of polarity. Each of intensifications should be stored in dictionary together with sign and number. This number can represent a percentage of changing of polarity intensity and sign represents the type of this change. This approach supposes that a lexical item is situated next to intensifier changing the polarity degree. This condition is fulfilled only in small number of cases.

The intensification based on dynamic coefficient does not suppose that a lexical item is situated next to intensifier changing the polarity degree. This kind of intensification does not depend on how far the negation is from the related word within the same lexical unit.

Our implementation uses dynamic coefficient for negation processing and also for intensification.

Dynamic Coefficient in Opinion Classification

First, a simple version of Opinion Classification Application (OCA) has been designed and implemented. This OCA represented the dictionary based approach to opinion classification with "static coefficient", which was defined by user as the parameter of the application. This static coefficient designates the length of a lexical unit (number of words from the text, which belong to one lexical unit) for processing within textscontributions of discussion forums. This processing represents the classification to positive or negative opinions. The OCA solves basic problems of opinion classification (words with subjectivity identification, words polarity determination and polarity intensity determination) but also problems connected with word polarity reversion by negation and intensification of words. The solving of these problems desire to process a combination of words instead of separated words. A length of processed word combination can be represented by the static coefficient, but also by a dynamic coefficient.

The value of the "dynamic coefficient" K is being dynamically changed during processing of different lexical units. The dynamic coefficient adapts itself to the length of a lexical unit (sequence of words) under investigation. The value K represents the number of words, which are included into the same word combination. In the case, when the value is higher than the number of words in the sentence, this value is dynamically decreased in order to ensure, that the combination contains only words from the investigated sentence, not from the beginning of the next sentence.

Three ways of the dynamic coefficient setting have been proposed. Before the process of opinion classification can start, user has to select one of the methods for coefficient determination, as it is illustrated in Fig 1. The first used way of dynamic coefficient setting is the calculation of the average length of all sentences of the discussion contribution text, which is analyzed. So, each contribution text from a live discussion can have the different value of the dynamic coefficient. The calculated value of the dynamic coefficient is used for processing of all sentences of the given contribution. Thus, each sentence of the same contribution is processed using the same value of the dynamic coefficient, although actual length of these sentences is different.

The second used way of dynamic coefficient setting is the calculation of the half length of each sentence of the discussion contribution text. If needed, the calculated value is rounded up. Each analyzed sentence is processed using a different value of the dynamic coefficient.

The last used way is the hybrid approach, which determines the value of the dynamic coefficient as an average of two values obtained from Average length of all sentences method and Half length of each sentence method, respectively.

N-grams Application to Opinion Classification

Our n-grams application to opinion classification belongs to dictionary approach. This application is oriented on the Slovak language, so it uses a dictionary of Slovak language words. The structure of this dictionary is given by four more important word classes for opinion analysis: adjectives, adverbs, nouns and verbs. The dictionary consists of two different parts. The first part contains adjectives, nouns and verbs. The second one contains adverbs and negations. The first part of the dictionary is used for solving basic problems of opinion classification. The second part of the dictionary is used for negation processing and intensification because the adverbs have in a language the function to increase ("surprisingly nice") or to decrease ("extremely low-class") intensity of a word polarity. The dictionary contains also some emoticons, which naturally can express emotions and opinions very well. Sometimes, the text analysis can be less clear and so emoticons can increase the precision of the classification. These emoticons are stored within the first part of the dictionary.

All words and emoticons from this first dictionary are quantified to polarity degree within the interval from -3 to 3. With respect to the second part of dictionary, intensifiers (adverbs) are assigned by value from -0.5 to 1 and negations are represented by value -2. The analyzed text is processed by the following way. All words from a text are compared with all words in the first dictionary, and in the case of match, the value of the word found in the dictionary is added into the overall sum of values of analyzed words. This sum is consequently multiplied by the second sum of values obtained from the second dictionary (for intensifiers and negations). This processing can be represented by formula (4)

P = ∑ v(w i 1 )[1+∑ v(w j 2 )] . (4)
Within this formula: P …is the polarity degree of analyzed text v(w i 1 ) …is the value of word w i of text found in the first part of the dictionary v(w j 2 ) …is the value of word w j of text found in the second part of the dictionary.

For example: the lexical unit "The chair was comfortable but dirty and its color was awful." is processed by the following way: comfortable (+1) + dirty (-3) + awful (-1): P = -3 the lexical unit "It is not good idea." is processed by the following way: good (+1) first dictionary, not (-2) second dictionary: P = 1*[1+(-2)] = -1 the lexical unit "The text processing is very decent." is processed by the following way: decent (+1) first dictionary, very (+1) second dictionary: P

= 1*[1+1)] = +2.
The question is, how long the length of processed lexical unit should be. We decided to represent the lexical units by n-grams. The value of n was fixed on 4 in an experimental way. Shorter value of n can separate negation or intensifier from related word. Consequently, we have designed new versions of n-gram approach. The first version has created 4-grams applying shift by one position. Another one was based on comparison of polarity value obtained by 4-grams and polarity value obtained by1grams.

Evaluation and Testing

The implementations of various versions of opinion classification were tested within several experiments.

First, the basic version with static coefficient (called "Static coefficient" in Table 1) was tested on the set of discussion contributions from the portal http://www.mobilmania.sk (a discussion thread related to reviews of the LGKU990 mobile telephone). This set of contributions contained 1558 words within 236 lexical units and the used classification dictionary had 27 positive words, 27 negative words, 10 negations and 11 intensifications. The resulting precision of these tests was 0.78, which was an average calculated from precision of positive contributions classification (higher value 0.86) and precision of negative ones (lower value 0.69).

The next versions were the version using the dynamic coefficient, which was set as an average length of each sentence (called "Dynamic coefficient 1" in the Table 1), the version using the dynamic coefficient determined as half length of each sentence (called "Dynamic coefficient 2" in the Table 1) and the version using the hybrid approach (called "Hybrid" in the Table 1) were tested on 50 reviews (25 positive reviews and 25 negative ones) obtained from the page http://recenzie.sme.sk. The classification dictionary contained 150 words in all categories (positive words, negative words, negations and intensifications). The results of negative contributions classification were surprisingly high as can be seen in Table 1 (0.84, 0.88 and 0.84)higher than precision of positive contributions classification (0.76, 0.80 and 0.80). It may be caused by the fact, that the number of negative contributions was the same as the number of positive ones. Usually, the precision of negative contributions is lower because the number of available negative contributions is fairly lower.

Lastly, the version based on n-grams was tested in two independent experiments (called "n-grams 1 and n-grams 2" in Table 1). The first experiment was performed on a set of 42 contributions with 2350 words. These contributions were extracted from discussion forums available on http://www.mojandroid.sk (a discussion thread related to reviews of the mobile telephones HTC One X and HCT One S) and http://www.pocitace.sme.sk (a discussion thread related to reviews of two products Asus Transformer Prime TF201 and Asus Transformer Pad TF300T). The second experiment (n-grams 2) was performed on a set of 71 contributions (4341 words) from the portal http://tech.sme.sk (a discussion thread related to reviews of the telephone Samsung Galaxy S4) and from the portal http://www.mojandroid.sk (a discussion thread related to reviews of the telephones HTC ONE and Samsung Galaxy S4). These two tests of n-grams application were provided using classification dictionary with 44 positive words, 46 negative words, 3 kinds of negations and 10 intensifications. The achieved precision of classification of positive contributions in the first experiment (N-grams 1) was quite satisfactory (0.83) but in the second experiment (N-grams 2) was not very high (0.76). A different situation was in the case of negative contributions classification. The achieved precision in the first experiment was only 0.57 and in the second experiment even worse 0.42, what is very low value. Maybe, an extremely low number of available negative contributions within these two last experiments was the cause of such disappointed results. The best average precision was achieved by three implementation versions using the dynamic coefficient. These results are interesting, because these versions had better results for processing negative contributions than for processing positive contributions. This fact is not common within the existing opinion classification applications. Usually, a processing of negative contributions is less precise. The basic version using static coefficient and version based on n-grams are more common from this point of view, because they achieved lower precision within negative contributions while they had quite high precision within positive contributions processing. The higher value of precision than 0.80 (80 percentage) seems to be very good in comparison with the average precision of human advices (about 70 percentage). An important factor is also the language which is used to present the classified opinions. Although languages have some similar features, the complexity of the task is evaluated on the basis of the emergent expression of the given particular language. Our modified application achieves relatively better results -higher precision (0.84, 0.82 using dynamic coefficient) against [START_REF] Taboada | Lexicon-Based Methods for Sentiment Analysis[END_REF]. The term "relatively" is used because two kinds of testing results achieved on two different input data sets were compared. They present many tests with resulting performance up to 80 percentages (within more than 100 experiments only two results are higher than 80 percentage). On the other hand, our tests were not so complex as in [START_REF] Taboada | Lexicon-Based Methods for Sentiment Analysis[END_REF] and therefore our resulting precision could be lower when using their corpuses of reviews. Our results seem to be better (once again relatively) than results (up to 73 percentages) in [START_REF] Thelwall | Sentiment Strength Detection in Short Informal Text[END_REF]. This comparison is relative because of compared results were achieved on different input contributions and because no cross validation was used. On the other hand, performance achieved in [START_REF] Choi | Learning with Compositional Semantics as Structural Inference for Subsentential Sentiment Analysis[END_REF] is higher than performance of our applications.

The paper introduced variety of approaches to solving the problem of opinion classification to positive or negative polarity. It also described five various original methods of opinion classifications and it also introduced the test results of implementations of the presented methods.

The novelty of our approach is, that our dictionary was generated directly from a web discussion, which increases the precision of opinion analysis of the given discussion and so the dictionary can easily accommodate some misspelled words as well.

The achieved precision of classification of positive contributions within all presented versions of our application was approximately 80 percentages. It is not so bad in the comparison with other existing applications. On the other hand, precision of classification of negative contributions using n-grams is too low. For the future, we would like to test the introduced version of opinion classification application on larger corpus of discussion contributions.

There is a possibility to upgrade version based on n-grams to achieve higher precision within processing of negative contributions. There is a need to extend the classification dictionary. This version should be enriched by techniques for processing also contributions, which contain only neutral words, but their context is positive or negative. The techniques for processing of irony and ambiguity should be included too. The research in the field of opinion classification has big importance for the future. A successful application of opinion classification can be very helpful in the process of decision making.

Fig. 1 .

 1 Fig. 1. Three ways of the dynamic coefficient determination.

Table 1 .

 1 Precision of testing results of various implementation versions.

	Version	Positive Negative Average precision
	Static coefficient	0.86	0.69	0.78
	Dynamic coefficient 1	0.76	0.84	0.80
	Dynamic coefficient 2	0.80	0.88	0.84
	Hybrid	0.80	0.84	0.82
	N-grams 1	0.83	0.57	0.70
	N-grams 2	0.76	0.42	0.59

Acknowledgements. The work presented in this paper was supported by the Slovak Grant Agency of Ministry of Education and Academy of Science of the Slovak Republic within the 1/1147/12 project "Methods for analysis of collaborative processes mediated by information systems".


Raik Niemann

Nikolaos Korfiatis

Roberto Zicari

Richard Göbel

Evaluating the energy efficiency of OLTP operations A case study on PostgreSQL

With the continuous increase of online services as well as energy costs, energy consumption becomes a significant cost factor for the evaluation of data center operations. A significant contributor to that is the performance of database servers which are found to constitute the backbone of online services. From a software approach, while a set of novel data management technologies appear in the market e.g. key-value based or in-memory databases, classic relational database management systems (RDBMS) are still widely used. In addition from a hardware perspective, the majority of database servers is still using standard magnetic hard drives (HDDs) instead of solid state drives (SSDs) due to lower cost of storage per gigabyte, disregarding the performance boost that might be given due to high cost.

In this study we focus on a software based assessment of the energy consumption of a database server by running three different and complete database workloads namely TCP-H, Star Schema Benchmark -SSB as well a modified benchmark we have derived for this study called W22. We profile the energy distribution among the most important server components and by using different resource allocation we assess the energy consumption of a typical open source RDBMS (PostgreSQL) on a standard server in relation with its performance (measured by query time). Results confirm the well-known fact that even for complete workloads, optimization of the RDBMS results to lower energy consumption.

Introduction

A general assumption is that efficient programs are also energy efficient [START_REF] Papadimitriou | Computational complexity[END_REF]. This seems to be reasonable since a program requiring less computation time will probably also require less energy for its execution. This can be true if we assume a constant energy use of a computer, and the computer performs more tasks in the same amount of time because of time efficient programs.

However, a more detailed analysis may show a different picture. For example it is a well-known fact that one complexity measure like time can be optimized at the costs of another complexity measure of space. An optimization following this path may require that the increased amount of data for a program may be transferred from one type of memory to a different type of memory. In a modern computer this might result that the data may be moved from the CPU cache to the main memory or from main memory to a drive. An obvious consequence of this transfer are longer access times which may already reduce the benefit of these optimization strategies. In addition the usage of a different memory type may result in higher energy costs [START_REF] Tsirogiannis | Analyzing the energy efficiency of a database server[END_REF]. For example, this can be the case if a large data structure needs to be generated on an external drive and the access to this drive would need to be frequently used in comparison to a solution where the drive may be even stopped to save energy.

Since the amount of information to be processed has drastically increased over the last couple of years, large and very large data centers which are expected to support internet operation have been built by major players (e.g. Google and Amazon). However, increased costs of operation (electricity, cooling costs) have made these vendors to offer the rental of unneeded data center capacity (disk storage space, computation time) to nearly everyone who is willing to pay. This gives rise to the concept of "cloud computing" where, for example, server capacities are only needed for a limited time or where the acquisition of an own data center is too expensive [START_REF] Armbrust | A view of cloud computing[END_REF].

Furthermore, in the context of database applications another issue might arise: the distribution of data across a database cluster as a basis for distributed computing, as it happens in the case of Big Data/Hadoop clusters [START_REF] Abouzeid | HadoopDB: an architectural hybrid of MapReduce and DBMS technologies for analytical workloads[END_REF]. Industry trends 3 advocate that increased demand for server performance will be fulfilled by deploying more (database) servers and data centers. But with increased energy costs, data centers operators are looking for mechanisms to avoid or reduce those costs (scale-up strategies). This way the energy efficiency of a single database server becomes important as it can be a crucial component for the overall cost assessment of a data center operation where energy costs are the most significant factor on their operation and scalability.

Background and Motivation

Several approaches which can be found in the literature have addressed the issue of energy efficiency of database servers from different aspects. Harizopoulos et. al [START_REF] Harizopoulos | Energy Efficiency: The New Holy Grail of Data Management Systems Research[END_REF] as well as Graefe [START_REF] Graefe | Database servers tailored to improve energy efficiency[END_REF] divided energy efficiency improvements into a hardware and a software part. Recent work such as the one by Baroso and Hölzle [START_REF] Barroso | The Case for Energy-Proportional Computing[END_REF] has revealed the fact that the impact of hardware improvements on the energy efficiency is quite low. A main approach in that direction is the use of Solid State Drives (SSD's) which have been shown to improve performance on typical database operations such as sorting and therefore energy efficiency [START_REF] Beckmann | Energy-efficient sorting using solid state disks[END_REF]. Obviously SSDs are faster in such kind of scenarios [START_REF] Polte | Comparing performance of solid state devices and mechanical disks[END_REF], but there are other tradeoffs as a replacement for HDDs with most obvious the cost per gigabyte (Schall et. all [11], Schröder-Preikschat et. all [START_REF] Schröder-Preikschat | Migrating server storage to SSDs[END_REF], Härder et. all [START_REF] Härder | Energy efficiency is not enough, energy proportionality is needed![END_REF]).

On the other side, software improvements seem to be more attractive when it comes to increasing the energy efficiency of a database server, especially for relational databases. Lang and Patel [START_REF] Lang | Patel: Towards Eco-friendly Database Management Systems[END_REF], for example, proposed a database query reordering technique to influence the energy consumption of the database server. Xu et. all [START_REF] Xu | Exploring power-performance tradeoffs in database systems[END_REF] proposed a modification of the query planner in order to take the estimated energy consumption into consideration.

Tsirogiannis et. all [START_REF] Tsirogiannis | Analyzing the energy efficiency of a database server[END_REF] had a very detailed investigation regarding the relation between performance and energy consumption in a RDBMS. For that they did extensive measurements with various hardware configurations that are typically found in a database server for a scale-out scenario. In addition to this, they identified performance tradeoffs for different SQL query operators.

Objective of This Study

This study provides the basis for a more detailed analysis of the energy consumption in the context of database applications that are common in daily workloads of enterprise users. For this purpose the paper does not only consider the total power consumption of the full system but also the usage of energy by different components. In addition the paper analyses standard energy saving strategies coming with a modern computer system and their impact on the power consumption.

In the context of database applications, it is important to know which database operation or which combination of SQL operators affects which of the measured components. This study analyzes these combinations and their fraction of the overall power consumption.

All the mentioned aspects lead to the final view on the energy efficiency of a single database server. This is important when it comes to a scale-out scenario that is typically found in a database cluster. There are two choices: either one decreases the energy consumption of the used hardware equipment with a small decrease of the database response time, or increases the performance while accepting a slight increase of the energy consumption. Both ways improve the energy efficiency.

As suggested by Xu [START_REF] Xu | Building a power-aware database management system[END_REF], more experimental research has to be done concerning the energy consumption of database servers. Taking this into account, this study tries to have a closer look on both choices mentioned above and to give recommendations how to improve the energy efficiency of a single database server in a general way (for example the usage of buffers and indices combined with traditional HDDs as the primary storage for the database files).

Measurement Methodology

Test Server Preparation

For the purpose of this study, we constructed a database server making use of recent technical core components. The operating system selected for testing was a typical Linux distribution (Ubuntu Server version 11.10) using a stable kernel (kernel version: 3.0.0.17). In order to eliminate biases from the operating system in our measurements, all unnecessary operating system services were turned off. The database management system (DBMS) that was used was PostgreSQL version 9.1. The hardware characteristics of the test server are provided in Table 1. Two of the three hard drives were combined as a striping RAID array in order to boost performance and to separate the filesystem calls of the DBMS from the operating system. The operating system itself was installed on the remaining third hard drive.

We identified the core components we were interested in their power consumption throughout the various tests as follows: (a) CPU, (b) main memory, (c) motherboard as a whole and (d) the hard drives of the RAID array. These core components were used as a unity of analysis in order to assess the optimization options. Additionally we were interested in the impact of the operating system settings as well as the test server capabilities on the energy consumption of the core components. Modern server configurations don't allow an external measurement of the energy consumption of internal server components so we decided to use a test apparatus based on moderate hardware. Our test arrangement makes use of a modified ATX power for measurements but server manufactors mostly use proprietary power cords. The complete test arrangement can be viewed online 4 .

Besides, the test server's motherboard used Intel 's EIST 5 . In general EIST enables and disables CPU cores or reduces and raises the overall CPU clock frequency as a function of the CPU usage. This also affects other technical aspects, e.g. the heat dissipation from the CPU.

Recent Linux kernels offer several modules providing more data to the frequency scaling heuristics. The observed modules for our test server configuration are the on-demand and the power-saving modules. Taking this into account, the command line tool powertop6 was used to suggest configurations on the disablement of operating system services that might influence energy consumption.

Stress Tests on Energy Consumption

Before assessing the energy efficiency as a whole as well as the components we were interested in profiling their energy consumption, we performed stress tests to get a detailed overview of the energy distribution among the single components. Figure 1 summarizes the stress tests. Each tuple of the shown bars represents a stress test for a core component. The left bar of a specific tuple illustrates the energy consumption of each component in conjunction with the on-demand frequency scaling module. The right bar of the tuple displays the energy consumption of all energy saving settings enabled, respectively. Figure 1 also shows the energy consumption of the power supply unit (PSU) which is the difference between the overall power consumption of the test server and the one of the measured components. Our first action was to calibrate the test procedure by analyzing the energy consumption of the core hardware components as a basis for the other tests. All services and applications not required for the operating system as well as the DBMS service were turned off. The operating system uses default settings, e.g. the usage of the on-demand CPU frequency scaling module. The average consumption per core component is shown in Fig. 1 in the left bar of the tuple named Idle. The right bar of this tuple shows the energy consumption with all available energy saving settings turned on. There is a slight increase of the power consumption: although the CPU is forced to reach the energy saving idle states, it is constantly interrupted by doing so, for example by administrative background processes of the operating system. Changing the CPU state costs some effort but results in higher energy consumption.

To measure the power consumption stressing the CPU of our test server, we decided to use the Linux command line tool burnMMX because it utilizes all parts of the CPU including extension like MMX or AVX. Based on the eight CPU cores reported to the operating system, we ran our CPU stress test eight times and increased the number of running burnMMX instances accordingly. As assumed the power consumption increases up to the four real cores and remains relatively constant if more cores were used due to HT 7 . This behavior corresponds to the CPU tests reported in [START_REF] Tsirogiannis | Analyzing the energy efficiency of a database server[END_REF]. The CPU stress test with the highest energy consumption for both scenarios (energy saving settings turned off and on) is depicted in Fig. 1 as the bar tuple labeled CPU for comparison with the other stress tests.

To stress test the hard drives in the RAID array we executed the I/O benchmark suite iozone while observing the power consumption throughout the different benchmark tests (different access strategies, buffered and un-buffered data access and so on). Our test results are displayed in Fig. 1 in the second bar tupel labeled Disks. Our test shows that the impact on the energy consumption is low when all energy savings settings are turned on. However, in contrast to the power consumption of current SSDs [START_REF] Schröder-Preikschat | Migrating server storage to SSDs[END_REF] the power consumption of the hard drives is two to three times higher.

Finally we stressed the main memory with the command line tool memtester that uses different patterns to access the main memory. It also tests for the correctness of the contents by writing, reading and comparing the main memory areas. The effect on the power lane supplying the main memory was not measurable. In contrast to this, the left bar of the tuple named Main memory in Fig. 1 indicates an increase of the overall power consumption of 30 Watts in which the CPU is responsible for. Even with all energy saving settings turned on [START_REF] Zheng | Power and Performance Trade-Offs in Contemporary DRAM System Designs for Multicore Processors[END_REF], the overall energy consumption was higher than in idle state.

Measuring Energy Efficiency

We define the performance ratio (P ) of a single database query as the unit of time to execute the query in time (t) to obtain the results [START_REF] Wang | A survey on energyefficient data management[END_REF]:

P = 1 t (1)
We then normalize a set of performance values to values between zero and one as follows: 7 HT is an acronym for Hyperthreading by Intel. It is used to improve parallelization of computation.

P normalized,i = P i • 1 max(P )
We then define the energy efficiency EE as the ratio between the performance P of the database query and the electrical work W executing the query:

EE = P W (2)
We then normalize the set of efficiency values to values between zero and one as follows:

EE normalized,i = EE i • 1 max(EE)

Selection of Workloads and DBMS Parameters

As aforementioned our intuition here is to examine the effects of executing a database query in relation to the overall power consumption. For example a combination of a not well formed SQL query and an optimized query planner can cause a cascade of operations that consumes a lot of unnecessary power, e.g. sequential scans cause unnecessary hard drive accesses with all its overhead in the operating system (access control, swapping and so on).

According to related work, for example [START_REF] Tsirogiannis | Analyzing the energy efficiency of a database server[END_REF] or [START_REF] Barroso | The Case for Energy-Proportional Computing[END_REF], we identified several settings for our PostgreSQL database server we hypothesized they had an important impact on the power consumption. Those settings can be divided into two groups: the first one are the settings for the underlying operating system and for PostgreSQL and the second one are settings for the database itself. In detail those settings are:

-The size of the main memory assigned to PostgreSQL to operate -The size of the miscellaneous buffers, e.g. for sorting resulting rows or caching -The settings for the query planner -The size of the data in the database -The session type of executing subsequent queries (single session vs. multi session) -Combinations of the different SQL operators and functions, for example increasing number of joined tables or the number of result set dimensions to be restricted To get comparable results we decided to run three complete database benchmark workloads: TPC-H [START_REF] Poess | New TPC benchmarks for decision support and web commerce[END_REF], the Star schema benchmark (SSB [START_REF] O'neil | The Star Schema Benchmark (SSB)[END_REF]) and a third benchmark constructed specifically for this study, we call it the W22 benchmark. The first two offer a standardized way for comparison whereas the last one is a workload we composed to analyze the behavior of PostgreSQL not covered by the previously mentioned workloads.

3 Workload Results

TPC-H Workload

For the TPC-H workload we used their data generator to generate three databases with a size of 1, 5 and 10 GByte of data as well as all suggested indices. We chose these database sizes because we wanted the databases to fit completely, nearly and under no circumstances in the working main memory for PostgreSQL by assigning 1, 2.5 and 5 GByte. This selection was made due to the limitation of 6 GByte overall main memory present in the database server. In a final setup step we optimized the internal data structures and the query planner statistics of PostgreSQL for the created databases.

At first we ran the benchmark queries subsequently using a new database connection to avoid PostgreSQL's internal cache 8 . After this we retried the TPC-H benchmark using a single database connection for the SQL queries. The average power consumption per component for both test series is shown in Fig. 2(a). This figure clearly indicates the higher energy consumption when a single session is used. We recognized that the average overall power consumption for all of our TPC-H tests does not vary a lot. Please compare only the bars which are identically labeled with each other. We assumed that the CPU and hard drives are the main energy consumer but in fact it turned out that the mainboard is the biggest one.

We also assumed that the usage of single database connection would improve the performance because of the better usage of PostgreSQL's internal cache but the opposite occured: the performance was nearly the same with an increased power consumption of 7 percent on average. Using the equations outlined in Sec. 2.3, this leads to a lower energy efficiency of nearly 8 percent on average as depicted in Fig. 2

(b).

A detailed study of the query plans reveals a broad usage of sequential scans on the TPC-H database tables as well as a low usage of the internal caches. Therefore we modified PostgreSQL's settings regarding the query planner and caches to favor the provided indices and repeated the tests. This has an inverted effect: the performance decreases by about 4 percent on average. The reason is the overhead to process the indices which are also disk bounded.

In general we observed a big effect on the energy efficiency by assigning a higher portion of the main memory to PostgreSQL. This results in massive swapping for some TPC-H queries, e.g. 1, 9 and 21, and the suspension of the PostgreSQL process. In fact, PostgreSQL is very disk bound and by accessing the database files the operating system swaps heavily because of the reduced main memory portion. Besides, swapping does effect only the hard drive and not the CPU. This affects the overall power consumption for our TPC-H tests and explains the small variation of the values.

Finally we were interested in performance versus energy efficiency ratio as stated in the conclusion of [START_REF] Tsirogiannis | Analyzing the energy efficiency of a database server[END_REF]. This ratio for our entire TPC-H tests with all its different configurations is shown in Fig. 3 and confirms the strong relation between performance and energy efficiency (the most energy-effiencent configuration is typically the highest performing one). q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q qq q qq q q q q q q q q q q q q q q q q q qq q qq q qq q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q qq q q q q qq q q q q q q q q q q q q q q qq q q q q q q 0.0 0.

Fig. 3. Performance vs. energy effiency for TPC-H workload

This figure also shows that the majority of the configurations are clustered in the lower left area. This means that most of the queries of the TPC-H benchmark show a poor energy efficiency.

Star Schema Workload

The Star schema benchmark (SSB) was initially composed to get a database layout closer to reality compared to TPC-H which it is based on. According to [START_REF] O'neil | The Star Schema Benchmark (SSB)[END_REF] several original tables were decoupled to make many join operations unnecessary and the set of SQL queries of SSB were created to be more realistic and to test the database capabilities regarding range coverage and indice usage.

For executing the SSB SQL queries we used the same parameters as described in Sec. 3.1: we generated three different databases with 1, 5 and 10 GByte of data and created test configurations for PostgreSQL with 1, 2.5 and 5 GByte main memory to work on.

Just as for the TPC-H workload, we ran the SSB database queries subsequently by using a single and multiple database connections. The average energy consumption per component is depicted in Fig. 4(a). The type of accessing the database matters: although the average performance is nearly the same, the average power consumption for multiple connections is lower than the one for using a single connection. The latter consumed nearly 10 percent more energy on average. Except for the database size of 1 GByte, this results in a lower energy efficiency.

In general and in terms of energy efficiency, the SSB benchmark performs better than TPC-H. In addition to this, SSB organizes its SQL queries into groups in which the requested rows do not overlap and the group number indicates on how many dimensions the result set has to be restricted. This allows a better analysis of the results and avoids side effects interfering the results. Figure 4(b) shows the energy efficiency of our SSB tests. A deeper investigation of the query plans showed us that the reduced set of tables and the modified queries lead to a more stable and predictable behaviour concerning the power consumption and energy efficiency. In particular this can be seen in Fig. 4(b): the energy efficiency for a given constant SSB database size does not vary a lot and is relatively independent from the amount of main memory spent for PostgreSQL.

Besides, the energy efficiency of the SSB database with 10 GByte is remarkably lower than the ones with 1 and 5 GByte of data. An investigation of the logged system activities during the tests revealed heavy swapping actions which caused the suspension of the PostgreSQL process handling the queries. As illustrated in Fig. 4(a), the low CPU energy consumption indicates the heavy swapping activity.

The query plans also show the general use of sequential scans on the SSB database tables. In fact, no indices were involved to execute the queries in all configurations. The execution of the queries purely relies on the read performance of the database files. As Fig. 5(a) indicates, it does not matter if the result set of the joint tables are further restricted. In addition to this, this figure shows that main memory spent for buffers is relatively unimportant: if one consider a specific database size, the row scan per second rate does not vary a lot. This means that the mentioned rate is independent of the main memory fraction assigned to PostgreSQL and also independent of the number of dimensions the result set is restricted. (a) SSB row scans per second q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 0.0 0.2 0.4 0.6 0. The performance vs. energy efficiency ratio for all SSB test configurations is illustrated in Fig. 5(b). The same strong relationship can be seen as in Fig. 3 for the TPC-H benchmark tests. In contrast to TPC-H, the vast majority of the SSB test configurations is clustered in the upper right corner of Fig. 5(b). This means that the SSB configurations perform much better. This leads to a better energy efficiency.

W22 Workload

To get a more in-detailed look at the impact of the different SQL operations and their combinations we composed a database workload called W22. The workload consists of six groups of database queries:

1. aggregate functions (count, avg and sum) 2. grouping (GROUP BY) 3. sorting (ORDERED BY) 4. selecting different data types, e.g. int, varchar, text and date 5. removing duplicates (DISTINCT) 6. joins (cross joins, conditional joins) In contrast to this, the TPC-H and the SSB workload are designed for benchmark an OLAP scenario. Their database queries use a mix of different SQL operations coming from the groups above. Our W22 workload instead tries to analyze the impact of SQL queries in each group. Besides, this workload allows to the behaviour of PostgreSQL's internal query optimizer and query planner as well as the interaction with the underlaying operating system. The W22 queries operate on the TPC-H databases described in Sec. 3.1.

Aggregate Functions Our first tests with aggregate functions, e.g. avg(), sum() and count(), show in particular the impact of the filesystem cache of the underlaying operating system. All of the mentioned aggregate functions cause PostgreSQL to perform a sequential scan. The first query that was executed (count(*)) had a notably longer execution time compared to the next ones (avg() and sum()). The query plans for all three queries are the same. After a closer investigation of the logged activities of the operating system, we identified the filesystem cache as the performance booster by caching the database files that PostgreSQL uses. In this case the kind of executing the queries (single session vs. multi session) does not matter. The most important setting is the fraction of main memory assigned to PostgreSQL: the lower the fraction the more main memory is available for system caches.

The suggested optimizations of the queries, e.g. the use of an indexed column for count() (count(column) instead of count(*)), did not change the execution times.

Grouping and Sorting

The queries of group 2 (grouping) and group 3 (sorting) expands the count() query from group 1 with SQL operators like ORDER BY and GROUP BY to get comparable results. Those queries were composed to study the impact of the mentioned SQL operators in reaction of the previous tested benchmarks TCP-H and SSB.

The tests result indicates only a slight difference in terms of execution times and energy consumption compared to the test results of group 1. The impact on the energy consumption of the CPU and the main memory was not measurable. As a result the calculated energy efficiency remains the same.

Selection of Different Data Types According to our tests, the selection of a specific data type, e.g. VARCHAR, DATE and INTEGER, has no impact on the query execution time.

The other purpose of the queries of group 4 was to test the operators of the different data types with and without having an index on the particular table column. We observed a big impact on the execution time when an index was used whereas the average energy consumption was slightly higher. The presence of an index in combination of an operator9 supporting this index lead to an immense performance gain. Therefore the energy efficiency is quite high compared to a sequential scan. In contrast to the queries with an absent index, the queries with an involved index showed an almost linear performance. This is crucial since we used the largest table of TPC-H, lineitem, which also has the greatest amount of rows throughout all queries of this group.

PostgreSQL uses an index for a query when a) the index supports the operator of the query and b) the costs for processing the index are lower than sequentially scanning the table. Those costs are composed of customizable base costs and dynamic cost estimations that PostgreSQL gathers periodically and statistically from all tables of a database.

We modified the settings for the base costs of loading and processing a database and an index page (usually 8 KBytes of data) to favor the usage of indices, e.g. if the database and indice files are stored on different storage devices with different access speeds (the indice files are usually stored on the faster one). Our test results remain the same because the data and index files are stored on the same hard drive device.

Joining Tables and Eleminating Duplicates

Based on our TPC-H and SSB benchmark results, we were interested in the behaviour of PostgreSQL dealing with table joins. There are two kinds of joins supported in PostgreSQL: unconditional and conditional joins.

Our first query of this W22 group deals with an unconditional join of two tables where the cross product is further restricted by the conditions given after the WHERE clause (one restriction per involved table). We expected this query to be unperformant due to the cross product and the successive restriction of the result set, but this was not the case. The query plan reveals the (unintentional) use of an index for one restriction and a sequential scan for the other one. So the results (performance, energy consumption and the energy efficiency) are the same as mentioned in the last section although a sequence scan is part of the query plan.

The other queries of this W22 group were composed to join two TPC-H tables using inner 10 and equi-joins 11 to examine differences in the query plans. Interestingly those queries indicate the same characteristics in terms of the query planner. For PostgreSQL it does not matter where the condition for joining two tables is placed. In other words, PostgreSQL does not distinguish between an inner, implicit or equi-join.

Besides, the queries are composed to join two TCP-H tables with different number of rows to investigate the join performance. The first two queries joined the lineitem table with the orders and the part table, respectivly. The last query joined the orders with the customers table.

Finally we select the amount of joined rows by using the count(*) aggregate function. This forces PostgreSQL to use sequential scans for the mentioned tables.

As assumed, our test results indicate that the join performance is strongly related to the row scan performance. The test results are similar to the ones of our TPC-H and SSB benchmarks. This means they do not resemble much in their energy consumption but in their execution times. Unsurprisingly the lower the amount of rows to be scanned for joining, the lower is the execution time and therefore the energy efficiency is quite better. Although compared with query with the unconditional join mentioned above, the performance is fundamentally worse.

We were also interested in the effects of eleminating duplicates from a result set. For this purpose we formed a test query using the DISTINCT() clause on a column of the lineitem table not having a supporting index. The query plan revealed a sequence scan and the removal of duplicates by hashing the values. Again, the test results showed the same characteristics as all of our database tests performing a sequence scan.

Summary

At first, our tests with our database server using normal HDDs indicates an energy increase of roughly 9 W when the HDDs are fully utilized. Compared to the energy consumption of the other measured core components during the tests, this is insignificant. The argument, SSDs should be prefered because they consume up to 12 times less energy compared to HDDs, is invalid in this context. 10 The SQL standard standardized an inner join as <table a> [INNER] JOIN <table b> WHERE <a.xyz> = <b.xyz>. 11 An equi-join is in the form <table a> JOIN <table b> ON <a.xyz> = <b.xyz>.

The SQL standard allows shorthand for the column to join by using the USING clause.

As Lang et all. stated in the summary of [START_REF] Lang | Towards Energy-Efficient Database Cluster Design[END_REF], evaluating the energy efficiency of a DBMS needs the inclusion of entire workloads, not just single queries. This study makes use of three different and complete workloads that allows a more comprehensive look at the energy efficiency of a relational DBMS. Most of the benchmark queries caused a massive usage of sequential scans. This implies that the sequential read performance is an extremly important factor that affects the energy consumption. Actual SSDs clearly outperform normal HDDs but in this case enterprise grade HDDs can be used because they offer nearly the same performance as SSDs.

As mentioned in the introductionary section of this paper, there are more factors and not only technical parameters that influence the performance and thus the energy efficiency of a database server.

For example, the filesystem cache provided by the operating system is more relevant for the execution of a database query in PostgreSQL than its internal cache. Based on our experiments, we recommend not to assign more than 50 percent of the main memory to PostgreSQL for operations. With more assigned main memory the remaining processes of the operating system are forced to use the remaining portion. This causes the operating system to swap this portion to the hard drive which leads to a dramatic reduction of the performance.

Another important factor for the energy efficiency of the used database benchmark is the kind of accessing PostgreSQL (single vs. multiple database connections). Our assumption, subsequent queries of the benchmarks would benefit from PostgreSQL's internal cache by using just a single database connection, does not come true. In fact, the opposite performed better.

Our tests also indicate the fact that energy saving settings are counterproductive for a database server that is reasonably utilized because it decreases the overall system performance.

Fig. 1 .

 1 Fig. 1. Energy consumption per component during our calibration stress test

Fig. 2 .

 2 Fig. 2. Energy consumption per component and energy efficiency for the TPC-H workload

1 5 10

 10 Database size in GByteComponent power consumption in W (a) Energy consumption per component

  GByteEnergy effiency (the higher the better) (b) Energy efficiency

Fig. 4 .

 4 Fig. 4. Energy consumption per component and energy efficiency for SSB workload

Fig. 5 .

 5 Fig. 5. Row scan count and performance vs. energy efficiency for SSB

Table 1 .

 1 Hardware characteristics of the test server used in our study

	CPU	Intel Core i7-860 @2.8 GHz
	Main memory 3x Samsung DDR-2 2 GByte 800 MHz (m378b5673fh0-ch9)
	Hard drives 3x Hitachi 1 TByte, 16 MByte cache (HDT721010SLA360)

State of the data center 2011 by Emerson

Refer to http://team.iisys.de/test-apparatus/

Acrynym for Intel Enhanced Speedstep. It allows the system to dynamically adjust the CPU frequency and voltage to decrease energy consumption and heat production.

Refer to http://www.lesswatts.org/projects/powertop/

Notice that PostgreSQL's implementation isolates client connections completely by running the client sessions in shared-nothing processes. The client processes only share some IPC memory for synchronization purposes and the ACID functionality. This means that every client has its own cache.

For example, the operators greater than, less than and equals (<, > and =) are valid for B-tree indices on numeric table columns in PostgreSQL. There are other index types, e.g. inverted index, for other column data types as well as their specialized operators.


Pascal Lienhardt
email: pascal.lienhardt@xlim.fr

Samuel Peltier
email: samuel.peltier@xlim.fr

Homology Computation during an Incremental Construction Process (Extended Abstract)

Keywords: Homology, simplicial and cellular combinatorial structures, incremental computation

Controlling the construction of geometric objects is important for several Geometric Modeling applications. Homology (groups and generators) may be useful for this control. For such incremental construction processes, it is interesting to incrementally compute the homology, i.e. to deduce the homological information at step s of the construction from the homological information computed at step s -1. We here study the application of effective homology results [13] for such incremental computations.

Introduction

Geometric Modeling deals with the representation and the construction of geometric objects. For instance, many representations and related construction operations have been conceived for CAD/CAM applications ; since a modeled geometric object can be manufactured, it is necessary to control its construction, in order to detect any problem as soon as possible. According to the application, homology (i.e. homology groups and/or the correspondence between their generators and chains of cells of the object at each step of its construction) may be useful for controlling the construction.

Many works in Geometric Modeling deal with subdivided geometric objects, i.e. objects partitioned into cells of different dimensions, and many methods have been proposed for computing the homology of subdivided objects, e.g. based upon the Smith Normal Form of incidence matrices [START_REF] Agoston | Algebraic Topology, a first course[END_REF]. Such methods make it possible to compute the homology at each step of the construction of a geometric object; but the whole homological information has to be computed at each step, without taking advantage of the information known at the previous step. So, it seems interesting for such a process to incrementally compute the homology, i.e. to deduce the homology of the object at step s from the homology of the object at step s -1, according to the operation which is applied. Such incremental computation can be done by applying results of effective homology [START_REF] Rubio | Constructive Homological Algebra and Applications[END_REF].

Although some aspects are close to the work described in [START_REF] Boltcheva | An iterative algorithm for homology computation on simplical shapes[END_REF], the approach here focuses on the application of construction operations and the related complexities. Since only the structure of an object has to be taken into account in order to compute its homology, it will be assumed that it is represented by a semi-simplicial set or a cellular combinatorial structure (incidence graph or combinatorial map). In the simplicial (resp. cellular) case, two basic operations (and the inverse operations) are studied 1 : cone and identification (resp. extension and identification), which make it possible to construct any semi-simplicial set (resp. any cellular combinatorial structure). At each step, some "homological information" is maintained in order to reduce the complexity of the homology computation. This "homological information" depends on the (subset of) combinatorial structure which is taken into account: for semi-simplicial sets and a subclass of cellular combinatorial structures, a "homological information" related to connected components is maintained; but it is necessary to maintain a "homological information" associated with cells and connected components for cellular combinatorial structures in general. More precision can be found in [START_REF] Alayrangues | Incremental Computation of the Homology of Generalized Maps -An Application of Effective Homology Results[END_REF].

Notations A chain complex (C, ∂) can be associated with a semi-simplicial set or a cellular combinatorial structure S, in such a way that there is a strong correspondence between them (for instance, a generator of the chain complex is associated with any simplex, and the boundary operator is deduced from the face operators). Chain complex (H, 0) (or equivalently H) denotes the homology of S. The complexity of a chain complex, or a combinatorial structure, is related to the number of generators and the "cost" of the face or boundary operators (in terms of generators): for instance, the complexity of a n-dimensional semi-simplicial set (or its associated chain complex) is

n i=0 k i c i + n i=1 (i + 1)k i d i-1 ,
where k i is the number of i-simplices, c i (resp. d i ) is the complexity of the representation of a i-simplex (resp. of a i-simplex in the boundary of a (i + 1)-simplex).

Effective homology bases

This section is mainly based on the course notes of J. Rubio and F. Sergeraert [START_REF] Rubio | Constructive Homological Algebra and Applications[END_REF] (see also [START_REF] Boltcheva | Constructive Mayer-Vietoris Algorithm: Computing the Homology of Unions of Simplicial Complexes[END_REF]).

A reduction ρ = ((C, ∂), (C S , ∂ S ), h, f, g) is a 5-tuple where (1) (C, ∂) and (C S , ∂ S ) are chain-complexes; [START_REF] Alayrangues | A Boundary Operator for Computing the Homology of Cellular Structures[END_REF] the complexity of (C S , ∂ S ) is lower than that of (C, ∂); so, the homology of (C, ∂) is computed with a better complexity starting from (C S , ∂ S ). Several methods are based on (composition of) elementary reductions3 in order to simplify a chain complex before computing its homology [START_REF] Dlotko | Coreduction Homology Algorithm for Regular CW-Complexes[END_REF][START_REF] González-Díaz | Chain homotopies for object topological representations[END_REF].

f : (C, ∂) → (C S , ∂ S
A homological equivalence Υ is a pair of reductions (C, ∂)

ρ ⇐ ⇐ ⇐ (C B , ∂ B ) ρ S ⇒ ⇒ ⇒ (C S , ∂ S
). This notion makes it possible to associate a "small" chain complex (C S , ∂ S ) with another chain complex (C, ∂), through a "bigger" one (C B , ∂ B ), even when no reduction (C, ∂) ⇒ ⇒ ⇒ (C S , ∂ S ) exists.

An effective short exact sequence

((C 0 , ∂ 0 ), (C 1 , ∂ 1 ), (C 2 , ∂ 2 ), i, j, r, s) is a di- agram: 0 0 -→ (C 0 , ∂ 0 ) r ←- -→ i (C 1 , ∂ 1 ) s ←- -→ j (C 2 , ∂ 2 ) 0 -→ 0 where (1) (C 0 , ∂ 0 ), (C 1 , ∂ 1 ), (C 2 , ∂ 2 ) are chain complexes;
(2) i,j are chain complex morphisms; (3) r,s are graded module morphisms. They satisfy ( 4)

ir = id C 0 ; (5) ri + js = id C 1 ; (6) sj = id C 2 .
This notion is a key one for optimizing the homology computation at each step of an incremental construction process; indeed, if an effective short exact sequence can be associated with the applied operation, the following SES theorem can be applied (only the subparts of the theorem which are useful here are provided: cf. [START_REF] Rubio | Constructive Homological Algebra and Applications[END_REF] page 71).

Theorem 1 (SES Theorem). Let ((C 0 , ∂ 0 ), (C 1 , ∂ 1 ), (C 2 , ∂ 2 ), i, j, r, s) be a short exact sequence. Then, given two homological equivalences Υ 0 : (C 0 , ∂ 0 )⇐ ⇐ ⇐ (C B0 , ∂ B0 )⇒ ⇒ ⇒(C S0 , ∂ S0 ) and Υ 1 : (C 1 , ∂ 1 ) ⇐ ⇐ ⇐ (C B1 , ∂ B1 ) ⇒ ⇒ ⇒ (C S1 , ∂ S1 ) (resp. Υ 2 : (C 2 , ∂ 2 ) ⇐ ⇐ ⇐ (C B2 , ∂ B2 ) ⇒ ⇒ ⇒ (C S2 , ∂ S2 )), it is possible to deduce from i, j, r, s, Υ 0 and Υ 1 (resp. Υ 2 ) a homological equivalence Υ 2 : (C 2 , ∂ 2 ) ⇐ ⇐ ⇐ (C B2 , ∂ B2 ) ⇒ ⇒ ⇒ (C S2 , ∂ S2 ) (resp. Υ 1 : (C 1 , ∂ 1 ) ⇐ ⇐ ⇐ (C B1 , ∂ B1 ) ⇒ ⇒ ⇒ (C S1 , ∂ S1 )).
If the applied operation "corresponds" to a short exact sequence, and if the operands of the operation are associated with homological equivalences, it is possible to deduce a homological equivalence, and thus a (homologically equivalent) "small" complex, for the result of the operation, providing a better complexity for the final homology computation 4 . Of course, it is also necessary to check the complexity of the application of the SES theorem in order to check that the whole computation is better than, say, a computation based upon the computation of the Smith Normal Form of the incidence matrices.

Application to simplicial structures

The SES theorem has been applied in order to reduce the cost of the homology computation [START_REF]The Kenzo program[END_REF]. For instance, Boltcheva et al [START_REF] Boltcheva | Constructive Mayer-Vietoris Algorithm: Computing the Homology of Unions of Simplicial Complexes[END_REF] applied it for the conception of the Meyer-Vietoris (MV) algorithm, which computes the homological information of abstract simplicial complexes from the homological information of sub-complexes and their intersections. This algorithm has been applied for the Manifold-Connected decomposition of abstract simplicial complexes [START_REF] Boltcheva | An iterative algorithm for homology computation on simplical shapes[END_REF]. The basic idea is the following: let B and C be sub-complexes of A, such that A = B∪C, and Υ B∩C , Υ B and Υ C are homological equivalences associated with B ∩ C, B and C; a short exact sequence ((B ∩ C), (B ⊕ C), A = (B ∪ C), i, j, r, s) can be defined 5 , and a homological equivalence associated with A can be computed by applying the SES theorem.

More basic operations are studied here: cone and identification (cf. [START_REF] Alayrangues | Incremental Computation of the Homology of Generalized Maps -An Application of Effective Homology Results[END_REF] for more precisions). Cone(A), the cone of A, consists in adding a new 0-simplex v to A, and, for each i-simplex σ, in adding a (i + 1)-simplex incident to σ and v. Obviously, a homological equivalence Υ : (Cone(A)) ⇐ ⇐ ⇐ (Cone(A)) ⇒ ⇒ ⇒ (X) can be defined, where X contains only one 0-dimensional generator (the homology of a cone is trivial), and Υ can be computed in linear time according to the size of A.

The basic identification operation Ident(A, σ, τ ) consists, given two i-simplices σ and τ having the same boundary, in replacing them by a new simplex µ such that the boundary (resp. the star) of µ is the boundary of σ (resp. the union of the stars of σ and τ ). This operation can be easily generalized in order to identify any two i-simplices, and more generally subsets of simplices.

Assume a homological equivalence Υ : (A) ⇐ ⇐ ⇐ (A B ) ⇒ ⇒ ⇒ (A S ) is associated with A. Given a set of simplices A 0 which have to be identified, a chain complex (A 0 ) can be computed, in which each i-dimensional generator corresponds to a basic identification of i-simplices (i.e. if k i-simplices are identified into one i-simplex, there are (k -1) corresponding i-generators in (A 0 )). The boundary operator of (A 0 ) is deduced from the face operators of the simplices of A 0 . So, a homological equivalence Υ 0 : (A 0 ) ⇐ ⇐ ⇐ (A 0 ) ⇒ ⇒ ⇒ (A 0 ) can be computed in linear time according to the size of A 0 (the size takes into account the simplices of A 0 and their face operators). A better homological equivalence Υ 0 : (A 0 ) ⇐ ⇐ ⇐ (A 0 ) ⇒ ⇒ ⇒ (A 0 ) may be deduced by applying a method for simplifying (A 0 ), i.e. which computes a reduction (A 0 ) ⇒ ⇒ ⇒ (A 0 ).

Let Ident(A, A 0 ) be the result of the identification of the simplices of A 0 in A. It is possible to compute a short exact sequence Q = ((A 0 ), (A), (Ident(A, A 0 )), i, j, r, s) in linear time according to the size of A. Thus, by applying the SES theorem, it is possible to compute a homological equivalence 1). Once again, a better homological equivalence Υ I : (Ident(A, A 0 )) ⇐ ⇐ ⇐ (I B ) ⇒ ⇒ ⇒ (I S ) may be deduced by applying a method for simplifying (I S ), i.e. which computes a reduction (I S ) ⇒ ⇒ ⇒ (I S ). Then, the homology of Ident(A, A 0 ) can be computed from (I S ).

Υ I : (Ident(A, A 0 )) ⇐ ⇐ ⇐ (I B ) ⇒ ⇒ ⇒ (I S ) (cf. figure
As said before, the homological equivalence Υ 0 can be computed in linear time according to the size of A 0 , and the short exact sequence Q can be com- 5 The chain complex associated with X is denoted (X).

puted in linear time according to the size of A. The generators of (I B ) (resp. (I S )) are the generators of (A 0 ) and of (A B ) (resp. (A 0 ) and (A S ); this explains why it is interesting to reduce (A 0 ) into (A 0 )). It is not possible to give a precise evaluation of the complexity related to the computation of the boundary operators of (I B ) and (I S ), and of the mappings of Υ I , since this complexity depends on Υ , and thus depends also on the operations previously applied for constructing A. But the complexity can be evaluated for certain cases: for instance, when A is constructed by applying identifications, the whole computation is linear; moreover, if (I B ) (resp. I S ) is deduced by modifying (A B ) (resp. (A S )), the computation is sub-linear; and the complexity of the whole construction (i.e. related to all computations for all steps) is linear according to the size of the initial object. In the general case, the complexity of the computation is clearly related to the size of the parts of the object which are identified, i.e. (A 0 ).

An informal argument for the interest of the approach is the fact that, for many construction processes, local operations are applied at each construction step ; since the complexity is related to the modified parts, it is interesting to modify a previously known homological information rather than to compute it from scratch. Other precisions are given in section 3 and Appendix 6.7 in [START_REF] Alayrangues | Incremental Computation of the Homology of Generalized Maps -An Application of Effective Homology Results[END_REF]. In particular, note that the SES theorem applies for the inverse operation of the identification. At last, note that these results generalize in some sense the results described [START_REF] Boltcheva | Constructive Mayer-Vietoris Algorithm: Computing the Homology of Unions of Simplicial Complexes[END_REF][START_REF] Boltcheva | An iterative algorithm for homology computation on simplical shapes[END_REF], since the identification operation is a more basic operation than the gluing of connected components. In other words, gluing connected components can be achieved by identifying parts of their boundaries; but the identification operation can also be applied to subsets of simplices belonging to the same connected component.

Application to cellular structures

The previous results directly apply to other structures, as cubical [START_REF] Dlotko | Computing The Cubical Cohomology Ring[END_REF] and simploidal [START_REF] Peltier | Simploidals sets -Definitions, operations and comparison with simplicial sets[END_REF] structures (as for simplices, the homology of any cube or simploid is trivial; moreover, classical results apply for the cartesian product, which corresponds in some way to the cone for simplicial objects). They can also be applied to cellular combinatorial structures as incidence graphs 6 [10] and combinatorial maps [START_REF] Damiand | Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing[END_REF]. An incidence graph is represented in figure 2; results in [START_REF] Alayrangues | Incremental Computation of the Homology of Generalized Maps -An Application of Effective Homology Results[END_REF] are obtained for combinatorial maps, which generalize incidence graphs in order to take multi-incidence into account 7 , and these results directly apply to incidence graphs.

Any cellular combinatorial structure can be constructed by applying two basic operations: extension and identification. Given a connected n-dimensional structure, in which the dimension of all main cells is n, the extension consists in adding a new (n + 1)-cell incident to all n-cells. For instance, this operation applied to the incidence graph in figure 2 adds a volume incident fo faces f 1 and f 2 , the resulting "corresponding object" is a 3-ball. The identification operation consists in "merging" two cells having the same boundary; as for the simplicial case, this operation can be generalized in order to identify subsets of cells (this is constrained by the fact that two cells can be identified if they are isomorphic: for instance, it is not possible to identify a triangle and a square). Fig. 2. A 2-sphere, subdivided into 2 faces, 2 edges and 2 vertices, together with its simplicial equivalent and the corresponding incidence graph.

In the general case, it is not possible to associate a "cellular" chain complex (A) with any cellular combinatorial structure A, i.e. a chain complex in which any generator corresponds to a cell, and such that the homology of (A) is the homology of A. It is thus not possible to directly apply the results obtained in the simplicial case to cellular combinatorial structures. Indeed, cellular combinatorial structures exist, in which cells cannot be associated with balls. For instance, applying the extension operation to an incidence graph which corresponds to a subdivided torus or a Klein bottle does not produce a 3-ball. Moreover, any (n + 1)-cell can be defined as the result of the application of the extension operation to a n-dimensional cellular combinatorial structure; but we don't know how to decide in the general case whether a (simplicial or cellular) combinatorial structure corresponds to a n-sphere. So, we don't know how to decide in the general case whether a combinatorial cell corresponds to a ball.

But it is always possible to associate a simplicial equivalent S(A) with any cellular combinatorial structure A; so, it is always possible to associate a "simplicial" chain complex (S(A)) with any cellular combinatorial structure A, i.e. a chain complex in which any generator corresponds to a simplex of S(A), and such that the homology of (S(A)) is the homology of A. So, the results presented in section 3 can be directly applied, by maintaining at each step of the construction of A its simplicial chain complex (S(A)). The problem here is the complexity of the approach, since it is possible that many simplices in S(A) are associated with one cell in A. So, more efficient approaches have been investigated.

A subclass of cellular combinatorial structures

A subset of cellular combinatorial structures has been defined in [START_REF] Alayrangues | A Boundary Operator for Computing the Homology of Cellular Structures[END_REF] (cf. also [START_REF] Basak | Combinatorial cell complexes and Poincaré duality[END_REF]): each structure A of this subclass satisfies properties so that the cellular chain complex (A) is homologically equivalent to the simplicial chain complex (S(A)). So, the results presented in section 3 can be directly applied to the structures of this subclass, associated with their corresponding cellular chain complexes, but it is necessary to check at each construction step if the properties of the subclass are still satisfied (this control can be done easily without significative cost, due to the definition itself of the properties).

The general case

The properties characterizing this subclass are sufficient but not necessary to ensure the equivalence between (A) and (S(A)). Moreover, it may be useful for some constructions to ignore these properties, even if only temporarily. It can thus be useful to handle A and (S(A)), even if it is less efficient than to handle A and (A). Even in this case, it is possible to optimize the computations. Indeed, the interior of each cell c in A corresponds to a subset of simplices in S(A); a homological equivalence Υ c can be associated with the interior of c when it is created, and it is possible to maintain Υ c during the construction process in order to optimize the homology computation.

More precisely, assume a homological equivalence is associated with the interior of any cell and with any connected component. Assume c is created by an extension operation applied to a connected component C of A. This operation corresponds in S(A) to a cone operation applied to S(C), where the vertex v of the cone symbolizes cell c (in fact, the interior of c corresponds to the subset incident to v, so the structure of the interior of c is very close to the structure of S(C), since c corresponds to a cone on S(C)). Each cell of C remains unchanged, so its homological equivalence is unchanged; the homological equivalence associated with the connected component after operation is trivially defined, since the resulting connected component is a cone; the homological equivalence associated with c can be easily deduced from the homological equivalence associated with C by applying the perturbation lemmas (cf. [START_REF] Rubio | Constructive Homological Algebra and Applications[END_REF] pages 48-49). All computations can be performed in linear time according to the size of S(C). Note that, at last, some reduction process may be applied to the small chain complex of Υ c . Let Ident(A, A 0 ) be the result of the identification of cells of a subset A 0 in A. Let c be a cell of Ident(A, A 0 ): either c does not result from the identification of cells, and its homological equivalence Υ c is not modified; either it results from the identification of isomorphic cells, and Υ c is simply a homological equivalence associated with one of these identified cells (all these homological equivalences are homologically equivalent, since the cells are isomorphic): so, nothing is really computed.

The homological equivalence associated with S(Ident(A, A 0 )) is computed in the following way. A homological equivalence Υ 1 A 0 is computed as the direct sum of homological equivalences corresponding to the identified cells; more precisely (and as for the simplicial case), if k isomorphic i-cells {c j } j∈ [1,k] are identified into one cell, there are in Υ 1 A 0 k -1 copies of Υ cj , for some j ∈ [1, k] (for instance, j may be chosen according to the complexity of Υ cj ). It is now possible to deduce from Υ 1 A 0 a homological equivalence Υ 2 A 0 by "linking" the homological equivalences corresponding to cells accordingly to the boundary relations between cells in A; this can be done by applying the pertubation lemmas (cf. [START_REF] Rubio | Constructive Homological Algebra and Applications[END_REF] pages 48-49), and the complexity is linear according to the size of Υ 1 A 0 and n, where n is the highest dimension of a cell in A 0 . Then, a reduction process can be applied to the small complex of Υ 2 A 0 , producing Υ 0 : C(A 0 ) ⇐ ⇐ ⇐ C B (A 0 ) ⇒ ⇒ ⇒ C S (A 0 ). Moreover, a short exact sequence Q = (C(A 0 ), (S(A)), (S(Ident(A, A 0 ))), i, j, r, s) can be computed in linear time according to the size of S(A) (as for the simplicial case, the complexity of the computation of the "interesting" information is sub-linear). The SES theorem can then be applied in order to deduce a homological equivalence Υ I associated with Ident(A, A 0 ); as for the simplicial case, a reduction process can be applied to the small complex of Υ I , and a "better" homological equivalence Υ I can be deduced.

As for the simplicial case in section 3, similar remarks about the complexity of the process can be done (the main difference with the simplicial case is the complexity of the computation of Υ 0 , which depends also on the dimension of the identified cells). At last, note that a similar process can also be applied for the inverse of the identification operation.

  ) and g : (C S , ∂ S ) → (C, ∂) are chain-complex morphisms; (3) h : (C, ∂) → (C, ∂) is a graded module morphism of degree +1. They satisfy 2 : (4) gf = id C S ; (5) f g + h∂ + ∂h = id C ; (6) hf = gh = hh = 0. Reduction ρ will be sometimes symbolized by (C, ∂) ρ ⇒ ⇒ ⇒ (C S , ∂ S ). The homologies of (C, ∂) and (C S , ∂ S ) are isomorphic, and 1 Obviously, other operations are useful for Geometric Modeling applications, and a similar study has to be done for each operation. 2 f g denotes g • f .

Fig. 1 .

 1 Fig. 1. Incremental computation of homological equivalences

An elementary reduction can be defined when a i-dimensional generator x appears in the boundary of a (i + 1)-generator y with a coefficient equal to 1 or -1. Note that reductions exist, which are not compositions of elementary reductions.

For instance, when Υ 2 is deduced from i, j, r, s, Υ 0 and Υ 1 , the generators of C S2 are that of C S0 and C S1 .

These structures have been defined in different contexts; they are sometimes referred to as orders, Hasse diagrams, etc.

It is not possible to unambiguously represent with incidence graphs "objects" in which a cell is incident several times to another one, but this is possible with combinatorial maps.

Acknowledgments. Many thanks to Francis Sergeraert, Sylvie Alayrangues and Laurent Fuchs.