Ubuntu equivalent of Yum's WhatProvides, to find which package provides a file

I believe apt-file will give you what you want.

$ apt-file update$ apt-file list mysqladminkmysqladmin: /usr/bin/kmysqladmin$ apt-file search mysqladminautoconf-archive: /usr/share/aclocal/ac_prog_mysqladmin.m4autoconf-archive: /usr/share/autoconf-archive/html/ac_prog_mysqladmin.htmlbash-completion: /etc/bash_completion.d/mysqladminkmysqladmin: /usr/bin/kmysqladmin$ apt-file search mysqladminmysql-admin: /usr/share/mysql-gui/administrator/mysqladmin_health.xmlmysql-admin: /usr/share/mysql-gui/administrator/mysqladmin_startup_variables_description.dtdmysql-admin: /usr/share/mysql-gui/administrator/mysqladmin_startup_variables_description.xmlmysql-admin: /usr/share/mysql-gui/administrator/mysqladmin_status_variables.xmlmysql-admin: /usr/share/mysql-gui/administrator/mysqladmin_system_variables.xmlmysql-client-5.1: /usr/bin/mysqladminmysql-client-5.1: /usr/share/man/man1/mysqladmin.1.gzmysql-cluster-client-5.1: /usr/bin/mysqladminmysql-cluster-client-5.1: /usr/share/man/man1/mysqladmin.1.gzmysql-testsuite: /usr/lib/mysql-testsuite/r/mysqladmin.resultmysql-testsuite: /usr/lib/mysql-testsuite/t/mysqladmin.test

I use dpkg -S filename for that. It can't search for files that are not installed on your system with it, but it's shipped in all dpkg distros by default while apt-file is not.

You also can look that up for files that are not installed on your system using http://packages.ubuntu.com/ website.