It must be possible to get the same effect without copying the files by using links. If it is all on the same file system then hardlinks would work and be very space efficient.

Extended attributes can do this for most unixy operating systems. See fsetattr and fgetattr. It's a bit tricky in that the standard tools, like find, don't support them directly. But, the tags stay with the files, no separate DB needed. You do have to pay attention to copying, backups, etc, to make sure they are preserved, and no separate DB means all "queries" are full scans.