It's likely an rpm bug checking erasure dependencies.

Here's what I see on FC7:

# rpm -e policycoreutils audit-libs-python kernel-headers
error: Failed dependencies:
        policycoreutils >= 2.0.7-5 is needed by (installed) selinux-policy-2.5.10-2.fc7.noarch
        /sbin/restorecon is needed by (installed) xorg-x11-xfs-1.0.2-3.1.i386
        kernel-headers >= 2.6.18 is needed by (installed) audit-libs-devel-1.5.1-2.fc7.i386
        kernel-headers is needed by (installed) glibc-headers-2.5.90-19.i386
        kernel-headers >= 2.2.1 is needed by (installed) glibc-headers-2.5.90-19.i386
# rpm --version
RPM version 4.4.9

Perhaps closer to your original reproducer:

# rpm -V bind
# rpm -e policycoreutils
error: Failed dependencies:
        policycoreutils >= 2.0.7-5 is needed by (installed) selinux-policy-2.5.10-2.fc7.noarch
        /sbin/restorecon is needed by (installed) xorg-x11-xfs-1.0.2-3.1.i386
# rpm -e policycoreutils --nodeps
# rpm -V bind
Unsatisfied dependencies for bind-9.4.0-3.fc7.i386:
        Requires: policycoreutils

Running
    # rpm -evv policycoreutils
shows no attempt to check whether bind has Requires: policycoreutils.

And the reason is because of the added attribute RPMSENSE_SCRIPT_POST
in the bind package spec file:
...
%if %{selinux}
Requires(post): policycoreutils
%endif
...

The attribute "...(post)" indicates the dependency is only needed for installing
bind and is unnecessary for running bind (assuming the spec file is correct).

So the --verify transaction check is generating misleading information because
its checking both the installing and the installed dependency contexts. Only the
installed context is meaningful for an installed package.

FWIW -- assuming the bind spec file is written correctly -- there is no flaw in the erasure dependency 
checking.

There is a flaw in --verify dependency checking, which needs to check only the installed, not the 
installing, dependency context.

Fixed (by testing the signgle package transaction using rpmtsAddEraseElement() rather than 
rpmtsAddInstallElement(), which tests installed+erasing rather than installing+installed dependency 
context) in rpm cvs, will be in rpm-4.4.9-0.4 when built.

Thanks for noticing.

UPSTREAM

Thank you, Jeff! I wonder if Paul is considering rpm-4.4.9 for fc7? Or maybe
just keep back-patching the 4.4.2 that is in rawhide. :-/

Hmmm, my analysis is sound, but I likely have to implement a bit more carefully than what
I tried. I changed from attempting a single package install to a single package
erase, which works for your case, but appears to have additional side effects.

So I'll add a bit mask to limit the dependency check context to only installed dependencies

User pnasrat's account has been closed

Reassigning to owner after bugzilla made a mess, sorry about the noise...

Verified still occurs in F7.

# yum -d1 -y erase audit-libs-python

=============================================================================
 Package                 Arch       Version          Repository        Size 
=============================================================================
Removing:
 audit-libs-python       i386       1.5.3-1.fc7      installed         213 k
Removing for dependencies:
 policycoreutils         i386       2.0.16-11.fc7    installed         2.1 M

Transaction Summary
=============================================================================
Install      0 Package(s)         
Update       0 Package(s)         
Remove       2 Package(s)         


Removed: audit-libs-python.i386 0:1.5.3-1.fc7
Dependency Removed: policycoreutils.i386 0:2.0.16-11.fc7
# rpm -V bind
Unsatisfied dependencies for bind-9.4.1-8.P1.fc7.i386: policycoreutils
# yum -d1 -y install policycoreutils   

=============================================================================
 Package                 Arch       Version          Repository        Size 
=============================================================================
Installing:
 policycoreutils         i386       2.0.16-11.fc7    updates           617 k
Installing for dependencies:
 audit-libs-python       i386       1.5.3-1.fc7      fedora             67 k

Transaction Summary
=============================================================================
Install      2 Package(s)         
Update       0 Package(s)         
Remove       0 Package(s)         

Total download size: 683 k

Installed: policycoreutils.i386 0:2.0.16-11.fc7
Dependency Installed: audit-libs-python.i386 0:1.5.3-1.fc7
# rpm -V bind
#

This message is a reminder that Fedora 7 is nearing the end of life. Approximately 30 (thirty) days from now Fedora will stop maintaining and issuing updates for Fedora 7. It is Fedora's policy to close all bug reports from releases that are no longer maintained. At that time this bug will be closed as WONTFIX if it remains open with a Fedora 'version' of '7'.

Package Maintainer: If you wish for this bug to remain open because you plan to fix it in a currently maintained version, simply change the 'version' to a later Fedora version prior to Fedora 7's end of life.

Bug Reporter: Thank you for reporting this issue and we are sorry that we may not be able to fix it before Fedora 7 is end of life. If you would still like to see this bug fixed and are able to reproduce it against a later version of Fedora please change the 'version' of this bug. If you are unable to change the version, please add a comment here and someone will do it for you.

Although we aim to fix as many bugs as possible during every release's lifetime, sometimes those efforts are overtaken by events. Often a more recent Fedora release includes newer upstream software that fixes bugs or makes them obsolete. If possible, it is recommended that you try the newest available Fedora distribution to see if your bug still exists.

Please read the Release Notes for the newest Fedora distribution to make sure it will meet your needs:
http://docs.fedoraproject.org/release-notes/

The process we are following is described here: http://fedoraproject.org/wiki/BugZappers/HouseKeeping

Moving to rawhide, the bug still exists in Fedora 9 and later.

this bug is still present in rpm-4.5.90-0.git8426.8

for example:

# rpm -e xorg-x11-filesystem
# rpm -V libX11
Unsatisfied dependencies for libX11-1.1.4-2.fc10.x86_64:
	xorg-x11-filesystem >= 0.99.2-3 is needed by libX11-1.1.4-2.fc10.x86_64

(aside) This is an xorg-x11-filesystem packaging flaw:

     Requires(pre): filesystem >= 2.3.7-1

Clearly the contents of filesystem are needed after xorg-x11-filesystem
is installed. The (pre) marker asserts the filesystem is _ONLY_ needed
while installing, not after being installed, which is obviously false.

There's a similar packaging flaw in libX11:

     Requires(pre): xorg-x11-filesystem >= 0.99.2-3

an assertion that xorg-x11-filesystem is needed _ONLY_ while
installing, not after being installed.

Get the assertions correct and rpm will honor the assertions.

This bug appears to have been reported against 'rawhide' during the Fedora 10 development cycle.
Changing version to '10'.

More information and reason for this action is here:
http://fedoraproject.org/wiki/BugZappers/HouseKeeping

*** Bug 472943 has been marked as a duplicate of this bug. ***

*** Bug 476275 has been marked as a duplicate of this bug. ***

*** Bug 520426 has been marked as a duplicate of this bug. ***

Fixed upstream now and is backportable...

Fixed in rawhide as of rpm-4.9.0-0.beta1.1.fc15.