Document Open Access Logo

Possible and Certain Answers for Queries over Order-Incomplete Data

Authors Antoine Amarilli, Mouhamadou Lamine Ba, Daniel Deutch, Pierre Senellart

PDF
Thumbnail PDF

File

LIPIcs.TIME.2017.4.pdf
  • Filesize: 0.62 MB
  • 19 pages

Document Identifiers

Author Details

Antoine Amarilli
Mouhamadou Lamine Ba
Daniel Deutch
Pierre Senellart

Cite As Get BibTex

Antoine Amarilli, Mouhamadou Lamine Ba, Daniel Deutch, and Pierre Senellart. Possible and Certain Answers for Queries over Order-Incomplete Data. In 24th International Symposium on Temporal Representation and Reasoning (TIME 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 90, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.TIME.2017.4

Abstract

To combine and query ordered data from multiple sources, one needs to handle uncertainty about the possible orderings. Examples of such "order-incomplete" data include integrated event sequences such as log entries; lists of properties (e.g., hotels and restaurants) ranked by an unknown function reflecting relevance or customer ratings; and documents edited concurrently with an uncertain order on edits. This paper introduces a query language for order-incomplete data, based on the positive relational algebra with order-aware accumulation. We use partial orders to represent order-incomplete data, and study possible and certain answers for queries in this context. We show that these problems are respectively NP-complete and coNP-complete, but identify many tractable cases depending on the query operators or input partial orders.

Subject Classification

Keywords
  • certain answer
  • possible answer
  • partial order
  • uncertain data

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Serge Abiteboul, Richard Hull, and Victor Vianu. http://webdam.inria.fr/Alice/pdfs/all.pdf. Addison-Wesley, 1995.
  2. Bogdan Alexe, Mary Roth, and Wang-Chiew Tan. http://www.vldb.org/pvldb/vol8/p365-roth.pdf. PVLDB, 8(4), 2014. URL: http://dx.doi.org/10.14778/2735496.2735500.
  3. Lyublena Antova, Christoph Koch, and Dan Olteanu. World-set decompositions: Expressiveness and efficient algorithms. In ICDT, volume 4353 of Lecture Notes in Computer Science, pages 194-208. Springer, 2007. URL: https://arxiv.org/abs/0705.4442.
  4. Anastasios Arvanitis and Georgia Koutrika. http://www.dblab.ntua.gr/~tasosarvanitis/pubs/TKDE13.pdf. IEEE TKDE, 26(6), 2014.
  5. Pablo Barceló, Leonid Libkin, Antonella Poggi, and Cristina Sirangelo. http://homepages.inf.ed.ac.uk/libkin/papers/jacm-pods09.pdf. J. ACM, 58(1), 2010. URL: http://dx.doi.org/10.1145/1870103.1870107.
  6. Michael Benedikt and Luc Segoufin. http://www.lsv.ens-cachan.fr/~segoufin/Papers/Mypapers/invfo.pdf. Journal of Symbolic Logic, 74, 2009.
  7. Andeas Brandstädt, Van Bang Le, and Jeremy P. Spinrad. Posets. In Graph Classes. A Survey, chapter 6. SIAM, 1987. Google Scholar
  8. Peter Buneman, Achim Jung, and Atsushi Ohori. http://www.sciencedirect.com/science/article/pii/0304397591902665. TCS, 91(1), 1991.
  9. Jan Chomicki and David Toman. Time in database systems. In Handbook of Temporal Reasoning in Artificial Intelligence. Elsevier, 2005. Google Scholar
  10. Edgar F. Codd. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.84.9469. TODS, 4(4), 1979.
  11. Latha S. Colby, Edward L. Robertson, Lawrence V. Saxton, and Dirk Van Gucht. https://www.cs.indiana.edu/~vgucht/p179-colby.pdf. In PODS, 1994.
  12. Latha S. Colby, Lawrence V. Saxton, and Dirk Van Gucht. http://www.sciencedirect.com/science/article/pii/0306457394900787. Information Processing &Management, 30(5), 1994.
  13. Robert P. Dilworth. A decomposition theorem for partially ordered sets. Annals of Mathematics, 1950. Google Scholar
  14. Cynthia Dwork, Ravi Kumar, Moni Naor, and Dandapani Sivakumar. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.8702. In WWW, 2001.
  15. Ronald Fagin, Amnon Lotem, and Moni Naor. http://researcher.watson.ibm.com/researcher/files/us-fagin/jcss03.pdf. In PODS, 2001.
  16. Wenfei Fan, Floris Geerts, and Jef Wijsen. http://homepages.inf.ed.ac.uk/fgeerts/pdf/currency.pdf. TODS, 37(4), 2012.
  17. Roland Fraîssé. L'intervalle en théorie des relations; ses genéralisations, filtre intervallaire et clôture d'une relation. North-Holland Math. Stud., 99, 1984. Google Scholar
  18. D. R. Fulkerson. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.226.652. In Proc. Amer. Math. Soc, 1955.
  19. Michael R. Garey and David S. Johnson. Computers And Intractability. A Guide to the Theory of NP-completeness. W. H. Freeman, 1979. Google Scholar
  20. Stéphane Grumbach and Tova Milo. http://www.cs.tau.ac.il/~milo/projects/query_languages/papers/icdt95.ps. In ICDT, 1995.
  21. Stéphane Grumbach and Tova Milo. http://www.sciencedirect.com/science/article/pii/S0022000096900422. JCSS, 52(3), 1996. URL: http://dx.doi.org/10.1006/jcss.1996.0042.
  22. Stéphane Grumbach and Tova Milo. http://www.sciencedirect.com/science/article/pii/S0890540198927778. Inf. Comput., 150(2), 1999. URL: http://dx.doi.org/10.1006/inco.1998.2777.
  23. John M. Howie. Fundamentals of semigroup theory. Oxford: Clarendon Press, 1995. Google Scholar
  24. Tomasz Imieliński and Witold Lipski. Incomplete information in relational databases. J. ACM, 31(4), 1984. Google Scholar
  25. Neil Immerman. http://www.sciencedirect.com/science/article/pii/S0019995886800298. Inf. Control, 68(1-3), 1986.
  26. Marie Jacob, Benny Kimelfeld, and Julia Stoyanovich. http://www.vldb.org/pvldb/vol7/p1255-jacob.pdf. VLDB Endow., 7(12), 2014.
  27. Werner Kiessling. http://www.vldb.org/conf/2002/S09P04.pdf. In VLDB, 2002.
  28. Maurizio Lenzerini. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.91.9907. In PODS, 2002. URL: http://dx.doi.org/10.1145/543613.543644.
  29. Leonid Libkin. http://homepages.inf.ed.ac.uk/libkin/papers/th-wsh.pdf. In Semantics in Databases, 1998.
  30. Leonid Libkin. http://homepages.inf.ed.ac.uk/libkin/papers/pods06a.pdf. In PODS, 2006. URL: http://dx.doi.org/10.1145/1142351.1142360.
  31. Leonid Libkin. http://homepages.inf.ed.ac.uk/libkin/papers/pods14.pdf. In PODS, 2014.
  32. Leonid Libkin. http://drops.dagstuhl.de/opus/volltexte/2015/4979/. In ICDT, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.ICDT.2015.94.
  33. Leonid Libkin and Limsoon Wong. http://www.sciencedirect.com/science/article/pii/S0022000097915233. J. Comput. Syst. Sci., 55(2), 1997. URL: http://dx.doi.org/10.1006/jcss.1997.1523.
  34. Witold Lipski, Jr. On semantic issues connected with incomplete information databases. TODS, 4(3), 1979. Google Scholar
  35. Wilfred Ng. https://www.cse.ust.hk/faculty/wilfred/paper/tods01.pdf. TODS, 26(3), 2001.
  36. Bernd Schröder. Ordered Sets: An Introduction. Birkhäuser, 2003. Google Scholar
  37. Richard T. Snodgrass, Jim Gray, and Jim Melton. Developing time-oriented database applications in SQL. Morgan Kaufmann, 2000. Google Scholar
  38. Mohamed A. Soliman and Ihab F. Ilyas. https://cs.uwaterloo.ca/~ilyas/papers/SolimanICDE09.pdf. In ICDE, 2009. URL: http://dx.doi.org/10.1109/ICDE.2009.102.
  39. Mohamed A. Soliman, Ihab F. Ilyas, and Shalev Ben-David. https://cs.uwaterloo.ca/~ilyas/papers/SolimanVLDBJ2010.pdf. VLDBJ, 19(4), 2010.
  40. Richard P. Stanley. Enumerative Combinatorics. Cambridge University Press, 1986. Google Scholar
  41. Kostas Stefanidis, Georgia Koutrika, and Evaggelia Pitoura. http://people.uta.fi/~kostas.stefanidis/docs/tods11.pdf. TODS, 36(3), 2011.
  42. Dan Suciu, Dan Olteanu, Christopher Ré, and Christoph Koch. Probabilistic Databases. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2011. Google Scholar
  43. Ron van der Meyden. http://www.sciencedirect.com/science/article/pii/S0022000097914550. JCSS, 54(1), 1997.
  44. Manfred K Warmuth and David Haussler. http://www.sciencedirect.com/science/article/pii/0022000084900187. JCSS, 28(3), 1984.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact