Witold Lipski

Polish computer scientist

Witold Lipski Jr.

Witold Lipski autoportrait

Born| July 13, 1949

Warsaw, Poland

Died| May 30, 1985(1985-05-30) (aged 35)

Nantes, France.

Nationality| Polish
Alma mater|

* Polish Academy of Sciences (Habilitation)
* Polish Academy of Sciences (PhD)
* Warsaw Technical University (BE/ME)

Known for| combinatorics, incomplete information, VLSI, Witold Lipski Prize
Scientific career
Fields|

* Computer Science
* Databases
* Combinatorics
* VLSI
* Graph Theory
* Logic
* Computational Geometry

Institutions|

* Polish Academy of Sciences
* University of Illinois at Urbana–Champaign
* University of Paris

Doctoral advisor| Wiktor Marek
Doctoral students|

* Tomasz Imieliński
* Zbigniew Michalewicz

Witold Lipski Jr. (July 13, 1949 – May 30, 1985) was a Polish computer scientist (habilitation in computer science), and an author of the books Combinatorics for Programmers (two editions) and (jointly with Victor W. Marek) Combinatorial analysis.

Lipski and his PhD student Tomasz Imieliński worked on the foundations of the theory of incomplete information in relational databases.

## Life

[edit]

Lipski was born in Warsaw. He graduated from the Program of Fundamental Problems of Technology, at the Warsaw Technical University. He received a PhD in computer science at the Computational Center (later: Institute for Computer Science) of the Polish Academy of Sciences, under the supervision of Victor W. Marek. Lipski's dissertation was on the topic of information storage and retrieval systems and titled 'Combinatorial Aspects of Information Retrieval'.[1] His habilitation was granted by the Institute of Computer Science of Polish Academy of Sciences. Lipski spent academic year 1979/1980 at the University of Illinois at Urbana–Champaign, and the last two years before his death, at the University of Paris.

Jointly with his doctoral student Tomasz Imieliński, Lipski investigated foundations of treatment of 'Incomplete Information in Relational Databases'. Their results were published from 1978 through 1985.[2][3][4][5] This produced a fundamental concept later known as Imieliński–Lipski algebras.[6][7][8]

With Imieliński, Lipski studied the semantics of relational databases. These investigations were based on the theory of cylindric algebras, a topic studied within universal algebra. According to Jan Van den Bussche,[9] the first people from the database community to recognize the connection between Edgar Codd's relational algebra and Alfred Tarski's cylindric algebras were Lipski and Imieliński, in a talk given at the very first edition of PODS (the ACM Symposium on Principles of Database Systems), in 1982. Their work "The relational model of data and cylindric algebras" was published in 1984.[10]

Lipski contributed to research on algorithm analysis, discovering a number of efficient algorithms applicable to the analysis of VLSI devices (with Franco P. Preparata),[11] time-sharing in database implementations (with Christos Papadimitriou),[12] and computational geometry as applied to shape recognition (again with Preparata).[13]

Lipski wrote the combinatorial algorithms textbook Kombinatoryka dla Programistow (Combinatorics for Programmers), which was published in two editions (one posthumous) and was translated into Russian.

Jointly with Marek, Lipski published a monograph on combinatorial analysis.

## Personal life

[edit]

Lipski's father was economist and politician Witold Lipski (1925–1998) [pl].

He had two children: Kasia (an endocrinologist) and Witold (a neuroscientist).

Lipski died in Nantes, France, after a battle with cancer. He is buried in Powązki Cemetery in Warsaw, Poland, (Location: C/39 (5/7)).

## Witold Lipski Award

[edit]

The Witold Lipski Award is the most prestigious award for young computer scientists in Poland. The award recognizes achievements in the field of theoretical and applied computer science. It was created by the initiative of a group of Polish computer scientists active outside of Poland and in Poland.

Submissions for the award are limited to applicants with exceptional accomplishments, who are younger than 30, or who are younger than 32, in case that a candidate was on maternity/paternity leave. The award is administered by the (Polish) Foundation for Computer Science Research,[14] in cooperation with Polish Chapter of the Association for Computing Machinery, and the Polish Computer Science Society [pl].

Starting in 2024, the Kosciuszko Foundation has handed over the role of organizing the award to the research and development center IDEAS NCBR [15] in Warsaw. The official competition website is now hosted at: https://nagrodalipskiego.ideas-ncbr.pl/

## See also

[edit]

* Null (SQL)

## References

[edit]

1. ^ Rough Sets and Intelligent Systems - Professor Zdzisław Pawlak in Memoriam. Springer Berlin Heidelberg. 16 August 2012. pp. 178, 652. ISBN 9783642303449.
2. ^ Lipski Jr., W. (1979). "On Semantic Issues Connected with Incomplete Information Databases". ACM Transactions on Database Systems. 4 (3): 262–296\. doi:10.1145/320083.320088. S2CID 8383997.
3. ^ Imieliński, T.; Lipski Jr., W. (1981). "On Semantic Issues Connected with Incomplete Information Databases". Proceedings VLDB. 4 (3): 388–397.
4. ^ Lipski Jr., W. (1981). "On Databases with Incomplete Information". Journal of the ACM. 28 (1): 41–70\. doi:10.1145/322234.322239. S2CID 18878482.
5. ^ Imieliński, T.; Lipski Jr., W. (1984). "Incomplete information in relational databases". Journal of the ACM. 31 (4): 761–791\. doi:10.1145/1634.1886. S2CID 288040.
6. ^ Green, T.J.; Karvounarakis, G.; Tannen, Val (2007). "Provenance Semiring". Proc. ACM SIGMOD-SIGACT-SIGART, PODS: 31–40.
7. ^ T.J. Green (2009). Models for Incomplete and Probabilistic Information; Chapter 2, in Managing and Mining Uncertain Data. Springer Link.
8. ^ Karvounarakis, G.; Green, T.J. (2012). "Semiring-Annotated Data: Queries and Provenance" (PDF). ACM SIGMOD. 41 (3): 5–14\. doi:10.1145/2380776.2380778. S2CID 11600847.
9. ^ Feferman, S. (2006). "Tarski's influence on computer science" (PDF). Logical Methods in Computer Science. 2 (3). arXiv:cs/0608062. Bibcode:2006cs........8062F. doi:10.2168/lmcs-2(3:6)2006. S2CID 2567206.
10. ^ Imieliński, T.; Lipski Jr., W. (1984). "The relational model of data and cylindric algebras". Journal of Computer and System Sciences. 28 (1): 80–102\. doi:10.1016/0022-0000(84)90077-1.
11. ^ Preparata, FP.; Lipski Jr., W. (1984). "Optimal three-layer channel routing". IEEE Transactions on Computers. 33 (5): 427–437\. doi:10.1109/TC.1984.1676459. S2CID 33260007.
12. ^ Lipski Jr, W.; Papadimitriou, Ch. (1981). "A fast algorithm for testing for safety and detecting deadlocks in locked transaction systems". Journal of Algorithms. 2 (3): 211–226\. doi:10.1016/0196-6774(81)90023-7.
13. ^ Lipski Jr, W.; Preparata, FP. (1980). "Finding the contour of a union of iso-oriented rectangles". Journal of Algorithms. 1 (3): 235–246\. doi:10.1016/0196-6774(80)90011-5.
14. ^ "Polish Foundation for Computer Science Research".
15. ^ "IDEAS NCBR".

Authority control databases

International|

* ISNI
* VIAF
* WorldCat

National|

* United States
* Italy
* Norway
* Croatia
* Poland

Academics|

* Mathematics Genealogy Project
* zbMATH
* DBLP
* MathSciNet