Věřím, že apt-file vám dá to, co chcete.
$ apt-file update
$ apt-file list mysqladmin
kmysqladmin: /usr/bin/kmysqladmin
$ apt-file search mysqladmin
autoconf-archive: /usr/share/aclocal/ac_prog_mysqladmin.m4
autoconf-archive: /usr/share/autoconf-archive/html/ac_prog_mysqladmin.html
bash-completion: /etc/bash_completion.d/mysqladmin
kmysqladmin: /usr/bin/kmysqladmin
$ apt-file search mysqladmin
mysql-admin: /usr/share/mysql-gui/administrator/mysqladmin_health.xml
mysql-admin: /usr/share/mysql-gui/administrator/mysqladmin_startup_variables_description.dtd
mysql-admin: /usr/share/mysql-gui/administrator/mysqladmin_startup_variables_description.xml
mysql-admin: /usr/share/mysql-gui/administrator/mysqladmin_status_variables.xml
mysql-admin: /usr/share/mysql-gui/administrator/mysqladmin_system_variables.xml
mysql-client-5.1: /usr/bin/mysqladmin
mysql-client-5.1: /usr/share/man/man1/mysqladmin.1.gz
mysql-cluster-client-5.1: /usr/bin/mysqladmin
mysql-cluster-client-5.1: /usr/share/man/man1/mysqladmin.1.gz
mysql-testsuite: /usr/lib/mysql-testsuite/r/mysqladmin.result
mysql-testsuite: /usr/lib/mysql-testsuite/t/mysqladmin.test
Používám dpkg -S filename pro to. Nemůže s ním vyhledávat soubory, které nejsou nainstalovány ve vašem systému, ale je standardně dodáván ve všech distribucích dpkg, zatímco apt-file nikoli.
Můžete také vyhledat soubory, které nejsou nainstalovány ve vašem systému, pomocí webové stránky http://packages.ubuntu.com/.