Graph database are increasingly popular for data management and analytics. As with every data model, managing the integrity of entities is fundamental for data governance but also important for the efficiency of update and query operations. In response to current shortcomings of uniqueness and existence constraints in graph databases, we propose a new principled class of constraints that separates uniqueness from existence properties, and fully supports the use of multiple labels and composite properties. We illustrate benefits of the constraints on real-world examples in terms of utilizing the node integrity they enforce for better update and query performance. We establish axiomatic and algorithmic characterizations for reasoning about any set of constraints in our new class. In addition, we give examples of small node samples that satisfy the same constraints as the original data set, and are therefore useful for domain experts to spot integrity faults and validate the meaningfulness of the constraints. Finally, we give four recommendations for graph database systems to extend their capabilities in terms of uniqueness constraints.