Keynote lecture: Certain considerations regarding the database complexity

The general subject of complexity examined from different points of view has been increasingly present in literature. Much work is constantly devoted to the complexity of interrogation procedures for “information systems”, and even for deepening the understanding of the conceptual aspects of the term “complexity” itself. The knowledge of the author is obviously limited, and I must recognize that according to the degree I have been able to inspect the available for me sources the issue of “database complexity” is not very favored by the literature, at least under this name. This is the main reason for the modest attempt contained in this presentation, in the intention to open a new way in studying this matter. A decisive avancement concerning the philosophy and the mathematical theory of complexity was achieved in 1963-1965, when A.N. Kolmogorov published his basic works on algorithmic information theory, generally known today as Kolmogorov complexity. According to Kolmogorov´s definition, the complexity of an object, such as a piece of text, is the measure of computational resources needed to specify that object. In fact, the basic idea, formulated first by A.N. Kolomogorov, is to measure the complexity of an object by the size in bits of the smallest program for computing it. As G.J. Chaitins expresses it, the “algorithmic information theory” is the result of “putting Shannon´s information theory and Turing´s computability theory into a cocktail shaker and shaking vigorously”.