Computing Queries on Linear Constraint Databases

Abstract

We consider rational linear constraint databases, and study the problem of evaluating efficiently first-order queries with linear constraints. We show that although queries admit low data complexity (NC), their naive evaluation is rather ine cient. The computation paradigm is based on relational algebra and constraint solving. We focus on the former, and show that the query processing should differ drastically from classical relational databases. In particular, optimization strategies used for relational queries may be inadequate. We describe the problem and propose some preliminary optimization principles.

Conference

Publication date: September 1995

Publication date (Print): September 1995

Pages: 1-22

Affiliations

University of Toronto and INRIA

L.R.I.- Université de Paris Sud and INRIA

Article

DOI: 10.14236/ewic/DBPL1995.17

Copyright statement: © Zoé Lacroix et al. Published by BCS Learning and Development Ltd. Proceedings of the Fifth International Workshop on Database Programming Languages, Gubbio, Umbria, Italy

License:

This work is licensed under a Creative Commons Attribution 4.0 Unported License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

Conference name: Proceedings of the Fifth International Workshop on Database Programming Languages

Conference acronym: DBPL-5

Conference number: 5

Conference location: Gubbio, Umbria, Italy

Conference date: 6-8 September 1995

Conference sponsor: Electronic Workshops in Computing (eWiC)

Conference theme: Database Programming Languages

Product

Product Information: 1477-9358BCS Learning & Development

Self URI (article page): https://www.scienceopen.com/hosted-document?doi=10.14236/ewic/DBPL1995.17

Self URI (journal page): https://ewic.bcs.org/

Categories

Series title: Electronic Workshops in Computing