Open AccessRECENT RESULTS ON CARDINALITY ESTIMATION AND INFORMATION THEORETIC INEQUALITIES
Author(s) -
Hung Q. Ngo
Publication year - 2021
Publication title -
journal of computer science and cybernetics (vietnam academy of science and technology)/journal of computer science and cybernetics
Language(s) - English
Resource type - Journals
eISSN - 2815-5939
pISSN - 1813-9663
DOI - 10.15625/1813-9663/37/3/16129
Subject(s) - cardinality (data modeling) , inequality , exposition (narrative) , point (geometry) , mathematics , computer science , connection (principal bundle) , mathematical economics , epistemology , calculus (dental) , algebra over a field , pure mathematics , geometry , data mining , philosophy , medicine , art , mathematical analysis , literature , dentistry
I would like to dedicate this little exposition to Prof. Phan Dinh Dieu, one of the giants and pioneers of Mathematics in Computer Science in Vietnam.In the past 15 years or so, new and exciting connections between fundamental problems in database theory and information theory have emerged. There are several angles one can take to describe this connection. This paper takes one such angle, influenced by the author's own bias and research results. In particular, we will describe how the cardinality estimation problem -- a corner-stone problem for query optimizers -- is deeply connected to information theoretic inequalities. Furthermore, we explain how inequalities can also be used to derive a couple of classic geometric inequalities such as the Loomis-Whitney inequality.A purpose of the article is to introduce the reader to these new connections, where theory and practice meet in a wonderful way. Another objective is to point the reader to a research area with many new open questions.