Schema polynomials and applications

ABSTRACT

Conceptual complexity is emerging as a new bottleneck as data-base developers, application developers, and database administrators struggle to design and comprehend large, complex schemas. The simplicity and conciseness of a schema depends critically on the idioms available to express the schema. We propose a formal conceptual schema representation language that combines different design formalisms, and allows schema manipulation that exposes the strengths of each of these formalisms. We demonstrate how the schema factorization framework can be used to generate relational, object-oriented, and faceted physical schemas, allowing a wider exploration of physical schema alternatives than traditional methodologies. We illustrate the potential practical benefits of schema factorization by showing that simple heuristics can significantly reduce the size of a real-world schema description. We also propose the use of schema polynomials to model and derive alternative representations for complex relationships with constraints.

REFERENCES

• 1: Extensible markup language (XML). http://www.w3.org/XML/.
• 2: Oracle9i database release 2 (9.2) documentation. http://www.oracle.com/technology/documentation/oracle9i.html.
• 3: The unified modeling language user guide. 2005.
• 4: Alexander Aiken , Dexter Kozen , Moshe Y. Vardi , Edward L. Wimmers, The Complexity of Set Constraints, Selected Papers from the 7th Workshop on Computer Science Logic, p.1-17, September 13-17, 1993
• 5: Paolo Atzeni , Nicola M. Morfuni, Functional dependencies in relations with null values, Information Processing Letters, v.18 n.4, p.233-238, May 1984 [doi>10.1016/0020-0190(84)90117-0]
• 6: F. Baader, R. K"usters, and R. Molitor. Rewriting concepts using terminologies. In KR, pages 297--308, 2000.
• 7: Franz Baader , Anni-Yasmin Turhan, On the Problem of Computing Small Representations of Least Common Subsumers, Proceedings of the 25th Annual German Conference on AI: Advances in Artificial Intelligence, p.99-113, September 16-20, 2002
• 8: Grady Booch , James Rumbaugh , Ivar Jacobson, The Unified Modeling Language user guide, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1999
• 9: R. K. Brayton, R. L. Rudell, A. L. Sangiovanni-Vincentelli, and A. R. Wang. Multi-level logic optimization and the rectangular covering problem. In ICCAD, pages 66--69, 1987.
• 10: Peter Buneman , Benjamin C. Pierce, Union Types for Semistructured Data, Revised Papers from the 7th International Workshop on Database Programming Languages: Research Issues in Structured and Semistructured Database Programming, p.184-207, September 01-03, 1999
• 11: I. Dagan and A. Itai. A set expression based inheritance system. Annals of Mathematics and Artificial Intelligence, (4):269--280, 1991.
• 12: A. Hosangadi, F. Fallah, and R. Kastner. Optimizing polynomial expressions by algebraic factorization and common subexpression elimination. IEEE Trans. on CAD of Integrated Circuits and Systems, 25(10):2012--2022, 2006.
• 13: Ivar Jacobson , Grady Booch , James Rumbaugh, The unified software development process, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 14: Mark Levene , George Loizou, Axiomatisation of functional dependencies in incomplete relations, Theoretical Computer Science, v.206 n.1-2, p.283-300, Oct. 6, 1998 [doi>10.1016/S0304-3975(98)80029-7]
• 15: Raghu Ramakrishnan , Johannes Gehrke, Database Management Systems, McGraw-Hill Science/Engineering/Math, 2002
• 16: K. A. Ross and J. Stoyanovich. Schema polynomials and applications. Columbia University Technical Report, (cucs-047-07), 2007.
• 17: Odysseas G. Tsatalos , Marvin H. Solomon , Yannis E. Ioannidis, The GMAP: a versatile tool for physical data independence, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.2, p.101-118, April 1996 [doi>10.1007/s007780050018]
• 18: Y. Tzitzikas, A. Analyti, and N. Spyratos. Compound term composition algebra: The semantics. J. Data Semantics, 2:58--84, 2005.
• 19: Y. Tzitzikas, A. Analyti, N. Spyratos, and P. Constantopoulos. An algebraic approach for specifying compound terms in faceted taxonomies. In EJC, pages 67--87, 2003.
• 20: Christopher Umans, The minimum equivalent DNF problem and shortest implicants, Journal of Computer and System Sciences, v.63 n.4, p.597-611, December 2001 [doi>10.1006/jcss.2001.1775]
• 21: B. Wynar. Introduction to Cataloging and Classification. Libraries Unlimited, Inc., 8th edition, 1992.
• 22: Cong Yu , H. V. Jagadish, Schema summarization, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema