Home // DBKDA 2012, The Fourth International Conference on Advances in Databases, Knowledge, and Data Applications // View article

Reasoning about Domain Semantics over Relations, Bags, Partial Relations and Partial Bags

Authors:
Sebastian Link

Keywords: Data models; Database design; Database semantics; Decision problems; Mathematical logic

Abstract:
Quality database schemata must capture both the structure and semantics of the domain of interest. Classes of data dependencies have been studied extensively to model domain semantics. Traditionally, the theory of data dependencies has been limited to relations. In practice, duplicate and partial information are permitted to occur in database instances. These features are supported to make data processing more efficient. We study the implication problem for an expressive class of data dependencies over all data structures that arise from the two features features. These include bags that permit duplicate tuples, partial relations that permit null marker occurrences, and partial bags that permit duplicate tuples and null marker occurrences. The class of data dependencies studied encompasses uniqueness constraints, functional and multivalued dependencies. We establish axiomatizations and sharp upper bounds for the worst-case time complexity of the implication problem.

Pages: 1 to 8

Copyright: Copyright (c) IARIA, 2012

Publication date: February 29, 2012

Published in: conference

ISSN: 2308-4332

ISBN: 978-1-61208-185-4

Location: Saint Gilles, Reunion

Dates: from February 29, 2012 to March 5, 2012