Perhaps a more apt analogy is that of a public library: The library may be public, but most state laws require that your records be kept confidential. The same goes for public education (FERPA). The same goes for healthcare (HIPPA).
If I go to a doctor, I do not expect them to send me mail that can disclose my medical history to an incidental observer, which has unfortunately happened to patients in both the UK and US, and people were rightfully angry about it (https://www.theguardian.com/technology/2015/sep/02/london-cl... and more recently https://www.statnews.com/2017/08/24/aetna-hiv-envelopes/). You cannot say, "well, you went to a doctor, you even paid with a credit card, and walked on a public sidewalk up to the door, so you must not care about it being private".
I believe that what Walmart did was inappropriate. Maybe not for everyone, but it is for me. (Conversely, I'm quite proud of my GPA & don't mind if it is public knowledge, but my university still won't tell you what it is without my explicit permission, because this kind of information does adversely affect some people, and is therefore protected by FERPA.) Unfortunately, I'm just a single individual and WM probably doesn't care what I think. So be it. I will still make it known, though, that I believe that they violated my privacy.
I'm not "surprised" and I don't think that I acted inconsistently. Rather, I'm frustrated at the lack of confidentiality.
But regarding the "record on their database" bit, you use credit cards and you KNEW that gets recorded in some payment gateway database somewhere. It has nothing to do with Walmart. You just don't like the hassle of using cash.
Give me a break. You use credit or debit cards, they record everything. You go around the internet showing your presence to all the data brokers.
This has nothing to do with Walmart. You'd just for the first time realized that the things you say you care about don't really match up with your actions, and now you're surprised.