The main challenge should not be the "over a network" requirement, but rather that you need an ActionScript driver for your DBMS. There are some third party libraries, e.g. asSql or Asql (both for MySQL), but I have no experience with either of them.
However, depending on your application, you might really want to consider to introduce some back-end encapsulating business logic and persistence, rather than having the AIR app talk to the remote DBMS directly. Especially for multi-user apps I would definitely discourage you from doing so.. If you want to introduce a back-end, the Java platform is certainly a good choice since there are two very good AMF3 implementations (BlazeDS and GraniteDS). I would also recommend to take a look at the Grails framework and especially the Grails Flex Plugin. There is a nice and informative article on InfoQ about Grails and Flex.