Relay not switching immediately if mains off to battery like UPS
Here's a simple solution, using Schottky diode switching.

The output voltage of the 7812 power supply is to be kept marginally higher than that of the battery in order to reverse bias the Schottky diode and isolate the battery as long as the power supply is available.
That would be possible by increasing the reference voltage with an additional diode in series for every 0.7 V increase.