File system that uses tags rather than folders?
Here are some file systems which I found using google.
TagFS - "Tag Semantics for Hierarchical File Systems" paper by Stephan Bloehdorn and Max Völkel, 2006 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.60.4187
dhtfs - "Tagging based filesystem, providing dynamic directory hierarchies based on tags associated with files" a usable implementation, last release 2007 http://code.google.com/p/dhtfs/
Tagsistant - "A reasoning semantic filesystem for Linux and BSD" project under active development http://www.tagsistant.net/
Leaftag - "Tagging for the Linux desktop" another implementation, last release 2006 http://www.chipx86.com/w/index.php/Leaftag
On integration with OSes, I dont think it should be that difficult. OSes are deeply dependent on file system hierarchy's but tag based file system can mimic directory structure. For example in a tag based file system the path /etc/init.d
will give all the files that are tagged with exactly two tags i.e 'etc' and 'init.d'. For files which are tagged with other tags as well as these two tags, their extra tags can appear as directories inside /etc/init.d. If there is a file a.txt with three tags i.e 'etc', 'init.d' & 'asdf' then 'asdf' will appear as directory inside /etc/init.d and full path of a.txt will become /etc/init.d/asdf/a.txt.
I'm the author of the Linux program TMSU that lets you tag files and view them in a tag-based filesystem.
Here is some example usage:
$ tmsu tag track.mp3 music genre=indie-rock good year=1999
$ tmsu tag melody.mp3 music
$ tmsu tag DC123.jpg photo landscape country=italy year=2014
$ tmsu files music year = 1999
./song.mp3
And the virtual filesystem:
$ mkdir mp
$ tmsu mount mp
$ ls mp
query tags
$ ls tags
country genre good landscape photo music year
$ ls tags/music
genre good track.1.mp3 melody.2.mp3 year
The numbers in the filenames are identifiers which are there to keep the filenames unique. These are symbolic links back to the files' original locations.
$ ls tags/music/good # you can drill down
genre track.1.mp3 year
$ ls "query/music and good" # this directory gets automatically created
track.1.mp3
It's still in active development. At time of writing (Oct 2014) 0.4.2 is available but I'll be releasing 0.5.0 soon.
What you are asking for is a Database File System. I know of one experimental implementation for Linux called DBFS. Microsoft started developing Windows Future Storage (WinFS) - it was planned to ship with Vista but due to technical problems the project was delayed and as far as I know finally canceled. NTFS is also capable of storing metadata for files but not to an extend of a full featured database file system.
The integration of such a file system into an operating system should not be that complicated for the core of the operating system - it can simply stick with the hierarchical model. The complex part is the (graphical) shell that must expose the structure and capabilities of the file system to the user.
Vista and Windows 7 support tagging of files. See this article
Try tagfs. It's a fuse based user space file system. It can show tagged directories from a source directory in a tag filter view.
E.g. let's say you have a directory 'vacation india' which is tagged 'india' and 'photos' and a directory 'vacation spain' tagged 'spain' and 'photos'. You can filter all your photos by entering the path '/my_mountpoint/photos'.
Directories are tagged through a simple text file. A file named '.tag' in the directory contains the tags. Multiple tags are separated by newlines.