+1  A: 

The primary key will never be "all of the fields in a table". This is not how relational databases are supposed to work, so forget that approach.

The key is a key, and data is data. Never ever mix the two up. If you mix them, you end up with a situation where you need to change the key and all records in the database that use it as soon as the data changes. Which is bad.

The only proper way to design this (common) 1:n relationship is:

Address               PhoneNumber
-------               -----------
 *ID         <---+     *ID
 StreetNumber    +---  AddressID
 HouseNumber           RegionNumber
 City                  TheNumber
 Country               ...
 ...

The * denote primary keys, typically an auto-incrementing number with a unique index on it.

The arrow denotes a foreign key relationship.

Tomalak
In my first approach, the key isn't all the fields in the table, it's only the keys that connects the table with the other table. When I use the second approach, then I have to add a uniqueness constraint on all those fields, which are logically form a primary key. I guess that if I add a uniqueness constraint, then I have to also add an index on those fields, since uniqueness without index will be slow (right?). By the way, in my scenario, the ID is never updated, so it seemed right to define those fields as primary.
Andy
You are not very clear on which of your fields *are* keys, then. Maybe you should edit the question to make the fields you think should be key bold or the like, because I don't understand your idea #1. In your idea #2 you do it the wrong way around: By defining a PhoneNumberID in the Address table, you set your data model up for multiple addresses per phone number.
Tomalak
A: 

Whether or not you have GUID the second option is easier to code and design. When you select data by joining two tables you'll only need the identifier columns indexed. The other way you need composite indexes for just this join.

Having unique primary keys in tables in a enterprise corporate system is a valuable practice in my experience. (from both dba and developer perspective)

Designing database for performance is a complicated issue involving many criteria. Rather then go after the theory, if you have Oracle at hand play with your two approaches in practice and use explain plan tools. I mean create tables with your mentioned approaches, play with indexes and use explain plan. If I am not mistaken Oracle even gives you an idea about query performance by projection (i.e. by letting you estimate number of rows in tables). I'm not sure about Express Edition version has this support

I still need uniqueness constraint on those fields, so shouldn't I index them in both of the approaches? (I thought that uniqueness constraint validation is faster when the fields are indexed, but maybe I wrong...)
Andy