Obsolete packages vs. orphaned packages

Question

What is the difference between obsolete and orphaned packages? More specifically, why does deborphan produce this:

dave@ubuntu:~$ deborphan
libbind9-80
libllvm3.1
libgrail5
libpython3.2
libsvga1
libarchive12
libdirectfb-1.2-9
gcalctool
liblwres80
libqpdf8
libkms1
libnux-3.0-0

... while aptitude search '~o' produces this:

dave@ubuntu:~$ aptitude search '~o'
idA libarchive12                                 - Multi-format archive and compression library (shared li
i   libbind9-80                                  - BIND9 Shared Library used by BIND                      
i   libdns81                                     - DNS Shared Library used by BIND                        
i   libdrm-nouveau1a                             - Userspace interface to nouveau-specific kernel DRM serv
idA libgrail5                                    - Gesture Recognition And Instantiation Library          
i   libisc83                                     - ISC Shared Library used by BIND                        
i   libisccc80                                   - Command Channel Library used by BIND                   
i   libisccfg82                                  - Config File Handling Library used by BIND              
i   liblwres80                                   - Lightweight Resolver Library used by BIND              
idA libnux-3.0-0                                 - Visual rendering toolkit for real-time applications - s
idA libnux-3.0-common                            - Visual rendering toolkit for real-time applications - c
idA libpython3.2                                 - Shared Python runtime library (version 3.2)            
idA libqpdf8                                     - runtime library for PDF transformation/inspection softw
i   libudev0                                     - udev library                                           
i A linux-headers-3.5.0-27                       - Header files related to Linux kernel version 3.5.0     
i A linux-headers-3.5.0-27-generic               - Linux kernel headers for version 3.5.0 on 32 bit x86 SM
i   linux-image-3.5.0-27-generic                 - Linux kernel image for version 3.5.0 on 32 bit x86 SMP 
i   linux-image-extra-3.5.0-27-generic           - Linux kernel image for version 3.5.0 on 32 bit x86 SMP 
i   python3.2                                    - Interactive high-level object-oriented language (versio
i   python3.2-minimal                            - Minimal subset of the Python language (version 3.2)

Bonus question: apt-get autoremove is even more different. Why?

dave@ubuntu:~$ sudo apt-get --purge autoremove
[sudo] password for dave: 
Reading package lists... Done
Building dependency tree       
Reading state information... Done
The following packages will be REMOVED:
  gksu* libarchive12* libdirectfb-1.2-9* libgksu2-0* libgnome-menu2* libgrail5* libllvm3.1*
  libnux-3.0-0* libnux-3.0-common* libpython3.2* libqpdf8* libsvga1* libts-0.0-0* libx86-1*
  mobile-broadband-provider-info* python-imaging* python-imaging-compat* python-    oauth* tsconf*
0 upgraded, 0 newly installed, 19 to remove and 0 not upgraded.
After this operation, 33.8 MB disk space will be freed.
Do you want to continue [Y/n]? n
Abort.

In case anyone wants to know, the upgrade to 13.04 is what prompted this.

Answer 1

For short, obsolete packages are not in any repository on your list anymore. Orphaned packages are automatic dependencies whose "dependants" have all been uninstalled. And apt-get autoremove only considers orphaned packages that were installed by apt to resolve dependencies.

Obsolete packages

As you probably know, apt keeps a list of repositories it can fetch packages from. But sometimes, packages are removed from a repository. Maybe nobody takes care of (maintains) the package any more, and the (very) old last version available has become a security risk. Or maybe the program has changed its name, the package names were changed accordingly and the old packages under the old name are removed. There are other possible reasons why a package is removed from a repository, as well.

If a package is installed on your system, but can no longer be found in any of the repositories your apt has on its lists, that package is considered "obsolete".

Orphaned packages

As you probably know as well, apt can manage dependencies between packages. Say for example, a program called "greatprogram" needs a library called "greatlibrary" to work. So, the package containing greatlibrary can be marked as a automatic dependency of the package containing greatprogram. You won't be able to install the greatprogram package, unless greatlibrary is already installed (or will be installed with the same command).

But what if you uninstall greatprogram on a later day and leave greatlibrary behind? In that case, once at least one other package needed greatlibrary as a dependency, but now no other package does any longer. Those "left behind" packages are called "orphaned packages".

apt-get autoremove

Still another fact you probably know, is that apt can resolve dependencies automatically for you. Say you want to install the before mentioned greatprogram, but don't have greatlibrary installed yet. apt-get "notices" that there is an unsatisfied dependency and offers you to install greatlibrary as well.

apt-get autoremove offers you to remove any orphaned packages that have been installed this way to resolve a dependency. Orphaned packages that have been installed in other ways are not in autoremove's list. If, say, you installed greatlibrary yourself before installing greatprogram, and on a later day uninstall greatprogram, greatlibrary would still be orphaned. But autoremove would not take care of it, because it has not been installed automatically as a result of an resolved dependency.