Bases de Datos - Ayuda en base de datos mysql

Por favor necesito ayuda en la elaboración de una base de datos, lo que estoy haciendo es un pequeño software, lo que quiero es un combobox que aparezca los departamentos y en el otro combo la provincias y aparte de eso quisiera hacer un buscardor, teniendo en cuenta los combos, el sexo si es hombre solo hombres y si es mujer solo mujer y si quiero todo que me busque todo y