What does cardinality mean?

Legacy questions from answers.semanticweb.com
,
#1

Cardinality of the results of a query is usually mentioned when studying papers related to SPARQL, rdf, etc...however, I am unable to understand what does cardinality here really means. I am a novice to SPARQL and rdf so can somebody be kind enough to explain what does cardinality means in SPARQL and rdf.

Cardinality in databases refers to uniqueness of values, what w.r.t to SPARQL and the results of its query does cardinality mean...I am really confused. Somebody please explain.

As it refers to unique values then what does maximum Cardinality and minimum Cardinality mean?

#2

Cardinality in SPARQL papers usually refers to the number of triples that match a basic graph pattern (BGP) in a SPARQL query. The cardinality is used to order the joined BGPs in the query, so that BGPs with a smaller cardinality (less solutions) are executed first. This can greatly reduce the number of solutions and joins that need to be evaluated, and therefore improves performance of the query evaluation. E.g with the following query:

SELECT * WHERE {
   ?subj <u:1> ?obj1 .     # assume cardinality 1000 when ?subj and ?obj are not known
   ?subj <u:2> "string" .  # assume cardinality 5 when ?subj is not known
}

When evaluating the BGPs from top to bottom, 1000 solutions for the first BGP need to be loaded, and joined with the second BGP. When evaluation starts with the second BGP only 5 solutions need to be loaded, and because then ?subj is known, the other BGP will now have a much smaller cardinality.

#3

see http://www.w3.org/TR/owl-ref/#cardinality-def

Cardinality is the number of distinct values that a property has in a restriction class. Minimum and Maximum Cardinality are the least and most amount of distinct values that the property can have. eg. if a restriction class has a cardinality of 5 on a property - it can have 5 semantically distinct values for that property

This is rather difficult to interpret in an Open World Assumption without the Unique Name Assumption. This is due to the fact that the Open World Assumption means that there can be other values that we haven't specified (unless we've specified otherwise), while the Unique Name Assumption means that its more difficult to infer that objects are indeed semantically different.