I was complaining recently about the poor state of UPRN data. But it turns out I was mostly wrong and the problem was my poor research abilities (or things have changed for the better recently). A Disqus conversation led me to this page which provides the links between different identifiers.
These are all CSV files that can be imported into your favourite database. To get the street name of a UPRN, we need to download the UPRN -> USRN links file. Once we've got the USRN, we need to download the Road TOID -> USRN links file. Once we've got the TOID, we can link to the street name using the OS Open Names download (it's probably also possible to do this using the OS Open Roads download but that's a bit more difficult to process).
We're still not able to construct an open version of PAF but we are slowly creeping closer towards that.
So I've pulled all that data into this site and started displaying it in a couple of places (like here and here) but I'm keen to hear suggestions for other potential uses for this data e.g. all the roads in a postcode area/district/sector, all the postcodes for a road.