[Back]


Talks and Poster Presentations (with Proceedings-Entry):

J. Fichte, M. Hecher, P. Thier, S. Woltran:
"Exploiting Database Management Systems and Treewidth for Counting";
Talk: PADL 2020 - The 22nd International Symposium on Practical Aspects of Declarative Languages, New Orleans, Louisiana, United States; 2020-01-19 - 2020-01-25; in: "Practical Aspects of Declarative Languages - 22nd International Symposium, {PADL} 2020, New Orleans, LA, USA, January 20-21, 2020, Proceedings", (2020), 151 - 167.



English abstract:
Bounded treewidth is one of the most cited combinatorialinvariants, which was applied in the literature for solving several countingproblems efficiently. A canonical counting problem is#Sat, which asksto count the satisfying assignments of a Boolean formula. Recent workshows that benchmarking instances for#Satoften have reasonably smalltreewidth. This paper deals with counting problems for instances of smalltreewidth. We introduce a general framework to solve counting questionsbased on state-of-the-art database management systems (DBMS). Ourframework takes explicitly advantage of small treewidth by solving in-stances using dynamic programming (DP) on tree decompositions (TD).Therefore, we implement the concept of DP into a DBMS (PostgreSQL),since DP algorithms are already often given in terms of table manipula-tions in theory. This allows for elegant specifications of DP algorithmsand the use of SQL to manipulate records and tables, which gives usa natural approach to bring DP algorithms into practice. To the bestof our knowledge, we present the first approach to employ a DBMS foralgorithms on TDs. A key advantage of our approach is that DBMSnaturally allow to deal with huge tables with a limited amount of mainmemory (RAM), parallelization, as well as suspending computation.


Related Projects:
Project Head Stefan Woltran:
HYPAR

Project Head Stefan Woltran:
START


Created from the Publication Database of the Vienna University of Technology.