Access controls determine which users are allowed to query and update the information that is stored in a database. Despite their rapidly increasing importance, XML and object DBMSs do not have a standardized and well-understood access control model. This reduces their practicality in the commercial world. Relational DBMS do have a standardized access control model, but it is coarse-grained: access rights are granted on entire relations or columns of relations. This limits the kinds of access control policies that can be easily defined.
Our goal is to develop a well-defined, efficiently implementable, fine-grained database access control model. In relational DBMSs, such a model allows access rights to be specified and managed at the level of individual tuples (rows) or attributes (fields). In an XML or object database, rights can be specified and controlled for individual objects or individual elements of an XML document.
Our work addresses several challenges associated with fine-grained access controls. First, because there are many database elements for which access is to be controlled, access rights may be cumbersome to specify and costly to store. The access control specification itself is potentially very large, since controls must be specified for individual database elements. Thus, there must be some means of compactly encoding this specification. In our work [2] , we have developed compact representations of fine-grained access controls for XML data. To obtain a compact representation, we exploit two properties of the access control specifications. One property is the structural locality of the access controls with respect to the tree structure of the XML data. The other is commonalities in access rights among the different users of the system. Second, access control administration may be decentralized and spread over thousands of users, with each user having jurisdiction over some portion of the database. With thousands of users managing their own data, the maintenance of access control cannot be funneled through a centralized administration, and yet the security of the system as a whole depends on the secure maintenance of the access control data. We insist that access to access control data, and indeed to any data in the database, be controlled by one, uniform mechanism. We have extended the role-based access control (RBAC) model to address the needs of fine-grained access control that is managed by the creators of the data [1] . As part of our solution the collections of privileges and the set of users associated with each role are specified through rules described by XPath.
Finally, once access controls have been specified, it is necessary to enforce the specification efficiently as the database is queried and updated. That is, the database system must ensure that each user's queries "see" only those tuples or document elements that that user has the right to see. Access control checks must be very fast, since a single query may depend on many database elements. For XML databases, we have shown how to enforce fine-grained access controls during query processing so that there is little or no performance penalty relative to query processing without access controls [2] . This enforcement mechanism relies on the compact, fine-grained access right encoding that we have developed. The encoded access rights are physically clustered with the data elements that they refer to, and access control enforcement is tightly integrated with query evalution. More recently, we have been addressing the same problem in relational DBMSs.
