Q:

How to find out which package installed a symlink

In this question I describe my problems finding out the package that installed the final target of the /usr/bin/rename command. dpkg -S /usr/bin/rename did not give a result, but after first finding out that that was a link, I found a general solution for that.
Since /usr/bin/rename points to /etc/alternatives/rename I know how this particular link is managed by update-alternatives.
How can I find out which package actually installed a symlink, if I would not have that kind of knowledge? If there is no simple command to do so, what is a general strategy to find out which command did set up a symlink?

A:

dpkg -S can't tell you which package installed the symlink because it only looks at the files that were unpacked from the packages. This information is provided by the *.list files in /var/lib/dpkg/info/*.list.
Every file on a Debian system can only be owned by one package. If you try to install a package that contains a file that is already provided by another package, one of the following things will happen:

dpkg will refuse to install the second package.
dpkg will remove the first package before it installs the second package (if the second package specifies a Breaks or Conflicts relationship to the first package).
dpkg will upgrade the first package to a newer version that no longer provides the file before it installs the second package (if the second package specifies a Conflicts/Breaks and a Replaces relationship to the first package).
dpkg will install the second package alongside the first package, and will overwrite the file with the one provided by the second package (if the second package specifies a Replaces relationship to the first package).

Obviously, this doesn't really allow for multiple packages that provide the same command and can be installed at the same time, so this is where the alternatives system of Debian comes in. The packages provide their files with different names, for example:
host ~ # dpkg -S /usr/bin/prename 
perl: /usr/bin/prename

and the package postinst script (/var/lib/dpkg/info/perl.postinst) registers it as an alternative:
# util-linux has an alternate rename
update-alternatives --install /usr/bin/rename rename /usr/bin/prename 60 \
--slave /usr/share/man/man1/rename.1.gz rename.1.gz \
    /usr/share/man/man1/prename.1.gz

That is the reason why dpkg -S doesn't know about /usr/bin/rename.

How can I find out which package actually installed a symlink, if I would not have that kind of knowledge?

Debian packages can provide symlinks, so as long as it's not an alternatives symlink (or a symlink that was created by the postinst for some other reason), dpkg -S will work fine.
In the case of the alternatives system, just follow the symlink trail:
host ~ # dpkg -S $(readlink -f /usr/bin/rename)
perl: /usr/bin/prename

Of course this may lead you to wrong conclusions for example when a package creates a symlink in it's postinst that points to a file provided by another file. In such cases, there's no general way to figure out the responsible package - you will have to do some detective work, for example by grepping through the *.postinst files.

